Audio/video for lectures 20 and 21 are not available.
Lecture notes files.| SES # | TOPICS |
|---|
| 1 | Administrivia - Introduction - Analysis of Algorithms, Insertion Sort, Mergesort |
| 2 | Asymptotic Notation - Recurrences - Substitution, Master Method |
| 3 | Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication |
| 4 | Quicksort, Randomized Algorithms |
| 5 | Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort |
| 6 | Order Statistics, Median |
| 7 | Hashing, Hash Functions |
| 8 | Universal Hashing, Perfect Hashing |
| 9 | Relation of BSTs to Quicksort - Analysis of Random BST |
| 10 | Red-black Trees, Rotations, Insertions, Deletions |
| 11 | Augmenting Data Structures, Dynamic Order Statistics, Interval Trees |
| 12 | Skip Lists |
| 13 | Amortized Algorithms, Table Doubling, Potential Method |
| 14 | Competitive Analysis: Self-organizing Lists |
| 15 | Dynamic Programming, Longest Common Subsequence |
| 16 | Greedy Algorithms, Minimum Spanning Trees |
| 17 | Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search |
| 18 | Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints |
| 19 | Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson |
| 20 | Quiz 2 Review
Note: No audio or video is available for this session. |
| 21 | Ethics, Problem Solving (Mandatory Attendance)
Note: No audio or video is available for this session. |
| 22 | Advanced Topics |
| 23 | Advanced Topics (cont.) |
| 24 | Advanced Topics (cont.) |
| 25 | Advanced Topics (cont.) - Discussion of Follow-on Classes |