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 |