COS 226 Final Information, Fall 2015
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
-
Final Exam Period: 7:30-10:30 PM on Friday, January 15. McCosh 50
-
Office Hours:
| DATE |
TIME |
ROOM |
PERSON |
| Sun 1/10 |
2:00-4:00 pm |
CS 003 |
Tom |
| Mon 1/11 | 1:00-3:00 pm |
CS 003 |
Nora |
| Tue 1/12 | 2:00-4:00 pm |
221 Nassau |
Guna |
| Wed 1/13 | 2:00-4:00 pm |
Sherrerd 3rd Floor |
Miles |
| Wed 1/13 | 4:00-5:00 pm |
CS 205 |
Maia |
| Thu 1/14 | 12:30-1:30 pm |
CS 205 |
Maia |
| Thu 1/14 | 2:00-4:00 pm |
CS 406 |
Szymon |
-
A design problem session will be held Tuesday January 12th from 6-8PM. The goal
is to focus on 5-6 design problems to discuss possible approaches.
Friend 101.
design session slides and solutions
-
An review session for the final exam will be held Wednesday January 13th from 5-7PM.
This session will cover all topics since midterm and topics from early in the
semester.
Friend 101.
Review Session Slides
Review Session solutions
Exam Format
- Covers all material through Tuesday 12/15/15.
- Includes associated readings and assignments(but no serious Java programming)
- Emphasizes post-midterm material.
- Honor code, 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–23.
- Algorithms in Java, 4th edition, Chapters 4–6.
- Exercises 12–22.
- Programming assignments 6–8.
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
| Depth-first search
| Breadth-first search
| Topological sort
| Prim's algorithm
|
| Kruskal's algorithm
| Dijkstra's algorithm
| Bellman-Ford algorithm
| Ford-Fulkerson algorithm
|
| Key-indexed counting
| LSD radix sort
| MSD radix sort
| 3-way radix quicksort
|
| Knuth-Morris-Pratt substring search
| Boyer-Moore substring search
| Rabin-Karp substring search
|
| RE to NFA
| R-way tries
| Ternary search tries
| Reductions
|
| 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).