Lect # Date Topic Topic Reading Linked Files
0 Feb. 5 Topic Sampler Chapter 0 of Erickson

We tried three multiplication algorithms (mult0, mult1, mult2), here were our experimental results.

We also noted that the 'runtime' of these two programs appear to be wildly different, despite computing the same thing.
1 Feb. 10 Introduction to Induction and Asymptotic Analysis Chapter 3 of CLRS
2 Feb. 12 Background cont., start of Greedy

Chapter 2 of CLRS

A little note here - CLRS uses something called loop invariants to show the correctness of Insertion Sort. If you read carefully, you will notice that their argument follows the exact same flow as ours from class.
3 Feb. 17

Greedy

  • Intro to Exchange Arguments
  • Activity Selection
  • Finishing Homeworks in Time

 First half of Erickson Chapter 4
4 Feb. 19

Greedy

  • Job Scheduling to Minimize Wait Time
  • Offline Caching

 Second half of Erickson Chapter 4
5 Feb. 24

Greedy

  • Stable Matching

 First two sections of CLRS chapter 15 The OG paper these results come from.
6 Mar. 1

Greedy

  • Wrap Up Stable Matching
  • Dijkstra's Algorithm

 Last two sections of CLRS chapter 15 Link to Zoom recording, Passcode: pw7E@Ckb
7 Mar. 3

Divide-And-Conquer

  • Karatsuba's Algorithm
  • Merge Sort
 CLRS Section 2.3, and CLRS sections 7.1 and 7.2 The OG paper of Karatsuba's algorithm. You may have difficulty reading it if you can't read Russian...
8 Mar. 5

Divide-And-Conquer

  • Quick Sort
  • Partition
  • first couple tries of Selection
 Erickson Chapter 1 first half
9 Mar. 10

Divide-And-Conquer

  • Review of QuickSort and Partition
  • Review of quadratic Selection
  • nlog n Selection
  • linear Selection
 CLRS Section 9.3 The OG paper of linear selection
10 Mar. 12

Divide-And-Conquer

  • Master Theorem
  • Binary Search on higher-dimensions
  • Review of Iterative stuff
 Erickson Chapter 1 second half
11 Mar. 17

Review Day

  • Review of Greedy
12 Mar. 19

Review Day

  • Review of D&C
13 Mar. 31

Dynamic Programming

  • The Fibonacci Program from day 1
  • Weighted Activity Selection
  • Rod-Cutting
 CLRS section 14.1
14 Apr. 2 Dynamic Programming Erickson up to section 3.2
15 Apr. 7 Dynamic Programming Erickson up to section 3.3 to 3.7
16 Apr. 9 Dynamic Programming
17 Apr. 14 Dynamic Programming
18 Apr. 16 Dynamic Programming
19 Apr. 21 Reductions
20 Apr. 23 Reductions
21 Apr. 28 Reductions
22 Apr. 30 P vs NP
23 May 4 Online Approximation
24 May 6 Online Approximation