The final is open book, open notes.
Study the homework solutions and the midterm solutions. What topics do you need to work on?
Readings in the text book for all of the lecture topics are on the "lectures" Web page.
You can see any of the lectures on tape. Check the class Web page for instructions on how.
There will be a dynamic programming question and you will be asked to prove some problem is NP-hard.
You should understand the definition of NP-completeness, and why both parts are important.
The final will cover Dijkstra's shortest path algorithm, the Bellman-Ford algorithm, Kruskal's minimum spanning tree algorithm, and the UNION-FIND data structure.
Review all the dynamic programming algorithms we did: Longest common substring, matrix sequence multiplication, edit distance between two strings, maximum-weight independent set, longest increasing subsequence.
Review all NP-complete problems we have worked with: SAT, 3-CNF-SAT, Clique, Vertex Cover, Independednt Set, Longest Path, Hamiltonian Path, Hamiltonian Cycle, Traveling Salesman Problem.