This document is intended to help you use your study time effectively. Please
view it as a guide, not a contract.

The Spring 2009 COS 226 final is Sunday, May 17 from 1:00-4:00pm in **Friend 101**.

The Q&A review session is Saturday, May 16, from 5:00-7:00pm **Friend 006**.

- Closed book, closed note.
- You may bring one 8.5-by-11 sheet (both sides) with notes in your own handwriting to the exam.
- No electronic devices (e.g., calculators, laptops, cell phones, MP3 players).

The exam is will *stress* material covered since the midterm,
including the following components.

- Algorithms in Java, 4th edition: 6.3-6.5
- Algorithms in Java, 3rd edition: 10, 15, 17-21
- Algorithms in C, 2nd edition: Chapters 24-27
- Lectures 12-24
- Programming assignments

LSD radix sort | MSD radix sort | 3-way radix quicksort | |

Depth-first search | Breadth-first search | MST algorithms (Prim, Kruskal) | |

Topological sort | Transitive closure | Shortest paths (Dijkstra) | Negative weights (Bellman-Ford) |

Knuth-Morris-Pratt | Boyer-Moore | Rabin-Karp | |

RE to NFA | R-way tries | Ternary search tries | |

Run-length encoding | Huffman coding | LZW compression | Burrows-Wheeler |

Convex hull (Jarvis, Graham) | 2D trees, quad trees | Range search | HV line intersection |

Reductions | Linear programming | Combinatorial search |

Questions that show awareness of advanced topics that were covered in lecture are also fair game. Examples: Voronoi/Delauney, linear programming.

**17.** Graph Properties and Types

Reading this entire chapter is a good way to be sure that you understand basic
concepts and terminology. You can check your understanding by working the easy
exercises.

**18.** Graph Search

This chapter goes into much more depth on the mechanics of search than we did
in lecture. It is critical that you understand DFS and basic DFS algorithms
(pages 87-97 and 105-112); BFS (Programs 18.7 and 18.8); and generalized
graph search (Program 18.9), but you may safely skim the detailed discussions
and skip section 18.4, 18.6, and 18.9
18.9.

**19.** Digraphs and DAGs

Your goal in this chapter is to understand directed graph search and
topological sort. Read 19.1, 19.2, and 19.6.
You may safely skim or skip the rest of the chapter.

**20.** Minimum Spanning Trees

For this chapter, you need to know Prim's and Kruskal's algorithm, including
how and why they work. To do so, you certainly need to read sections 20.1,
20.3, and 20.4 and also relevant text in 20.2.

**21.** Shortest Paths

Your main focus in this chapter should be understanding Programs 21.1,
21.6, and 21.9 along with the perspective of section 21.8 on single-source
problems. You may
skip material on the all-pairs algorithms, DAGs, and Euclidean graphs.
You do not need to study section 21.6 in detail, but
you should understand the concept of reduction as covered in lecture.