CS420 Introduction to Analysis of Algorithms
| Week | Dates | Topics | Material | Due |
|---|---|---|---|---|
| 1 | 8/20-8/24 | Asymptotic analysis | pp. 5-6, Ch. 2, pp. 43-56, Asymptotic analysis (big O) | |
| 2 | 8/27-8/31 | Asymptotics, Recurrences | Section 4, Recurrences | |
| 3 | 9/3-9/7 | Recurrences from algorithms, master theorem | Chapter 4, Section 33.4 Recurrences | |
| 4 | 9/3-9/7 | Strassen's algorithm, closest pair, sorting networks | Chapter 4, Section 33.4, handout on sorting networks | |
| 5 | 9/10-9/14 | Strassen's algorithm, closest pair, sorting networks | Chapter 4, Section 33.4, handout on sorting networks | |
| 6 | 9/17-9/21 | Rules of probability; examples; hiring problem | 5.1, 5.2, 5.3 | |
| 7 | 9/24-9/28 | Randomized algorithms and their analysis; Quicksort | 5.1, 5.2, 5.3, Chapter 7 | |
| 8 | 10/1-10/5 | Review of principles of counting; | ||
| 9 | 10/1-10/5 | Review of principles of counting; lower bounds for sorting, reductions | 8.1 | |
| 10 | 10/8-10/12 | Selection; randomized selection | 9.1, 9.2 | |
| 11 | 10/15-10/19 | Worst-case bounds for order statistics | 9.3 | |
| 12 | 10/22-10/26 | Review, midterm, randomized search trees | Handout on treaps | Midterm 10/24 |
| 13 | 10/29-11/2 | Randomized search trees; analysis of randomized hashing | Handout on treaps; 11.1-11.2 | |
| 14 | 11/5-11/9 | Amortized analysis | Chapter 17; handout on splay trees | |
| 15 | 11/12-11/16 | Amortized analysis, advanced data structures | Chapter 17; handout on splay trees; handout on binomial heaps | |
| 11/19-11/23 | Fall break | |||
| 16 | 11/26-11/29 | Binomial heaps, leftist heaps, simulating array list with binary trees | ||
| 17 | 12/3-12/7 | Review 12/3; review for final 12/7 | Exam 12/5 |
Final exam: December 10, 7:30-9:30 a.m. (Sorry about the early hour; I don't schedule them.)