COS 226 Final Information, Fall 2013
This document is intended to help you use your study time effectively. Please
view it as a guide, not a contract.
You may also view the exam archive to study old questions.
Final Exam Schedule

Office Hours (Josh's hours TBA, depending on when review session happens):
DATE 
TIME 
ROOM 
PERSON 
Wed 1/15 
12:303:30 pm 
CS 004 
Ruth 
Thurs 1/16  7:008:00 pm 
Outside CS 406 
Tengyu 
Fri 1/17  12:004:00 pm 
Outside CS 306 
Debbie 
Sun 1/19  2:005:00 pm 
CS 312 
Josh 
Mon 1/20  10:301:30 pm 
CS 313 
Katie 
Mon 1/20  1:304:30 pm 
CS 324 
Bob 
Mon 1/20  7:009:00 pm 
CS 406 
Tengyu 
Tue 1/21  9:00am12:00 pm 
ACE 34 (in EQuad) 
Guna 
There will be a review session TBA.
The final exam is from 1:30 to 4:30 pm on Tuesday, Jan 21st in McCosh 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, and cell phones).
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?
The exam will stress material covered since the midterm,
including the following components.
 Lectures 13–24.
 Algorithms in Java, 4th edition, Chapters 4–6.
 Exercises 13–23.
 Programming assignments 5–9.
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
keyindexed counting
 LSD string sort
 MSD string sort

Depthfirst search
 Breadthfirst search
 Topological sort
 Prim's algorithm
 Kosaraju's algorithm

Kruskal's algorithm
 Dijkstra's algorithm
 BellmanFord algorithm
 FordFulkerson algorithm

KnuthMorrisPratt substring search
 BoyerMoore substring search
 RabinKarp substring search
 Kolmogorov complexity 
RE to NFA
 Rway tries
 Ternary search tries
 Reductions (no mathematically difficult ones, though)

Runlength coding
 Huffman coding
 LZW compression
 KdTrees

Questions that show awareness of advanced topics that were covered in lecture
are also fair game (for example, NPcompleteness and 3satisfiability).
See the study ugide for a more thorough list of topics.