COS 226 Final Information, Spring 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.

Time and location:

The final exam is on Saturday, March 16 from 9-12noon.
The room is either McCosh 28 or McCosh 50, depending on your last name.

McCosh 28: Last name begins with A–F.
McCosh 50: Last name begins with G–Z.

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.

Office Hours/help sessions

Office hours (under construction).
Thursday, May 7, 3-4pm. Kevin Wayne in CS 207.
Tuesday, May 12, 2-4pm. Swati Roy in Nassau 221.
Tuesday, May 12, 6-8pm. Josh Wetzel in Icahn 253.
Wednesday, May 13, 2:00-3:00 pm. Andy Guna in Naussau 221.
Wednesday May 13, 6:30-9:30pm. Design problem solving session in COS 104.
Thursday, May 14, 2-4pm. Shivam Agarwal in CS 302.
Thursday May 14, 6:30-8:30pm. Review session in Friend 101.
Friday, May 15, 2-4pm. Robert MacDavid in CS 302.
Friday, May 15, 4-6pm. Josh Wetzel in Icahn 253.
Friday, May 15, 6-8pm. Ryan Beckett in CS 242.

Design Problem Solving Session

We will be hosting an optional problem-solving session from from 6:30-9:30pm on Wednesday, May 13 in COS 104. 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.

Final Exam Review Session

We will have an optional final exam review session from 6:30-8:30pm on Thursday, May 14 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.
download handout
handout annotated
note: not all slides are annotated. Post of Piazza if you have questions or email: guna@cs.princeton.edu

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).