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