The final exam will take place on Thursday, Dec 20th from 7:30 am to 9:30 am in our classroom, W207 PBB. 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 the 8-Queens Problem and the Travelling Salesman Problem and more. This also includes examples of divide-and-conquer such as merge sort and quick sort.
  2. The PRIORITY QUEUE ADT and its heap implementation.
  3. Applications of the PRIORITY QUEUE ADT. This includes Prim's MST algorithm and 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.