Uninformed Search(Week 3)

Question 1

Uninformed Search Algorithm?

Answer 1

-Blind Search: It doesnot have any additional information about state or search space. It only knows how to traverse through
- No cost consideration
- It might take up more time

Question 2

types of uninformed search algorithms?

Answer 2

• Breadth first Search
• Depth first Search
• Uniform Cost Search

Question 3

What properties of search algorithm are considered?

Answer 3

• Optimal: Provides least cost path
• Complete: if it provides any solution path
• Time Complexity: Maximum amount of time needed to traverse through.
• Space Complexity: Least amount of space needed to traverse

Question 4

Depth first search properties

Answer 4

• Expands the deepest node first
• Starts from leftmost deepest node
• Time taken: O(b^m) where m is maximum depth and is finite
• Space taken: O(bm)
• Can give complete solution

Question 5

Is DFS complete or optimal? How?

Answer 5

Its complete if m (i.e. maximum depth) is finite.
It may not be optimal because it always finds the left-most solution,regardless of depth or cost.

Question 6

What are Breadth first search properties?

Answer 6

• Expands the shallowest node first
• Explores all nodes above shallowest node
• Time taken is O(b^s) where s is depth of shallowest solution
• Space is also O(b^s)
• Can be complete or optimal
• It finds the shortest path in terms of number of actions, it might jot always be the least-cost path

Question 7

Is BFS complete or optimal?

Answer 7

It can be both. Its complete because s (i.e. number of solutions) is finite and its optimal if costs are all 1.

Question 8

Difference between DFS & BFS

Answer 8

DFS
- Expands deepest node first
- Better in space complexity (b*m)
- For deepest goal
BFS
- Expands tier by tier
- Exponential space complexity (b^m)
- For shallowest goal.

Question 9

What is Space Complexity & Time Complexity?

Answer 9

Space Complexity: Least amount of space needed by search algorithm to traverse through

Time Complexity: Maximum amount of time needed to traverse

Question 10

What fringe strategies/ Priority Queues are used for each search algorithm ?

Answer 10

Priority queue is dependent on environment and what is required more
For DFS: LIFO i.e. Last In First Out
For BFS: FIFO i.e. First In First Out (Shallowest)
For UCS: Cost

Question 11

What are Uniform Cost Search properties?

Answer 11

• Expands cheapest node first
• Space & time complexity stays the same because solution depends on cost
• It provides both optimal and complete solution

Question 12

Issues of UCS?

Answer 12

• Explores options in every direction
• No information about goal location
• Time complexity is higher