Module 1 Flashcards
Time complexity of BFS?
O(b^d)
Is BFS optimal?
Yes (if cost = 1 per step); not optimal in general
Space complexity of BFS?
O(b^d)
What are uninformed search strategies?
Uninformed search strategies are algorithms that do not use domain-specific knowledge to guide the search but instead explore the search space systematically.
List the main types of uninformed search strategies
Breadth-first search
Uniform-cost search
Depth-first search
Depth-limited search
Iterative deepening search
What are the four evaluation criteria for search strategies?
- Completeness (guarantees finding a solution if one exists).
- Time complexity (time to find a solution).
- Space complexity (memory usage).
- Optimality (whether it finds the best solution).
What is breadth-first search?
Breadth-first search expands nodes at the shallowest depth first, using a FIFO queue.
What are the advantages of breadth-first search?
It is complete and finds the least-cost solution if the cost is uniform across nodes.
What is a major drawback of breadth-first search?
It has high space complexity due to the number of nodes stored in memory.
DFS space complexity?
O(bd)
Why use a uniform-cost search?
Because we can manage trees where the cost is not uniform. If applied to BFS, it guarantees completeness.
What is limited DFS?
It’s a variant to DFS with an hyperparameter for the maximum depth. This can truncate the tree to avoid infinite branches and avoid loops.
Is DFS complete?
No, because there can be infinite branches or loops where the DFS keeps searching, since it explorates the deepest nodes first
Which data structure use DFS?
LIFO queue
Which data structure use BFS?
FIFO queue
