CPSC 629: Final Exam Review
Fall 2003

The final exam will be cumulative, but there will be more emphasis on the material since the midterm. The exam will consist of some short answer questions and several "work-out" problems, similar in spirit to the homework, but not as involved (since time is limited). This review sheet is for the material since the midterm.

For example, for NP-completeness, I will either give you the reduction and ask you to verify that has the desired properties, or remind you of one we've seen before (lecture or reading or HW) and give you a hint as to how to modify it.

In general, you should review your notes from lecture, the readings, and the homeworks and their solutions. More details below on things to know:

Topics:

• Basic Graph Algorithms (Ch 22). BFS, DFS, topological sort, and SSC algorithms and their running times and why.

• Minimum Spanning Tree Algorithms (Ch 23). Kruskal and Prim's MST algorithms, their running times, and why, with various data structures.

• Single-Source Shortest Path Algorithms (Ch 24, skip Sec 4). Dijkstra's and Bellman-Ford algorithms, their running times, and why, with various data structures. General idea of correctness proofs.

• All-Pairs Shortest Path Algrithms (Ch 25). Dynamic-programming-based algorithms, especially Floyd-Warshall, and Johnson's algorithm, their running times, and why. General idea of correctness proofs.

• Max Flow (Ch 26, Secs 1-3). Definitions of flow network, flow, residual network, etc. Ford-Fulkerson and Edmonds-Karp algorithms, their running times and why. Application to maximum matching in a bipartite graph.

• NP-Completeness (Ch 34, skip circuit-sat). Definitions of P, NP, NP-complete, reductions, decision problem, optimization problem, etc. How to show a problem is NP-complete. Review reductions from lectures and homework.

• Approximation Algorithms (Ch 35, skip Secs 3-4). Definitions of approximation algorithm, fully polynomial time approximation scheme, approximation ratio and other ways of measuring performance. Approximation algorithms for VC, TSP (with triangle inequality), and subset-sum, including analyses of running times and ratios. Proof that general TSP does not have a polynomial time constant ratio approximation unless P = NP.

• String Matching (Ch 32, Secs 1-2). Problem definition. Naive algorithm and Rabin-Karp and their running times.

• Number-Theoretic Algorithms (Ch 31). Basic definitions. Euclid's algorithm and its running time, and why. Definition of pulbic-key cryptosystem. RSA algorithm (finding keys and applying them) and running time. Primality testing: naive algorithm and its running time; pseudo-primality algorithm, its time and performance.