COS 226 Final Information, Spring 2016
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.
Time and location:
- The final exam is on Thursday May 19th from 9AM-12PM.
- The room is either McCosh Hall 46 McCosh Hall 50, depending on your precept.
- McCosh Hall 46: Friday Precepts P06, P07, P07A.
- McCosh Hall 50: Thursday Precepts P01, P02, P02A, P03, P03A, P04, P05 and P99(flipped).
Failure to go to the right room can result in a serious deduction on the exam.
Final exams can be rescheduled only by the Registrar.
Rules:
-
In-class exams are governed by the Undergraduate Honor System.
- Closed book, closed note.
- You may bring one 8.5-by-11 sheet (two sides) with notes in your own
handwriting to the exam.
- Computers, calculators, and electronic communication devices are forbidden.
Headphones attached to audio devices are also prohibited.
- Sit one one seat apart from other students and avoid sitting near
students with whom you've studied.
- Bring a pencil (with eraser) and write darkly and legibly.
help sessions
- Monday May 16th, 4:30-6:30pm. Course Review Session in Friend 101.
- Tuesday May 17th, 4:30-6:30pm. Special Design Review Session in Friend 101.
Office Hours
- Guna: Monday 5/2 (1:00-3:00 PM), Wednesday 5/18(12-2PM) , - 221 Nassau
- Miles: Monday 5/2 (4-6 PM), Wednesday 5/18 (2-4 PM) - Sherrod 3rd Floor Common Area
- Marc: Monday 5/2 (6-8 PM), 5/16 (9:30-11:30AM) - CS 001B
- Maia: Tuesday 5/3, 5/17, 12:30-2:30 PM- CS 205
- Harry: Tuesday 5/3, 5/17, 3-5 PM- CS 241
- Shivam: Tuesday 5/3, Tues 5/17, 5-7 PM- Sherrod 3rd Floor Common Area
- Arvind: Wednesday 5/4 (2-4 PM), Wed 5/18 (4-6 pm) - Sherrod 308
- Ming-Yee: Saturday 5/14 , 4-6 PM- Lewis 121
- Sergiy: Sunday 5/15 , 4-6 PM- Lewis 121
(Optional) Design Problem Review Session
We will be hosting an optional problem-solving session on Tuesday May 17th from 4;30-6;30 PM in Friend 101.
We will discuss general strategies for handling design questions.
We will also discuss specific design questions from past exams and
entertain questions from students.
You are welcome to come and go, as your schedule permits.
(Optional) Final Exam Review Session
We will have an optional final exam review session Monday May 16th from 4:30-6:30 PM in Friend 101.
A session to review basic ideas from the course.
We will present a summary of the material, discuss problem-solving strategies,
and solve some old exam problems.
We are also happy to answer specific questions that you have.
You are welcome to come and go, as your schedule permits.
Handout
Solution
If you have questions about this handout, please click here to make notes by annotating in salon.
Material Covered
We have covered a large body 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).