COS 226 Final Information, Spring 2014


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

  • There will be a review session TBA.

  • The final exam is from 1:30 to 4:30 pm on Wednesday, May 21st in McDonnell Hall A01 and McDonnell Hall A02. Students in Thursday precepts (P01, P02, P03) will take the exam in A01; students in Friday precepts will take the exam in A02.

    Exam Format


    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.

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