Reading

• Russell and Norvig, chapters 2 and 3

Doing

1. Do Exercise 2.4, second and third bullet items (Titan, books) on page 62.
2. Do Exercise 3.9 on page 115. But don't do any programming. Do part b "by hand" (and brain), drawing a few diagrams to show intermediate steps of your search algorithm. And make sure in part b to state the name of the search algorithm you use.
3. Run the program PathDemo.exe, and read the associated readme.txt file, both in PathDemo.zip. Try each of the following search algorithms in PathDemo, and write a few sentences answering these questions:
   • Breadth First: If you put more expensive (cost greater than 1, but not "X" or forbidden) squares between the Start and the Goal, how does this affect the path found?
   • Depth First: What happens if the Search Depth is less than the distance from Start to Goal? What happens if Search Depth is much greater than the distance from Start to Goal, and you un-select "Aim to Goal First"?
   • IDDF (Iterative Depth First Search): How is IDDF affected by putting some more expensive squares on and near the direct path from Start to Goal?
4. Consider a problem with states labeled H, L, M, P, S, T, V, W, and Z. The initial state is P and the goal state is Z. The following state to state transitions (operators) are allowed, followed by their costs: from L to P, cost 10; from P to S, cost 20; from P to T, cost 3; from P to V, cost 10; from S to L, cost 20; from S to M, cost 15; from S to Z, cost 20; from T to W, cost 25; from V to M, cost 15; from V to S, cost 5; from W to H, cost 4; from W to Z, cost 10.
   • Draw a graph representing this problem.
   • Show the search trees resulting from solving the problem using breadth-first search (Fig. 3.11), uniform cost search (Fig. 3.14), depth-first search (either BFS from 3.11 with a LIFO queue for frontier or the recursive version in 3.17), and iterative deepening search (Fig. 3.18). Next to each node in each search tree, write a number indicating the order in which it was removed from frontier. For each search, show the value of the frontier queue right after the goal is recognized and before the algorithm returns. If expanding a node results in more than one "child" node, put the child nodes on frontier so that they will be removed in alphabetical order (except for uniform cost search).

Details

• upload a Word (.doc or .docx) or a PDF file to the EEE dropbox "CS 171 - hw 2" before 11:55pm (based on the EEE server's clock) on Friday, Jan. 18; or
• hand in a printed or neatly hand-written printed copy of your assignment at the start of lecture, 12:00 noon sharp, on Friday, Jan 18 -- make sure your name is clearly written at the top of the first page, and multiple pages are stapled together.

Late homeworks will be accepted through midnight at the end of Sunday, Jan. 15, with a 50% penalty. (No later submission will be accepted.)