The exam will take the place, time, and duration of the usual lecture (see the course syllabus).

The exam is CLOSED note and CLOSED computer.

You are allowed to bring ONE 8.5" x 11" (double sided, printed is fine) cheat sheet with any information you'd like with you for consultation into the exam.

The exam may feel long, but that's OK! Take your time, a deep breath or two, and don't worry if you don't finish everything -- it will be likely that your classmates do not either, which will likely be by design.

This exam will cover the conceptual topics in the second ~5 weeks. These include:

• Comparing Algorithmic Paradigms: search vs. dynamic programming (including comparisons of depth-first tree search and depth-first recursion), memoization structures in each, space and time complexities of each.

• Dynamic Programming: purpose and benefits, applicability / optimal substructure of problems, tabular memoization and relation to subproblems.

• Bottom-up vs. Top-Down Dynamic Programming: definition, strengths, and weaknesses of each, algorithms for completing and reading solution from the memoization table, applications to Changemaker and Longest Common Subsequence (LCS) problems.

• Compression: purpose and applications, character encoding, compression vs. decompression, lossy vs. lossless compression algorithms, prefix-free codes.

• Huffman Coding: purpose, what it produces, Huffman Tries and finding encoding map from some text corpus, compressing a corpus with the encoding map, decompressing a bitstring with a Huffman Trie, methods of encoding and decoding a bitstring representation of a Huffman Trie.

What will NOT be on the exam:

• Search-tree representations of recursion in dynamic programming (these were to build intuition).

The examination format may include:

• Definitions and short answer questions

• Multiple choice

• Tracing the execution of dynamic programming in Changemaker and LCS problems.

• Tracing the execution of Huffman Coding compression, decompression, and encoding of Huffman Trie.

• Light Java-implementation questions related to any of the above. You should be comfortable with basic recursion.

Be prepared to answer some questions similar to those on the assignments and in-class exercises.

Furthermore, although I won't ask you anything about mechanics we haven't covered in class, you might be expected to apply the mechanics we've learned about in a way that we didn't see in class. If you thoroughly understand the material, there should be no surprises, but still challenges.

Here is my general suggestion for preparation order:

1. Re-read my course notes, re-doing the exercises if you aren't clear on any of them. Importantly: try to answer each "question" box yourself before revealing its answer.

2. Read the relevant textbook chapters outlined in the Syllabus.

3. In groups, create some variants of the classwork exercises, complete them independently, then regroup to see if your answers agree.

4. Study any available classwork and homework solutions.