**When and where:**

Wednesday, May 9, 2001, 12-2 pm, 1505 Seaman's Center

**Material to read:**

- Chapters 10 (Selection) and 12 (Hashing). Sections 17.1, 17.2, and 17.3 (Greedy Algorithms), Sections 23.1 and 23.2 (Graph Traversals), and Sections 25.1, 25.2, 25.3, and 25.4 (Shortest Paths).
- Solutions to Homeworks 4-8. Problems in the exam may refer to homework problems or their solutions, so bring these along to the exam.
- Solutions to Practice Problems. Problems in the exam may refer to practice problems or their solutions, so bring these along to the exam.

**Format of the exam:**

The exam is open notes and open book. It is worth 350 points
(35% of your entire grade).
It contains 5 problems, each worth 70 points.
Each problem has 2 parts, each worth 35 points.

- Problem 1 is on the selection problem: There are many interesting problems in the book on selection and median finding. Working on these problems before the finals will be good practice.
- Problem 2 is on hashing: You should know what makes a good hash function. In particular, what is a simple uniform hash function? When is a hash function used for open addressing good? What conditions ensure that a hash function used in open addressing yields a probe sequence that is a permutation?
- Problem 3 is on the greedy method: Review all the examples of the greedy method we studied in class. Practice constructing counterexamples to wrong greedy algorithms. Review the proofs of correctness of greedy algorithms.
- Problem 4 is on graph representation and traversal: How does BFS work? What proparties do the d-values and pi-values have?
- Problem 5 is on shortest path algorithms: Think about how to improve Dijkstra's algorithm and the Bellman-Ford algorithm for special cases of the shortest path problem.