**
What the exam covers:** The exam is cumulative. Any topic that
was covered in the lectures or in the assigned readings from the
book is "fair game". There are two exceptions, corresponding to
lectures on advanced topics that I promised not to test you on:

- the Fast Fourier Transform;
- the Miller-Rabin Randomized Primality Test.

The exam will give approximately equal coverage to all three phases of the course (i.e. the material on Prelim 1, the material on Prelim 2, and the material that was taught after Prelim 2). There may a slight bias toward testing material that was taught after the second prelim, but the bias (if any) will be mild enough that it shouldn't bias your studying. On the other hand, it might be advisable to allocate most of your studying to the most recently taught topics for the simple reason that if you already studied Chapters 4-8 for the first two prelims, then you've already spent more time studying those topics this spring than you spent studying Chapters 10, 11, 13, and online algorithms.

Generally speaking, the purpose of CS 482 is to learn
techniques for algorithm design and analysis, not to memorize
the details of specific algorithms and their analyses. Thus, in
studying for the final it's much more important to understand the
principles underlying the lectures, book chapters, etc., than to
understand the specifics of how the algorithms and proofs work.
One interesting corollary of this observation is that many of you
may actually find it more useful to study sections of the book
that **weren't** covered in lectures rather than those that the
lectures covered, simply because you'll be reading about fresh
applications of these algorithm design principles rather than
re-hashing stuff you already learned once before. Here are some
examples of instructive sections of the book that weren't taught in
lectures this spring:
**4.7, 5.3, 6.3, 7.11, 8.7, 11.2, 11.8, 13.4, 13.5**.
The solved exercises at the end of each chapter of the book
are another good source of material like this.

Just to be clear about this: I am *absolutely not* saying that the final exam will test material that is in these extra sections of the book, or that one of these sections teaches a technique that will be directly applicable on the final. What I'm saying is that if there's some topic (e.g. randomized algorithms) and you feel that the lectures and homeworks didn't give you a sufficiently clear impression of how to solve problems in this area --- or even if you have a clear impression but you just want to get some more practice --- then reading these extra sections of the book may be a useful study technique.

One more clarification: I'm also not saying you should
**ignore** the specifics of the algorithms and proofs that were
covered in CS 482 lectures this spring. For example, I think
each of the following 3 algorithms is important in itself, not
just as an illustration of general algorithm design principles:
*minimum spanning tree* (Kruskal's and Prim's algorithms),
*shortest paths with negative edge weights* (Bellman-Ford),
*sequence alignment* (section 6.6), *network flow* (Ford-Fulkerson,
preflow-push). For the network flow algorithms, I think it's
important to know the analysis of Ford-Fulkerson (residual
graph, augmenting paths, using the residual graph to identify
a minimum *s*-*t* cut) but for preflow-push I only expect you to
know the running time.

**Exam format:** Like the prelims, the final will contain a mix
of short-answer and long-answer questions. The time limit
puts me in a difficult position because 150 minutes is not
enough time to ask you a large number of long-answer
questions (i.e. those that require you to design an algorithm,
analyze its running time, and prove its correctness) of the
sort that were typically asked on the homework. Of
course there will be some questions like that (probably 3 of
them) but they will be accompanied by a significant share of
short-answer questions. Some types of short-answer
questions that I might ask are:

- multiple choice questions like Prelim 1, Problem 1A.
- very short answer (less than 1 sentence) questions like Prelim 1, Problem 1B.
- asking you to run an algorithm on a specific input instance of a problem, like Prelim 1, Problem 3A or Prelim 2, Problem 1A.
- asking you to give a counterexample to a statement, like Prelim 2, Problem 1B.
- showing you a computational problem you haven't seen before, and asking you to say (without proof) whether or not it's NP-Complete.
- showing you an incorrect algorithm for a problem, and asking you to find an input on which it gives the wrong answer.

**Suggested review problems:** You've already studied
for Prelims 1 and 2, and at the time I sent out some
suggestions for what problems to study. Here are
some suggestions from Chapters 10, 11, 13.

- problems 10.1, 10.5(a)
- problems 11.2(a), 11.3, 11.4, 11.9
- problems 13.3, 13.4, 13.6

**Monday evening review session:** Andrew Chan is
running a review session on Monday evening, from
7pm to 9pm, in Upson 315. I didn't consult Andrew
when choosing the list of review problems above,
and I don't expect him to cover them in his review
session, although he's certainly welcome to cover
them if people want that.