Lect # Date Topic Topic Reading Scribe Duty
0 Sep. 9 (Wednesday) Topic Sampler Chapter 0 of Erickson
1 Sep. 14 (Monday)
Introduction
  • Big O Notation
  • Induction
Secion 2.1 of CLRS and First half of Chapter 3 of CLRS Stephen Owusu Badu and Simon Lartey
2 Sep. 16 (Wednesday)
Introduction
  • Using Induction to show correctness of algorithms
  • How to show best case and worst case runtimes
Greedy
  • We gave the basic structure of what an exchange argument looks like
Second half of Chapter 3 of CLRS Eric Hernandez and Henry Olson
3 Sep. 21 (Monday)
Greedy
  • Exchange Arguments
  • Maximal Interval Selection
  • Scheduling Homework Assignments
First half of Erickson Chapter 4 (up to stable matching) Svita Kiran and Kamalani Enomoto
4 Sep. 23 (Wednesday)
Greedy
  • Scheduling Homework Assignments to minimize maximal lateness and average completion time
  • Minimum Spanning Trees
First two sections of CLRS chapter 15 Azeem Gbolahan and Jack Dai
5 Sep. 28 (Monday)
Greedy
  • Stable Marriage Problem
Second half of Erickson Chapter 4 and The OG paper these results come from. Frankly, I think section 6, the conclusive section (one page in length), is the most interesting part of this paper. But the final paragraph makes me want to vomit a bit. Francis O'Hara Aidoo
6 Sep. 30 (Wednesday)
Greedy
  • Review Day
Yilin Pan
Midterm 1 — Thu, Oct. 1, 6:30–10:00 PM (evening, proctored, location TBD). Covers: Introduction + Greedy.
7 Oct. 5 (Monday)
Divide and Conquer
  • Karatsuba's Algorithm
Erickson Chapter 1, through section 1.3 Zoe Ahmiegbe and Tenzin Thinley
8 Oct. 7 (Wednesday)
Divide and Conquer
  • A little history on integer multiplication
  • MergeSort
  • Motivation of Quicksort
Section 1.4 of Erickson, section 2.3 of CLRS, and section 4.4 of CLRS Quinn Nguyen and Daniel Gil
9 Oct. 14 (Wednesday)
Divide and Conquer
  • Fast (Linear) Selection
  • MSCA
Obviously CLRS isn't always the best, but in this case its chapter on Selection is actually exceptional, and the drawings are nice. If CLRS just isn't your thing, Erickson also has a good section on it (1.8) Gent Maksutaj
10 Oct. 19 (Monday)
Divide and Conquer
  • Master Theorem
CLRS section 4.5 David Solano and Bryn Kerslake
11 Oct. 21 (Wednesday)
Divide and Conquer
Jack Reddy
Midterm 2 — Thu, Oct. 22, 6:30–10:00 PM (evening, proctored, location TBD). Covers: Divide and Conquer.
12 Oct. 26 (Monday)
Dynamic Programming
  • Maximum Weight Independent Set
  • Rod Cutting
CLRS section 14.1 Jacob Choi
13 Oct. 28 (Wednesday)
Dynamic Programming
  • Maximum Weight Interval Selection
  • Subset Sum
Erickson up to section 3.2 Lukas Gramss and Nick Berney
14 Nov. 2 (Monday)
Dynamic Programming
  • Longest Increasing Subsequence
Erickson sections 3.3-3.7 Papa Yaw Owusu
15 Nov. 4 (Wednesday)
Dynamic Programming
  • Palindrome
  • Longest Common Subsequence
Erickson 3.10 and CLRS Section 14.4 Daniel Gil and Quinn Nguyen
16 Nov. 9 (Monday)
Dynamic Programming
  • Maximal Value Independent Set (on Trees and Graphs)
  • Traveling Salesman
CLRS Section 14.5 Christina Long
17 Nov. 11 (Wednesday) Dynamic Programming Allison Rodriguez
Midterm 3 — Thu, Nov. 12, 6:30–10:00 PM (evening, proctored, location TBD). Covers: Dynamic Programming.
18 Nov. 16 (Monday)
Reductions and P vs NP
  • Network Flow and the Ford-Fulkerson Algorithm
  • Bipartite Matching
Chapter 24 of CLRS Glory Mahenge
19 Nov. 18 (Wednesday) Reductions and P vs NP Erickson Chapter 11
20 Nov. 30 (Monday) Reductions and P vs NP Erickson Chapter 12
21 Dec. 2 (Wednesday) Reductions and P vs NP CLRS Chapter 34
22 Dec. 7 (Monday) TBD
23 Dec. 9 (Wednesday) Review
Midterm 4 — Thu, Dec. 10, 6:30–10:00 PM (evening, proctored, location TBD). Covers: Reductions and P vs. NP.

Links to lecture code, papers, and other in-class materials will be added to this table as we go.