About the final

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.