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