COS 226 Final Information, Fall 2009

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

Final Exam Schedule

Corey will hold office hours at 2-4pm on Wednesday, January 13.
Berk will hold office hours at 2-4pm on Thursday, January 14.
Anu will hold office hours at 10-12noon on Friday, January 15.
Kevin will havea a review session at 2-4pm on Monday, January 18 in CS 105 (small auditorium).
The final exam is at 9am on Tuesday, January 19 in CS 104 (large auditorium).

Exam Format

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).

Material Covered

We have covered an enormous amount of material this semester, but the exam can only contain basic questions about a small fraction of it. When you study, you should focus on understanding basic issues, not memorizing details. For each algorithm, you should make sure that you understand how it works on typical input and then ask yourself some basic questions: Why do we care about this algorithm? How is it different from other algorithms for the same problem? When is it effective? Knowing the answer to those sorts of questions is the key to doing well on the exam.

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

Algorithms in Java, 4th edition: Chapter 6.1 - 6.5.
Algorithms in Java, Part 5, 3rd edition: Chapters 17 - 21.
Algorithms in C, 2nd edition: Chapters 24-27.
Lectures 12-24.
Programming assignments.

But some material before the midterm is also relevant to putting new algorithms in context. For example, you might see a question on sorting/searching that covers both standard and string algorithms.

Partial list of topics covered since the midterm

LSD radix sort	MSD radix sort	3-way string 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	Range / nearest neighbor search	HV line intersection
Reductions	Combinatorial search

Questions that show awareness of advanced topics that were covered in lecture are also fair game. Examples: NP-completeness.

Graph Processing

To prepare for the graph processing part of the exam, here are parts of Algorithms in Java that we covered this semester in lecture.

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.