### CS534 Artificial Intelligence Homework 2 - Fall 2007

#### PROF. CAROLINA RUIZ

Due Date: September 20, 2007 at the beginning of class

• Read Chapters 3, 4, 5, and 6 of the textbook.

• Problems: You need to turn in written solutions ONLY TO THE PROBLEMS MARKED WITH AN ASTERISK "*" BELOW at the beginning of class on September 20, 2007. Solve the other problems before the class so that you can ask questions about them in preparation for Exam 1.

1. Chapter 3: 3.6,3.8*, 3.9, 3.12, 3.13*, 3.14, 3.17.

2. Chapter 4: 4.1, 4.2*, 4.3*,4.7, 4.11*, 4.16.

3. Construct a search space together with an admissible heuristic for which each of the search methods listed below produces a different sequence of expanded states (that is, the states and/or the order in which the states are expanded is different for each search method). The search methods you should take into consideration are: depth-1st, breadth-1st, depth-limited (limit=3), uniform (i.e., branch and bound), A*, greedy search, hill-climbing, and beam search (w = 2).

4. * Describe the general behavior of the search methods listed below in terms of how they handle a "queue" that keeps track of which paths are expanded and in what order. Describe this general behavior by answering the following questions. Note that the answers to questions 1, 2, 3, 4, and 6 should be the same for all search methods, so answer them just once. The answer to part 5 depends on the particular search method.
1. what is a path?
2. how is the queue initialized (be precise!)?
3. what path in the queue is selected for expansion?
4. once that a path is selected for expansion, how is it expanded?
5. where are the expansions of the selected path addeded to the queue?
6. when does the search terminate and why?
The search methods you should take into consideration are: depth-1st, breadth-1st, depth-limited, iterative deepening, uniform (i.e., branch and bound), A*, greedy search, hill-climbing, and beam search.