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:
- 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.
- The PRIORITY QUEUE ADT and its heap implementation.
- Applications of the PRIORITY QUEUE ADT.
This includes Prim's MST algorithm and
Dijkstra's shortest path algorithms.
- 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.
- Problems 2 and 3 from this homework from spring 2007.
- Problems 1, 2 and 4 from this final from spring 2007.
- Problems 2(a), 3, 4, and 5 from this
final from spring 2006.