15-451 Fall 2000 Schedule
TOPICS Date Chapters
-------------------------------------------------------------------------
Fundamentals
1. Course intro, algorithm examples 08/29 1, 2, 9.5
2. Math Foundations: asymptotics, recurrences 08/31 3, 5
Sorting and Order Statistics
3. Randomized quicksort, Probability intro 09/05 6.4
4. Linear-time Selection (rand and det) 09/07 6.5
5. Sorting Lower bounds (det and rand) 09/12
Data Structures
6. Balanced search trees: B-trees 09/14 4.3.3
7. Amortized Analysis 09/19
8. Balanced search trees: Splay trees 09/21
9. Radix sort, tries, and **QUIZ** 09/26
10. Hashing: Universal and Perfect 09/28 4.4
11. Hashing (contd) 10/03
Dynamic Programming
12. Dynamic Programming & memoizing 10/05 5.10,6.11
Graph Algorithms
13. Basic Graph Algorithms 10/10 7.1-7.8
14. Fibonacci heaps 10/12 4.3.2
15. **MIDTERM** 10/17
16. Graph Algs (contd) 10/19
17. Union-Find 10/24 4.5
18. Max Flow and Matchings 10/26 7.10,7.11
19. Max Flow (contd) 10/31
20. Linear Programming 11/02 10.3
Computational Complexity
21. NP-Completeness 11/07 11
22. NP-Completeness (contd) + **QUIZ** 11/09
Numerical Algorithms
23. Fast Fourier Transform 11/14 9.4,9.6
24. Crypto and number-theoretic algs 11/16 9.1-9.3
25. (contd) 11/21
Modern Topics
26. Zero-Knowledge proofs 11/28
27. Approximation Algorithms 11/30 11.5.2
28. On-line Algorithms 12/05
29. Machine learning algorithms 12/07
30. Summary 12/12
Final exam is Mon Dec 18 08:30a.m.-11:30a.m in PH 100.
Notes:
- Each quiz will be 1/2 hour long. The midterm will take the full
class period.