It's time for your FINAL computing exam wooo! View this not as an intimidating obstacle to be overcome, but a chance at reflection to see how much you've learned and where your gaps of knowledge may be.

Here's how this is going to go:

• The "exam" will be entirely conceptual / procedural to test your understanding of the material.

• The exam will take place in our typical classroom and will last only 90 minutes; see the final exam schedule for the time and day:

  LMU Final Exam Schedule

• The exam is non-cumulative and will only quiz you on the material after the midterm. See topics of exam below.

• The exam is CLOSED note and CLOSED computer. You may NOT collaborate with peers or any other person during the duration of the exam.

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

Grading

• 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 be by design.

• The exam does not have a forced curve (i.e., that only some set number of people can receive A's, B's, etc.), but it WILL have a difficulty adjustment (upward bonus) if it was too hard.

• Remember the class' exam policy: your worse exam counts for half as much as the other. If your midterm grade wasn't where you wanted it to be, here's your chance to catch up!

• The last question on the exam will always be a bonus to illustrate a pun on this section's material; come prepared with an idea, those are easy points.

Remember: The final exam is NOT cumulative!

The final exam will cover the topics in the second half of the class. These include:

• 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 ONLY the edit distance problems.

• Bloom Filters: definition, purpose, strengths, weaknesses, operations (including possible set operations), false positives and likelihoods thereof.

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

• Constraint Satisfaction Problems (CSPs): formalizations (variables, domains, constraints), distinctions from Classical Search, semantics of prototypical example problems (N-Queens, Map-Coloring, Numerical, Scheduling).

• Backtracking: semantics and relation to depth-first search, runtime complexity, generation of recursion tree, node-consistency, arc-consistency, filtering, forward-checking, constraint-propagation (AC-3), order heuristics.

• Tree Structured CSPs: constraint graphs vs. constraint trees, directed arc consistency (use in solving tree-structured CSPs), cutset conditioning (for nearly-tree structured CSPs), performance improvements over backtracking.

• Iterative Algorithms: local search, min-conflict heuristic, hill-climbing (including notions of local vs global maxima + upward, downward, and sideways moves), simulated annealing, and genetic algorithms (including notions of fitness, selection mechanics, recombination, mutation).

What will NOT be on the exam:

• Any Python programming questions

• Any material on the midterm's set of topics

Exams in this class are most like the classwork exercises!

The examination format may include:

• Definitions and short answer questions

• Multiple choice

• Tracing the execution of dynamic programming problems.

• Tracing the execution of Bloom filter operations and Huffman compression.

• Tracing the execution of backtracking and its improvements / alternatives (like DAC, local search).

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 paradigms we haven't covered in class, you might be expected to apply the paradigms 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. Complete suggested extra exercises in the course notes that we did not see in class.

3. Form a study group, come up with an example problem, perform individually, and then compare solutions.

4. Study any available classwork solutions and correct any bugs in your homework based on the grading tests.

5. [Optional] Read the relevant textbook chapters outlined in the Syllabus.