Instructor: Nadia Lafrenière
Course on Canvas: https://canvas.dartmouth.edu/courses/44288
Syllabus
| Date | Content |
| January 8 | Introduction to the analysis of algorithms |
| January 11 | First example: merge sort, optimal sorting algorithms |
| January 13 | Solving recurrences |
| January 15 | Divide-and-conquer algorithms, part 1 |
| January 18 | No class, MLK day |
| January 20 | Divide-and-conquer algorithms, part 2 (Master’s theorem, Strassen algorithm for matrix multiplication) |
| January 21 (x-hour) | The symbolic method, ordinary generating functions |
| January 22 | Labeled classes and exponential generating functions |
| January 25 | Lagrange inversion |
| January 27 | Averages and moments |
| January 29 | Asymptotic expansions, part 1 |
| February 1 | Asymptotic expansions, part 2 |
| February 3 | Compositions and partitions |
| February 5 | Student presentations |
| February 8 | Student presentations |
| February 10 | Student presentations |
| February 12 | Trees |
| February 15 | Trees for searching |
| February 17 | Q&A: The symbolic method |
| February 19 | Permutation statistics: Ascents, descents, runs |
| February 22 | Permutation statistics: Cycle lengths |
| February 24 | Permutation statistics: Increasing sequences |
| February 26 | Sorting: Bubble sort, Quicksort |
| March 1 | Randomized algorithms, Quicksort |
| March 3 | NP-completeness |
| March 5 | Student presentations |
| March 8 | Student presentations |
| March 10 | Student presentations |