## Final Exam Information |
## Spring 2005 |

**Date, time and place.** The final exam will be held in McCosh Hall 28
at 9am on Tuesday, May 17. The exam will be three hours.

**What to bring. **Like the midterm, the final exam will be ** closed book**,
but **you may bring a one-page
"cheat sheet"** consisting of a single, ordinary 8.5"x11"
blank sheet of paper with whatever notes you wish written upon it. You may
write on both the front and the back. However, it must be * handwritten* (not
computer generated or photocopied) in * your own * handwriting.

You may * not* use the text book, your notes, a computer, calculator or any other materials
during the exam.

**Previous year exams.** Some exams from previous years are
available
here. Keep in mind that the material covered varies from year to year.

**Review session.** A review session will be offered sometime before the exam.
More details will be announced shortly.

**What will be covered.** The exam will cover the entire semester
with a strong emphasis (perhaps, 3 to 1) on material covered since the midterm.
This includes material covered at the very end of the course which might have
only been lightly covered on the homeworks (such as the simplex algorithm and
NP-completeness). In principle, anything covered in lecture or in the
required readings is "fair game" for the exams. However, realistically, you can
expect that the emphasis will be placed on those same topics that were
emphasized in lecture and on the homeworks.

Below is a list of topics, concepts and algorithms that you should be familiar with. I have attempted to make this an exhaustive list, although I cannot guarantee that I did not miss an item or two.

- union-find
- sorting
- insertion sort
- selection sort
- bubble sort
- quicksort
- mergesort
- lower bound on comparison-based sorting

- priority queues, heaps and heapsort
- symbol tables
- hash tables
- separate chaining
- linear probing
- double hashing

- binary search trees
- randomized BST
- splay trees
- red-black trees

- tries
- patricia tries
- multi-way tries
- ternary search tries

- radix sort
- data compression
- entropy and information
- prefix (a.k.a. instantaneous) codes
- Kraft inequality
- Shannon-Fano code
- Huffman code
- Lempel-Ziv

- dynamic programming
- graphs
- adjacency list and adjacency matrix
- depth-first search
- breadth-first search
- Euler tours
- minimum-spanning tree
- Prim's algorithm
- Kruskal's algorithm

- transitive closure
- topological sort
- strongly connected components and Kosaraju's algorithm
- shortest paths
- Dijkstra's algorithm
- shortest paths in DAG's
- Bellman-Ford

- max-flow and min-cut
- Ford-Fulkerson
- maximum-bipartite matching

- convex hulls
- package wrap (Jarvis's march)
- Graham scan

- finding closest pair of points
- range search and k-D trees
- finding all intersections in a set of line segments
- horizontal-vertical special case
- general case

- linear programming: pivoting, simplex algorithm, duality
- NP-completeness

**Good luck!**