CS 341: What to know for the final exam
The final exam is on December 12 2016 from 7:30 to 10:00 PM in
PAC 1,2,3.
You can bring a 1-page "cheat sheet" with anything you want on it
(both sides). No other aids allowed. No calculators, computers, cell
phones, etc.
You are responsible for everything you had to know
for the midterm, plus:
all the material in lectures 13-24 available on the
course home page, as well as
the suggested readings in the textbook:
Section B.4 of CLR
Chapter 6 of CLR
Section 22.1 of CLR
Chapter 23 of CLR
Chapter 24 of CLR
Chapter 25 of CLR
Chapter 34 of CLR
You should know all the things you had to know for the midterm, together
with
- properties of logarithms and factorials
- analyzing algorithms
- probabilistic analysis of randomized algorithms (e.g., RANDOMIZE-SELECT)
- what is a lower bound on a problem; how to do lower bound proofs
- graphs: definitions, representation as a data structure (adjacency
matrix, adjacency list).
- minimum spanning tree: Kruskal's and Prim's algorithms.
- single-source shortest paths: Dijkstra's algorithm and the
Bellman-Ford algorithm. Negative-weight cycles.
- All-pairs shortest paths: the Floyd-Warshall algorithm.
- Solvability and unsolvability: proving problems unsolvable. Reductions.
- P, NP, co-NP, NP-complete: definitions. Proving problems NP-complete.
A solvable problem not solvable in polynomial time. Polynomial-time
reductions. NP-complete problems: CIRCUIT SAT, SAT, 3-CNF-SAT,
CLIQUE, VERTEX COVER, SUBSET SUM, HAM-CYCLE.
The best way to study for the final is to read the lecture notes and make
sure you understand them, and to do some of the exercises in the textbook
in the sections listed above. The emphasis on the exam will be on the
material in the second half of the course, but there will certainly be
questions about the first half material. The coverage on the exam
between 2nd half and 1st half is about 65% / 35%.