The final exam will take place on Monday, Dec 15th from noon to 2:00 pm in our classroom, 112 MH. Feel free to bring notes, books, and printouts; you will not be allowed to use your laptops. The final has 4 problems on it, each problem consisting of 2-4 parts. The topics covered by each problem are:
  1. Recursion. This includes examples of search with backtracking such as depth-first search, the 8-Queens Problem and the knapsack problem. This also includes examples of divide-and-conquer such as merge sort and quick sort.
  2. The PRIORITY QUEUE ADT and its heap implementation. This includes understanding algorithms, implementation, and running time of methods such as insert, delete, min or max.
  3. Applications of the PRIORITY QUEUE ADT. This includes Dijkstra's shortest path algorithms.
  4. Binary Search Trees and AVL Trees.

To practice for the test, you might want to solve these problems. This is by no means a comprehensive list.

  1. Problems 2 and 3 from this homework from spring 2007.
  2. Problems 1, 2 and 4 from this final from spring 2007.
  3. Problems 2(a), 3, 4, and 5 from this final from spring 2006.
  4. All problems except Problem 3(1) in the final from fall 2007.