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.