Search Algorithms Flashcards
What are the steps of a Breadth-First Search (BFS)?
(4 points)
- Pick a vertex.
- Explore that vertex, ‘visiting’ all adjacent vertices.
- Pick an unexplored vertex from among the adjacent vertices.
- Repeat steps 2 and 3 until the graph is explored.
What are the steps of a Depth-First Search (DFS)?
(4 points)
- Pick a vertex.
- Visit one of that vertex’s adjacencies.
- Repeat step 2 until we can’t find any.
- Once we can’t find any, backtrack and repeat step 2-3.
What are the steps of a Uniform Cost Search (UFS)?
What does it mean for a search algorithm to be ‘uninformed’ or ‘blind’?
Does not have any additional information about the search space besides its structure.
What does it mean for a search algorithm to be complete?
If it provides a solution for a given input if there does exist at least one solution. In other words, if a solution exists, it will always find it.
What does it mean for a search algorithm to be optimal?
The best solution given at the lowest path cost.
What is meant by time complexity?
Time complexity is the variable quantity of time used when running an algorithm.
For example, an algorithm with time complexity O(x) will take as much time as x exists. In most cases, this is the number of data points.
What is meant by space complexity?
Space complexity is the variable quantity of space or memory used when running an algorithm.
For example, if a algorithm uses a queue to store only data points, it would have a space complexity of O(x), where x is the number of data points given as input.
What is the time complexity of a BFS/DFS?
O(V + E), where V is the number of vertices and E is the number of edges.
What is the space complexity of a BFS/DFS?
O(V), where V is the number of vertices.
What is the difference between a Greedy Search and a Uniform Cost Search?
A Greedy Search goes straight for the closest, smallest cost, while UFS takes its time and finds the most optimal solution.
Greedy Search is not optimal or complete, but it is faster.
What are the two search algorithms that are both optimal and complete?
Breadth-First Search and Uniform Cost Search.
What are the two search algorithms that are neither optimal nor complete?
Depth-First Search and Greedy Search.
What is the difference between BFS and DFS?
A BFS carefully searches all of its adjacent vertices, while DFS ‘rushes to the end’ and only goes back once it has reached an endpoint.
Which is a type of informed search: Greedy or Uniform Cost?
Greedy Search.
