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
10 Oct. 19 (Monday) Divide and Conquer
11 Oct. 21 (Wednesday) Divide and Conquer
Midterm 2 — Thu, Oct. 22, 6:30–10:00 PM (evening, proctored, location TBD). Covers: Divide and Conquer.
12 Oct. 26 (Monday) Dynamic Programming
13 Oct. 28 (Wednesday) Dynamic Programming
14 Nov. 2 (Monday) Dynamic Programming
15 Nov. 4 (Wednesday) Dynamic Programming
16 Nov. 9 (Monday) Dynamic Programming
17 Nov. 11 (Wednesday) Dynamic Programming
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
19 Nov. 18 (Wednesday) Reductions and P vs NP
20 Nov. 30 (Monday) Reductions and P vs NP
21 Dec. 2 (Wednesday) Reductions and P vs NP
22 Dec. 7 (Monday) Open / TBD
23 Dec. 9 (Wednesday) Open / TBD
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.