CSE 326 - Autumn 2000

Homework #6
Due: Friday Dec 1st (Two weeks)


1. Weiss 9.7 (a).  (Explain where Dijkstra goes wrong on your example.)

2. Weiss 9.15.

3. Recall that A* uses
	f(n) = g(n) + h(n)
as the priority of a node, where g(n) is the distance (cost) from the
start and the heuristic h(n) is a lower-bound estimate of the distance
to a goal node.  Suppose that h(n) is in fact always exactly the the
true minimum distance from n to a goal node.  Prove that A* will never
expand (i.e. remove from the priority queue) a node that is not on a
shortest path to a goal node.  (You can simplify your argument by 
assuming that there is only a single goal node.)

4. Draw both the 2-d tree and the quad trees that correspond to the
   final panels in figures 12.52 and 12.53 in Weiss (page 539)
   respectively.

BONUS:

5. Weiss 9.44 (pseudocode).