Syllabus and Schedule

Course Homepage

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  
    - 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)    

Author: Akshar Varma

Created: 2023-08-06 Sun 09:26