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:
- 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.
- 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.
- Applications of the PRIORITY QUEUE ADT.
This includes 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.
- All problems except Problem 3(1) in the
final from fall 2007.