Syllabus and Schedule
Date | Day | Topic (links to PDF slides) | Reading | Problem Sets/Quizzes |
---|---|---|---|---|
Week 1 | ||||
Jul/03 | Mon | Administrivia | Homepage | PS:0 out; due Jul/06 |
Grading, Policies, Logistics | (Learn LaTeX; | |||
Overview | Test Gradescope; | |||
Prerequisite readings below: | Ungraded.) | |||
Prerequisites | [DPV]: Chapter 0; [JE]: Appendix I | |||
- Sets, relations, functions | [MMF]: Chapters 1, 3, 5–8, 11, 17. Appendix A | Quiz 0 | ||
- Exponentials and Logarithms | Separately linked chapters are Important! | (Self-diagnostic; | ||
- Proofs: Induction, Contradiction | [LLM]: Chapters 1,4,5 | Ungraded survey.) | ||
Jul/04 | Tue | (No classes) | PS:0 due | |
Jul/05 | Wed | Asymptotic Notation and Computability | [MMF]: Chapter 14, [DPV]: Chapter 0 | PS:1 out; due Jul/11 |
- \(O\), \(\Omega\), \(o\), \(\omega\), \(\theta\) | [KT]: Chapter 2 slides | (pre-reqs, asymptotics, | ||
- Computability | number theoretic) | |||
- Halting problem is undecidable | Wiki: Halting Problem | |||
Jul/06 | Thu | Number theoretic algorithms | ||
- (Modular) Arithmetic | Wiki:Modular Arithmetic (Congruence, Properties) | |||
- Fast exponentiation (binary) | Wiki:Exponentiaion | |||
- |
Wiki:DH Key exchange | |||
- Greatest Common Divisor (Euclid) | Wiki:Euclidean Algorithm | |||
GCD visualization for a=1071 b=462 | ||||
- |
Wiki:Fermat's little theorem, Wiki:pseudoprimes | |||
- |
Wiki: Miller-Rabin Primality Test | |||
Jul/07 | Fri | ------------------------------ | ------------------------------ | Quiz 1 |
Week 2 | ||||
Jul/10 | Mon | Recurrences and Master Theorem | [JE]: Appendix II (skip section 4 onwards) | |
- Guess and Prove: Induction | ||||
- Recurrence Trees | ||||
- Master Theorem Image, Video | Practice Problems [PDF] | |||
Jul/11 | Tue | Divide and Conquer: Introduction | [JE]: Chapter 1 Recursion (1.4 for mergesort) | Recitation 01, with solutions |
- Binary search | [KT]: Binary Search demo | |||
- Sorting: Mergesort | [KT]: Chapter 5 slides; [KT]: Mergesort demo | |||
- Sorting lower bound | [DPV]: Chapter 2 | |||
- Closest pair of points | [KT]: Chapter 5; | |||
Higher dimensions, Improved sparsity analysis | ||||
Jul/12 | Wed | Divide and Conquer: Order Statistics | [JE]: Chapter 1 Recursion | PS:1 due |
- Median of Medians | [DPV] Section 2.4 | |||
- Quicksort using MoM | [JE]: Section 1.8; [KT]: Quickselect demo | |||
Jul/13 | Thu | Dynamic Programming: I | Recitation 02, with solutions | |
- Fibonacci | [JE]: Chapter 3 | (Recurrences and | ||
- Abstract framework | above has very nice suggestions | Divide and Conquer) | ||
- Weighted Interval Scheduling | [KT]: Chapter 6 slides | |||
- Maximum Grid Path Sum | leetcode practice | |||
- Knapsack | [DPV]: Section 6.4; [KT]: Chapter 6 | |||
Jul/14 | Fri | ------------------------------ | ------------------------------ | PS:2 out; due Jul/22, Quiz 2 |
Week 3 | ||||
Jul/17 | Mon | Dynamic Programming: II | ||
- |
||||
Jul/18 | Tue | Dynamic Programming: III | ||
- |
||||
- |
||||
Jul/19 | Wed | Dynamic Programming: IV | ||
- |
||||
- Review of DP | ||||
Jul/20 | Thu | Graphs and basic traversals | ||
- Introduction | [KT]: Chapter 3 slides; [DPV]: Chapter 3, 4 | |||
- Data structures: Stacks, Queues | ||||
- Depth First Search (DFS) | [JE]: Chapter 6 | |||
- Breadth First Search (BFS) | [JE]: Chapter 5 | |||
Jul/21 | Fri | ------------------------------ | ------------------------------ | |
Week 4 | PS:3 out; due Jul/30 | |||
Jul/24 | Mon | More about graphs | ||
- Topological Ordering | [KT]: Chapter 3 slides; [JE]: Section 6.3 | |||
- |
||||
- DAGs | [KT]: Chapter 3 slides | |||
- Bipartite Graphs | [KT]: Chapter 3 slides | |||
Jul/25 | Tue | Shortest Paths on Graphs | [JE]: Chapter 8; [DPV]: Chapter 4 | |
- Dijkstra's algorithm | [KT]: Dijkstra demo | |||
- Data structures: Priority Queues | [DPV]: Section 4.5 | |||
- Bellman-Ford | [JE]: Section 9.5 | |||
Jul/26 | Wed | Minimum Spanning Trees | [JE]: Chapter 7; [KT]: Chapter 4 slides | |
- Prim's algorithm | [KT]: demo for MSTs | |||
- Kruskal's algorithm | [DPV]: Section 5.1; | |||
- |
||||
Jul/27 | Thu | Graphs continued | ||
Jul/28 | Fri | ------------------------------ | ------------------------------ | Quiz 3 |
Week 5 | ||||
Jul/31 | Mon | [Same chapters as before, any greedy works] | ||
- |
[KT]: Chapter 4 slides | |||
- |
Wiki:Greedy Coloring | |||
- |
[KT]: Independent Set demo, Vertex Cover demo | |||
- |
[JE]: Section 4.3 | |||
- Review (finalize instructor notes) | ||||
Aug/01 | Tue | Midterm | ||
- Open Notes: Printed notes allowed | ||||
Aug/02 | Wed | Midterm solution review | ||
- Start greedy Proof strategies | [JE]: Section 4.3 | |||
Aug/03 | Thu | Lots of Greed | [JE]: Chapter 4, [KT]: Interval partitioning demo | |
- Making change | [KT]: Chapter 4 slides | OPTIONAL greedy practice | ||
- Fractional Knapsack | 2160, 2357, 1974 | |||
- |
Other practice | |||
- Graph Coloring | Wiki:Greedy Coloring | (Also OPTIONAL) | ||
- |
1137, 931, 64, 70, 121 | |||
- |
1143, 1027, 300, 518 | |||
Aug/04 | Fri | ------------------------------ | ------------------------------ | 392, 643, 1732, 2542 |
23, 372, | ||||
Week 6 | ||||
Aug/07 | Mon | Network Flows | [JE]: Chapter 10; [KT]: Chapter 7 slides | |
- Max Cut-Min Flow | [JE]: Section 10.1–10.3 | PS:4 out; due Aug/13 | ||
- Disjoint Paths/Menger's Theorem | [KT]: Chapter 7 slides | (Network flow, LP) | ||
- Bipartite Matching/Hall's Theorem | [DPV]: Section 7.3; [KT]: Chapter 7 slides | |||
Aug/08 | Tue | Network Flow Applications | [KT]: Chapter 7 slides; [JE]: Chapter 11 | |
- Applications | [KT]: Chapter 7 slides | |||
\(\longrightarrow\) Survey design | (all these examples | |||
\(\longrightarrow\) Airline scheduling | are taken from | |||
\(\longrightarrow\) Project selection | the slides above) | |||
\(\longrightarrow\) Baseball elimination | ||||
Aug/09 | Wed | Linear Programming | [DPV]: Chapter 7; [KT]: LP I slides | |
- Reducing problems to LPs | ||||
- Duality | [KT]: LP II slides | |||
- Maximum flow and minimum cut | ||||
- Graph Coloring and Independent Set | ||||
Aug/10 | Thu | Applications of LPs | [KT]: LP II slides; [DPV]: Chapter 7 | |
- More applications | ||||
- (Maybe) Using a library | ||||
Aug/11 | Fri | ------------------------------ | ------------------------------ | Quiz 4 |
Week 7 | ||||
Aug/14 | Mon | Review recursion | ||
Aug/15 | Tue | Review graphs, flows, LP | ||
Aug/16 | Wed | Final Exam Review | ||
- reviewing practice exam | ||||
- finalize instructor notes | ||||
Aug/17 | Thu | Final exam (3 hours) | ||
------------------------------ | ------------------------------ | |||