##
CPSC 411: Review for Exam 2

Fall 2008

*You may bring ***one** 8.5-by-11 inch sheet of paper with your own
notes on it to the exam. You may write on both sides.
Review the lectures and the reading from Oct 7 through Nov 13.
Here is a detailed list
of what was covered and will be fair game for the exam:

- graph algorithms (BFS, DFS, topological sort, strongly-connected
components)
- more graph algorithms (Prim's MST, Dijkstra's SSSP, Bellman-Ford SSSP)
- slides set 9
- Ch 23.2, Ch 24.1-24.3

- randomized algorithms (hiring problem, basic probability, randomly
permuting an array, randomized quicksort)
- slides set 10
- boardwork on analysis of randomized quicksort
- Ch 5.1-5.3, Appendix C.1-C.3

- NP-completeness (P, NP, polynomial reduction, NP-complete, TSP, HC,
SAT, 3SAT, VC, Clique, approximation algorithms, min VC approx alg,
TSP approx alg., triangle inequality)
- slides set 11
- Ch 34 (skip pp. 987-993 and 997-1002), Ch 35.1-2

Also review:

Quizzes 7-11 and their solutions (given in class).
Homeworks 4-7 and their solutions
8
The format of the exam will be some short answers and some
"work-out" problems.