The final is open notes/book. It is from 2:15-4:15 in Room 1505 SC (our classroom) on Monday, 5/8.

For the final you should read (i) your notes from lectures and discussion sections, (ii) problem sets and their solutions, (iii) projects and their solutions, (iv) sample code, (v) relevant material from the textbook, and (vi) Lafore's code. From the text book read: Chapter 4 (exluding the material on parsing arithmetic expressions), Chapter 6, Chapter 7 (excluding the material on radix sort), Chapter 8 (excluding the material on Huffman codes), Chapter 12, Chapter 13 (only pages 615-642), Chapter 14 (only pages 687-707). The final exam is comprehensive in the sense that material covered before the midterm such as running time analysis, linked lists, etc. will be quite relevant. However, the focus will be on material covered after the midterm. A detailed list of these topics is below.

Specific topics, that the final covers, are:

1. Adjacency list representation of graphs: how to implement the methods addEdge, deleteEdge, addVertex, deleteVertex, etc. of the myGraph class if we change the underlying representation from an adjacency matrix representation to an adjacency list representation; determining the running times of these methods as a function of the number of vertices and the number of edges in the graph; comparing these running times with corresponding running times in the adjacency matrix implementation. A bit of this is covered in Chapter 13 on Graphs.
2. Simple examples of recursion: computing Fibonacci numbers, linear search, binary search, etc. Drawing recursion trees that show the execution of recursive algorithms. Chapter 6.
3. Implementing divide-and-conquer sorting algorithms using recursion: mergeSort and quickSort, the merge function and the partition function, and running time analysis of these functions; improving the running time of quickSort by using median-of-three rule and randomization; the recursive solution to the Towers of Hanoi problem. Chapters 6 and 7.
4. Implementing backtracking using recursion: the knapsack problem and its solution, the Queens problem and its solution, and depth first traversal. Chapters 6 and 13.
5. The Stack ADT and the connection between recursion and stacks: activation records and the system stack; translating recursive functions into equivalent functions that make explicit use of the stack; examples such as: the stack based fibonacci function and the stack based solution to the Towers of Hanoi problem. Chapters 4 and 6.
6. The Queue ADT and implementing breadth-first search: different implementations of the Queue ADT, application of the Queue ADT to breadth first search, and computation of the breadth first search trees. Chapters 4 and 13.
7. The PriorityQueue ADT and binary heaps: what a binary heap is and how the PriorityQueue ADT is implemented by a binary heap, implementation of a binary heap using an array, the running times of binary heap operations. Chapter 12.
8. Heap Sort and Dijkstra's shortest path algorithm: using a binary heap to sort in O(n log n) time; Dijkstra's shortest path algorithm and its two implementations: one that runs in O(n^2) and the other (based on binary heaps) that runs in O((m+n) log n) time. Chapters 12 and 14.
9. Skip lists: how skip lists generalize the notion of linear lists, what role randomization plays, implementation of the skip list operations. Problem Set 12 and the links therein.
10. Binary Search trees: what a binary search tree is, the implementation of the three binary search tree operations, and their running time. Chapter 8.

The final contains 5 problems, each worth 40 points.