1. R&N: Exercise 3.3 (a,d)
SOLUTION:
I pretty much accepted anything that was plausible. Some of you allotted path costs for the map coloring problem and some of you asserted that the path cost does not matter for this problem. I accepted both answers.
2. Consider the formulation of the 8queens problem on the top of page 65
in R&N, with an empty chess board for the initial state. What makes more
sense in this case, breadthfirst or depthfirst search? Why?
SOLUTION:
The key notion is that depthfirst search will probably find the solution faster, since it will always lie at the leaves of the search tree. The fact that the search tree is finite for this problem (you won’t put more than 8 queens on the board, so no search path will be infinite) also leads to depthfirst, since you want to take advantage of it’s lower space requirements if you can.
3. What are the memory and time requirements for breadth, depth and
iterative deepening search for
i) branch factor 2, depth 10
ii) branch factor 10, depth 10
SOLUTION:

Breadthfirst 
Depthfirst 
Iterative Deepening 


Time 
Space 
Time 
Space 
Time 
Space 
BF2,
D10 
2047 
2047 
2047 
20 
4083 
20 
BF10,
D10 
11111111111 
11111111111 
11111111111 
100 
123456789011 
100 
I also accepted worstcase answers of the form O(b^n)… or any response that displayed understanding that there are some important constants in there. It’s important to understand that depthfirst search and iterative deepening have different behaviors when it comes to time, since iterative deepening has to regenerate nodes for each iteration.
4. What is the "catch" with bidirectional search for most problems?
Give an example of a real application where it would help.
SOLUTION:
As many of you noted, there is more than one “catch” with bidirectional search. Most of you identified the ones listed in the book: the difficulty in generating predecessor states in some problems, the possible existence of multiple goal states, etc. The question asks for a problem where bidirectional search would help. Many of you offered map and maze problems, which was fine. I appreciated the more creative responses.
5. R&N: Exercise 3.20 (a)
SOLUTION:
There was a huge variation in the level of detail of your responses to this question. After going through the homeworks once, I decided on threshold for how many constraints I wanted listed (for full credit). Most of you got full credit.
The cryptarithmetic problem as a CSP:
Variables: The letters in the puzzle words.
Domain: Digits (09)
Constraints:
All the letters must have distinct digits assigned to them.
The mathematical expression that results from the assignments must hold.
The leftmost letter in each word can’t be zero.
…
6. Using the map on page 95 (figure 4.2) of R&N, show how breadthfirst
search would find a path from Dobreta to Bucharest. Then, show how A* search
would expand this path using the "straightline distance" to Bucharest as
your heuristic function. Your answers should use a format similar to that of
Figure 4.3 (a series of search trees).
SOLUTION:
I believe everyone did the graphs right for breadthfirst. On the graphs for bestfirst search, many of you expanded Pitesti before considering Mehadia, which actually has a lower f() value than any of Craiova’s children (Rimicu Vilcea, Dobreta, Pitesti). Bestfirst just looks at the f() values of the nodes in it’s queue, so Mehadia should be expanded before Pitesti (even though it reveals two nodes we won’t want to expand, subsequently).
7. Give an example of an admissable heuristic for the 8Queens problem.
SOLUTION:
This question caused a lot of confusion. I ended up giving full credit to just about any answer that displayed knowledge about admissible heuristics (what they are, why they’re important, etc…). Basically, all attempts that seemed sincere got full credit.
8. Give an example of a search problem in which simple hillclimbing would
provide better performance, on average, than simulated annealing. Why does
the simpler algorithm work better in this instance?
SOLUTION:
Simulatedannealing will make “bad moves” at times in order to avoid local maxima/minima. Most problems have some local maxima, so this is an important modification. However, if the problem has a very smooth “heuristic landscape,” it makes less since to take these sorts of measures. The class came up with a wide range of examples for these sorts of “simple” problems – again, I appreciated the more creative ones.