Directory of all slides and notesNote: Slides/notes are usually
modified versions of those provided by the author of this book
(Levitin) or of the previous book I used (Goodrich). Also note that
most of the class is done on the board (not via slides), so slides are
sometimes not polished in terms of formatting.
-
Week 1:
Introductory analysis
slides; Web archive of good loop
invariants link.
- Week 2: BigOh, Brute
Force, Divide and Conquer slides.
- Week 3: RecurrenceTree
method, analysis and recurrence equation practice sheets: a newer one , and an older one. Closest pair notes.
- Week
4:Convex Hull problem, QuickHull
Animation, Convex
Hull notes.
- Week 5: Dynamic
Programming and Knapsack slides.
- Week 6: Graphs and
Floyd-Warshall slides. Also Decrease & Conquer,
DFS, BFS slides.
- Week 7: Midterm 2 review
sheet. Also here are some dynamic programming practice problems;
dynamicpractice1
(with solutions in solution
directory), and dynamicpractice2.
- Week 8: Greedy
Algorithm slides (including Prim's algorithm).
- Week 9: Transform
and conquer slides (including heapsort). Heapsort
animation. Strongly
connected components slides.
- Week 10: Lower bounds slides, Final Review sheet