It's time for a 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 test your proficiency with algorithm concepts and execution with no programmatic components.

• The exam will take the place and time of the usual lecture (see the course syllabus) and will last 90 minutes.

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, printed or hand-written) 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.

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.

Exam I will cover the topics in the first half of the class. These include:

• Algorithmic Paradigms: definitions, uses, and ability to apply: search, memoization/caching, heuristics, pruning, and dynamic programming.

• Classical Search Problems: definition of combinatorial search, uniform vs. non-uniform cost problems, use in search strategies, use of search trees to explore search spaces, steps of creating a search tree (expansion and generation).

• Uninformed Search: problem-solving specification (5 components), tree vs. graph search, breadth-first search, depth-first search, depth-limited search, iteratively-deepening depth-first search, best-first search, theoretical guarantees of each (completeness, optimality, space and time complexity) (+ability to perform by hand), differences in what happens at expansion vs. generation of nodes and how these compare between strategies.

• Informed Search: heuristics, heuristic design properties (admissibility, consistency, ensemble heuristics), heuristic estimate \(h(n)\) vs. true future cost \(h^*(n)\), A* search, evaluation functions and expansion priority (+ ability to perform by hand), differences in what happens at expansion vs. generation.

• Adversarial Search: canonical games and specifications, game-trees and their components, utility functions, mini-max search (and minimax values), alpha-beta pruning (+ ability to perform by hand).

• Dynamic Programming: definition and applicability, components (memoization structure, ordering, and recurrence), bottom-up vs. top-down, and ability to apply by hand on changemaker and LCS problems.

The examination format may include:

• Definitions and short answer questions

• Multiple choice

• Tracing the execution of various search strategies in classical search problems and on abstract search trees.

• Tracing the execution of minimax and α-β pruning algorithms in an abstract game tree.

• Tracing the execution of dynamic programming deployed to solve problems with optimal substructure.

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 (e.g., gridworld for search, tic-tac-toe root state for minimax, N and D for changemaker), perform individually, and then compare solutions.

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