COS 226 Final Information, Spring 2018

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.

While this page is accurate, changes are still being made. Those changes will be listed in red.

Time and location:

Programming Exam Rules:

Written Exam Rules:

Office Hours for 4/28 - 5/1. No office hours from 5/2-5/6 (after the exams)

Sat 4/28 8:00-10:00 pm Friend 010 Yushan
Sun 4/29 3:00 -5:00 pm Lewis 122 Maia
Mon 4/30 2:00-4:00 pm 221 Nassau St Ibrahim
Mon 4/30 6:30-8:30 pm Friend 010 Tosin
Tue 5/1 12:30-2:30 pm Friend 010 Shayan
Tue 5/1 2:30-4:30 pm Friend 010 Charlie
Tues 5/1 4:30-6:30 pm Friend 010 Lauren
Tues 5/1 6:30-8:30 pm Friend 010 Nayana

(Optional) Practice Programming Exam Preparation

(Optional) Written Exam Preparation

Class meeting (design questions) April 25 in Friend 101.

Exam review session April 30 at 4:30pm in CS104.
Quizzera review

Material Covered

We have covered a large body of material this semester, but the exam can only contain 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 programming exam is cumulative but will not include string algorithms.

The written exam will stress material covered since the midterm, including the following components.

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

KdTrees Linear Probing Hashtables Separate Chaining Hashtables
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
RE to NFA R-way tries Ternary search tries
Key-indexed counting LSD radix sort MSD radix sort 3-way radix quicksort
Run-length coding Huffman coding LZW compression

Questions that show awareness of advanced topics that were covered in lecture are also fair game.