CSCE 625 - Homework #1
due: Wed, Sep 14 (hand-in hard-copy in class)

1. Write out a formal proof that the uniform-cost algorithm is optimal.

2. In a search with a branching factor of 5 and a maximum tree depth
of 20 (not counting the root) and in which the only goal node occurs on
the end of the 10th expanded row, calculate how many goal tests will
be performed by BFS, DFS, and ID (iterative deepening).  What is the
maximum size of that the queue grows in each case?