Fall, 2004 Computer Science 226 |
This document is intended to help you use your study time effectively. Please view it as a guide, not a contract. We have covered an enormous amount of material this semester, but the exam can only contain basic questions about a small fraction of it. When you study, you should focus on understanding basic issues, not memorizing details. For each algorithm, you should make sure that you understand how it works on typical input and then ask yourself some basic questions: Why do we care about this algorithm? How is it different from other algorithms for the same problem? When is it effective? Knowing the answer to those sorts of questions is the key to doing well on the exam.
There may be a question or two on sorting and searching: to prepare for these, you should understand correct answers for the midterm. There also may be a question or two on string processing and geometric algorithms: to prepare for these, you should study the lecture notes and assignments. Most of the exam will be about graph processing. You should study the lecture notes and assignments on these topics, too, but most of your preparation should involve reading the text, as outlined below.
17. Graph Properties and Types
Reading this entire chapter is a good way to be sure that you understand basic
concepts and terminology. You can check your understanding by working the easy
exercises.
18. Graph Search
This chapter goes into much more depth on the mechanics of search than we did
in lecture. It is critical that you understand DFS and basic DFS algorithms
(pages 87-97 and 105-112); BFS (Programs 18.7 and 18.8); and generalized
graph search (Program 18.9), but you may safely skim the detailed discussions
and skip section 18.4, 18.6, and 18.9
18.9.
19. Digraphs and DAGs
Your goal in this chapter is to understand Kosaraju's algorithm
(Program 19.10). To do so, you will need to read sections
19.1 and 19.2, understand Program 19.4, read section 19.6 through page 195,
read section 19.7, and read secton 19.8 through page 210. You may safely skim
or skip the rest of the chapter.
20. Minimum Spanning Trees
For this chapter, you need to know Prim's and Kruskal's algorithm, including
how and why they work. To do so, you certainly need to read sections 20.1,
20.3, and 20.4 and also relevant text in 20.2.
21. Shortest Paths
Your main focus in this chapter should be understanding Programs 21.1,
21.6, and 21.9 along with the perspective of section 21.8 on single-source
problems. You may
skip material on the all-pairs algorithms, DAGs, and Euclidean graphs.
You do not need to study section 21.6 in detail, but
you should understand the concept of reduction as covered in lecture.
22. Network Flow
You are responsible for sections 21.1, 21.2, and 21.4. This reading includes
a bit of material not covered in lecture, in particular some interesting
reductions to maxflow that tie together several concepts about graph
processing.
You can also check your understanding of the material by studying
old exams
but be warned that old courses might have covered different material and used
different policies for exams. Still, it is no secret that we draw upon old
exams for questions, and you might get lucky if we happen to choose a question
that you have studied (usually, we do change the data).