COS 226 Final Information, Spring 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:
- Wednesday, May 15th, 2–5 PM. Josh. CS 301
- Friday, May 17th, 12–5 PM. Nico and Stefan, Equad C320
- Friday, May 17th, 7–9 PM. Maia, CS 205
- Saturday, May 18th, 3–5 PM. Arvind, Sherrerd 308
- Saturday, May 18th, 5–7 PM. Dushyant, CS 003
- Sunday, May 19th, 3–5 PM. Jenny, CS 001A
- Sunday, May 19th, 7–9 PM. Ruth, CS 004
- Sunday, May 19th, 8–10 PM. Diego, CS 003
There will be a review session 1–3pm on Saturday, May 18th in Robertson 100. NEW: There will be a second review session 5–7pm on Saturday, May 18th. Since this was a bit last minute, we don't have a room reserved. We'll start by checking the small auditorium (CS 105) in the CS building, and we'll be clever enough to find a room as a team. Check Piazza for updates.
Josh's office hours on May 15th and May 18th will be problem solving sessions. Copies of old finals will be provided, and Josh will walk around answering questions that come up.
The final exam is 9am-noon on Monday, May 20th.
If you are in P01 or P02 or P03 (any Thursday precept), you will take the exam in room McCosh 46. If you are in any other precept (P04, P05, P05A, P06, P06A, P07, P08), you will take the exam in McCosh 10.

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, 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

key-indexed counting	LSD string sort	MSD string sort	3-way string quicksort
Depth-first search	Breadth-first search	Topological sort	Prim's algorithm
Kruskal's algorithm	Dijkstra's algorithm	Bellman-Ford algorithm	Ford-Fulkerson algorithm
Knuth-Morris-Pratt substring search	Boyer-Moore substring search	Rabin-Karp substring search	Kolmogorov complexity
RE to NFA	R-way tries	Ternary search tries	Reductions (no mathematically difficult ones, though)
Run-length coding	Huffman coding	LZW compression	Burrows-Wheeler

Questions that show awareness of advanced topics that were covered in lecture are also fair game (for example, NP-completeness and 3-satisfiability).