| Week # | Date | Topic | Topic Reading | Linked Files |
|---|---|---|---|---|
| 0 | Sep. 4 | Topic Sampler |
We tried two different multiplication algorithms, 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 | Sep. 9 | Some discussion about "what we do"; namely some basic thoughts on runtime analysis and correctness arguments | CLRS sections 2.1 and 2.2 and chapter 3. This reading will have a lot of technical stuff, but will help you get a solid grounding in these topics. | Scribe Notes |
| 2 | Sep. 11 | A deeper dive into asymptotic analysis. | The introduction of Erickson's book. It's a really good read and I honestly believe will help you think about a lot of things in this course. | |
| 3 | Sep. 18 | Brute Force Algorithms | Scribe Notes | |
| 4 | Sep. 23 | Introduction to Divide and Conquer | Section 4.4 of CLRS | Scribe Notes |
| 5 | Sep. 25 | Merge Sort and Faster Multiplication | Section 2.3 of CLRS and Chapter 1 of Erickson | |
| 6 | Sep. 30 | QuickSort and Partition | Sections 7.1 and 7.2 of CLRS | Scribe Notes |
| 7 | Oct. 2 | Fast Selection | Section 9.3 of CLRS | |
| 8 | Oct. 7 | Intro to Dynamic Programming | First half of chapter 3 of Erickson | Scribe Notes |
| 9 | Oct. 9 | Activity Selection, started Rod Cutting | Second half of chapter 3 of Erickson | Scribe Notes |
| 10 | Oct. 16 | Finished Rod Cutting, started Longest Increasing Subsequence | Section 14.1 of CLRS | |
| 11 | Oct. 21 | Finished Longest Increasing Subsequence | Section 14.3 of CLRS | |
| 12 | Oct. 23 | The 3 Problems / Interview Day | CLRS Chapter 14 | |
| 13 | Oct. 28 | Longest Common Subsequence | CLRS Chapter 14 | Scribe Notes |
| 14 | Oct. 30 | Longest Palindrome | Kleinberg and Tardos Chapter 6 | Scribe Notes |
| 15 | Nov. 4 | Subset Sum / Partition | Kleinberg and Tardos Chapter 6 | |
| 16 | Nov. 6 | Interview Day (Edit Distance) | Kleinberg and Tardos Chapter 6 | Scribe Notes |
| 17 | Nov. 11 | Started Reductions (Partition and Subset Sum) | ||
| 18 | Nov. 13 | Max Flow and the Ford-Fulkerson Algorithm | Kleinberg and Tardos Chapter 7 or CLRS Section 24 | |
| 19 | Nov. 18 | Introduction to P and NP (3Sat and SubsetSum) | Erickson Chapter 12 | |
| 20 | Nov. 20 | NP-Completeness (3Sat and Hamiltonian Cycle) | CLRS Section 34 | |
| 21 | Dec. 2 | Online Algorithms (Min-Weight Metric Matching) | CLRS Section 27 | |
| 22 | Dec. 4 | Dynamic Pricing for Set Cover | Their paper |