Information about the CS 482 Final

Date and time: The exam is happening at 7pm on Wednesday, May 14, in Uris Hall Auditorium. It will be a two-and-a-half hour (150 minute) timed exam. You only need to bring a pen or pencil; paper will be provided.

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 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:

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.

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.