COS 226 Final Information, Fall 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
-
Final exam office hours:
-
Kevin: Monday 1-2pm, Thursday 2-3pm, Friday 2-4pm.
-
Siyu: Friday 11-2pm.
-
Aman: Monday 2-3pm, Tuesday 2-4pm.
-
Yuri: Tuesday 1-2pm, Thursday 3-5pm.
-
There will be a review session 6:30-9pm on Thursday, January 20 in CS 104.
-
The final exam is at 9am-12noon on Saturday, January 22 in 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 11, 13–24.
- Algorithms in Java, 4th edition: Chapters 4–5
- Algorithms in C, 2nd edition: Chapters 24-27 (online).
- Exercises
- Programming assignments.
The lecture slides are the primary reference for lectures 16-17 and 23-24;
the text is the primary reference for lectures 11-15 and 18-22.
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 string sort
| MSD string sort
| 3-way string quicksort
|
Depth-first search
| Breadth-first search
| MST algorithms (Prim, Kruskal)
|
Topological sort
| Critical-path method (CPM)
| 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.