COS 226 final info

Information on final exam

Monday, May 17, 1:30pm
Frick 120
Closed book
You may bring one 8.5-by-11 sheet with notes in your handwriting to the exam
No calculators (or computers!)

Material Covered

The exam will only cover material from the second half of the course
Textbook, Chap. 16
Course packet on Strings and Geometry
Course packet on Graphs, Digraphs, and MSTs
Lecture notes for March 8 and later
Programming assignments 5-10
Problem sets 6-10

Review Session

There will be an optional review session for those interested:

Date: Wednesday, May 12
Time: 7:30-8:30pm
Place: CS104 (the large auditorium)

Additionally, Michael will arrive 30 minutes early and leave 30 minutes late for those with additional questions or issues.

Partial list of algorithms covered

extendible hashing	B-trees	KMP string search	Rabin-Karp
grep	Huffman compression	LZ and LZW compresseion	arithmetic compression
Graham scan	package wrapping	2D trees	sweep line/intersection
multiplication	FFT	RSA	Pollard's algorithm
DFS	BFS	topological sort	transitive closure
Kosaraju strong components	Tarjan strong components	Prim's MST	Kruskal's MST
Boruvka's MST	priority graph search	Dijkstra's SPT	Warshall/Floyd
network flow	bipartite matching	linear programming

Sample question

Give the result of alg X running on input Y
(we may ask other types of questions also; this is just one example)

The test will be similar in style to this year's midterm. The best preparation is to read the text in the course packets and attempt to work the easy exercises.