# 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;
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
- Diffie-Hellman Wiki:DH Key exchange
- Greatest Common Divisor (Euclid) Wiki:Euclidean Algorithm
GCD visualization for a=1071 b=462
- Fermat's little theorem, pseudoprimes Wiki:Fermat's little theorem, Wiki:pseudoprimes
- Miller-Rabin Primality test 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
- Segmented Least Squares [KT]: Chapter 6 slides
Jul/18 Tue Dynamic Programming: III
- Edit distance [JE]: Section 3.7; [DPV]: Section 6.3
- Memory efficient edit distance
Jul/19 Wed Dynamic Programming: IV
- RNA folding [KT]: Chapter 6 slides
- 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 ------------------------------ ------------------------------ Quiz 3
Week 4   PS:3 out; due Jul/30
Jul/24 Mon More about graphs
- Topological Ordering [KT]: Chapter 3 slides; [JE]: Section 6.3
- (Strongly) Connected Components [DPV]: Section 3.4; [JE]: Section 6.5, 6.6
- 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;
- Data structures: Union Find [JE]: Disjoint sets (way more than needed)
Jul/27 Thu Graphs continued
Jul/28 Fri ------------------------------ ------------------------------ Quiz 3
Week 5
Jul/31 Mon After greed comes more greed [Same chapters as before, any greedy works]
- Minimizing maximum lateness [KT]: Chapter 4 slides
- Graph Coloring Wiki:Greedy Coloring
- Independent Set [KT]: Independent Set demo, Vertex Cover demo
- Proof strategies [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
- Unweighted interval scheduling [KT]: Interval scheduling demo Other practice
- Graph Coloring Wiki:Greedy Coloring (Also OPTIONAL)
- Independent Set [KT]: Independent Set demo, Vertex Cover demo 1137, 931, 64, 70, 121
- Review proof strategies [JE]: Section 4.3 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)

Aug/18 Fri ------------------------------ ------------------------------
Aug/21–22 Mon–Tue Final Exam (Open Notes)

Created: 2023-08-06 Sun 09:26

Validate