Homework Assignment 2
601.464/664
Search
In this part of the assignment, you will implement search agent and answer some theoretical questions.
Question 1. Open the following google colaboratory notebook. Follow all the steps specified in it. Include
link to your solved notebook in your submission. Some parts of the notebook are optional and will not be
graded.
Question 2. What is uninformed search and informed one. Name specific methods of both.
Question 3. Is depth-first search optimal if step costs are all equal? Is breadth-first optimal in this case?
Question 4. When is breadth-first search complete and optimal? What is the time and space complexity?
Question 5. Is breadth-first search optimal if cost of every step exceeds some small positive constant ? and
costs are not equal? Why ? Is uniform-cost search optimal in this case?
Question 6. What is the time and space complexity of uniform-cost search? Under what conditions it is
complete?
1
