COS 226 Final Information, Spring 2010

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

Final Exam Schedule

May 20 - office hours:
Charlie 12-1pm in Icahn 225
Linjie 1-2pm in CS 418A
Maia 3-4pm in CS 205
There will be a review session at 5-7pm on Thursday, May 20 in Friend 006
The final exam is at 9am on Friday, May 21, Friend 101

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.

Lectures 12-24.
Algorithms in Java, 4th edition: Sections 4.3 and 4.4 (online).
Algorithms in Java, 4th edition: Sections 5.1 through 5.5
Algorithms in C, 2nd edition: Chapters 24-27 (online).
Exercises
Programming assignments.

The lecture slides are the primary reference for lectures 12-13 and 21-24; the text is the primary reference for lectures 14-20. 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	CPM/Arbitrage	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, satisfiability, independent set.