COS 226 Final Information, Spring 2011
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 15, 16  office hours

There will be a review session at 35pm on Sunday, May 15 in Friend 006

The final exam is at 7:30pm on Monday, May 16, McCosh Hall 10
Exam Format
 Closed book, closed note.
 You may bring one 8.5by11 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 1224.
 Algorithms in Java, 4th edition
 Exercises
 Programming assignments.
The midterm itself is fair game (did you take the time to understand
questions that you missed on that exam?).
Also, 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
 3way string quicksort

Depthfirst search
 Breadthfirst search
 MST algorithms (Prim, Kruskal)

Topological sort
 CPM/Arbitrage
 Shortest paths (Dijkstra)
 Negative weights (BellmanFord)

KnuthMorrisPratt
 BoyerMoore
 RabinKarp
 Strong components (Kosaraju)

RE to NFA
 Rway tries
 Ternary search tries
 Maxflow

Runlength encoding
 Huffman coding
 LZW compression
 BurrowsWheeler

FordFulkerson
 Linear programming
 Reductions
 Combinatorial search

Questions that show awareness of advanced topics that were covered in lecture
are also fair game. Examples: NPcompleteness, satisfiability, independent set.