CMU 15-451/651: Algorithm Design and Analysis, Fall 2022: Schedule

Schedule

Please keep in mind that this is preliminary and may change.

PDF Schedule (last updated Aug 23 2022)

Week 1

Tue 30-Aug	Lecture 1: Linear-time Selection	[notes] [slides]
	Homework 1 released	[homework 1]
Thu 01-Sep	Lecture 2: Concrete models and tight upper/lower bounds	[notes] [slides]
Fri 02-Sep	Recitation 1: Recurrences and Lower Bounds	[recitation 1] [solutions]

Week 2

Tue 06-Sep	Lecture 3: Amortized Analysis*	[notes] [slides]
Wed 07-Sep	Homework 1 due	[solutions]
Thu 08-Sep	Lecture 4: Splay Trees^†	[notes] [slides]
	Homework 2 released	[homework 2]
Fri 9-Sep	Recitation 2: Amortized Analysis and Splay Trees	[recitation 2] [solutions]

*Lecture recording failed, so I re-recorded it in my office, sorry
^†Lecture recording failed again. Link is to last year's lecture

Week 3

Tue 13-Sep	Lecture 5: Hashing I: Universal and Perfect Hashing	[notes] [slides]
Wed 14-Sep	Homework 2 due	[solutions]
Thu 15-Sep	Lecture 6: Hashing II: Streaming Algorithms	[notes] [slides]
	Homework 3 released	[homework 3]
Fri 16-Sep	Recitation 3: Hashing and Streaming	[recitation 3] [solutions]

Week 4

Tue 20-Sep	Lecture 7: Hashing III: Fingerprinting	[notes] [slides]
Wed 21-Sep	Homework 3 orals	[solutions]
Thu 22-Sep	Lecture 8: Range Query Data Structures	[notes] [slides]
	Homework 3 orals
Fri 23-Sep	Recitation 4: Fingerprinting and SegTrees	[recitation 4] [solutions]
	Homework 3 orals
Sat 24-Sep	Midterm I Review Session

Week 5

Tue 27-Sep	Midterm I
Thu 29-Sep	Lecture 9: Dynamic Programming I	[notes]
	Homework 4 released	[homework 4]
Fri 30-Sep	Recitation 5: Dynamic Programming	[recitation 5] [solutions]

Week 6

Tue 04-Oct	Lecture 10: Dynamic Programming II	[notes] [slides]
Wed 05-Oct	Homework 4 due	[solutions]
Thu 06-Oct	Lecture 11: Network Flows I: Flows, Cuts, and Matchings	[notes] [slides]
	Homework 5 released	[homework 5]
Fri 07-Oct	Recitation 6: Dynamic Programming and Flows	[recitation 6] [solutions]

Week 7

Tue 11-Oct	Lecture 12: Network Flows II: Polynomial-Time Algorithms	[notes] [slides]
Wed 12-Oct	Homework 5 due	[solutions]
Thu 13-Oct	Lecture 13: Network Flows III: Minimum Cost Flows	[notes] [slides]
Fri 14-Oct	Recitation 7: More Flows	[recitation 7] [solutions]

Fall Break

Mon 17-Oct	Fall Break begins
Fri 21-Oct	Fall Break ends

Week 8

Tue 25-Oct	Lecture 14: Game Theory	[notes] [slides]
	Homework 6 released	[homework 6]
Thu 27-Oct	Lecture 15: Linear Programming I: Basics^†	[notes] [slides]
Fri 28-Oct	Tartan Community Day (No Classes)

^†Microphone dies half way. See last year's video as an alternative.

Week 9

Tue 01-Nov	Lecture 16: Linear Programming II: Algorithms (Seidel's 2D Algorithm)	[notes] [slides]
Wed 02-Nov	Homework 6 orals	[solutions]
Thu 03-Nov	Lecture 17: Linear Programming III: Duality	[notes] [slides]
	Homework 6 orals
Fri 04-Nov	Recitation 8: Game Theory and Linear Programming	[recitation 8] [solutions] (kunal's notes)
	Homework 6 orals
Sun 06-Nov	Midterm II Review Session

Week 10

Tue 08-Nov	Midterm II
Thu 10-Nov	Lecture 18: Experts & The Multiplicative Weights Algorithm	[notes] [slides]
	Homework 7 released	[homework 7]
Fri 11-Nov	Recitation 9: Experts & The Multiplicative Weights Algorithm	[recitation 9] [solutions]

Week 11

Tue 15-Nov	Lecture 19: Approximation Algorithms	[notes] [slides]
Wed 16-Nov	Homework 7 due	[solutions]
Thu 17-Nov	Lecture 20: Online Algorithms (Take Two - MTF Proof)	[notes] [slides]
	Homework 8 released	[homework 8]
Fri 18-Nov	Recitation 10: Online and Approximation Algorithms	[recitation 10] [solutions] (kunal's notes)

Week 12

Tue 22-Nov	Lecture 21: Computational Geometry I: Primitives and Convex Hull	[notes] [slides] (blank)
Wed 23-Nov	Thanksgiving Break begins
Fri 25-Nov	Thanksgiving Break ends

Week 13

Tue 29-Nov	Lecture 22: Computational Geometry II: Incremental Algorithms	[notes] [slides] (blank)
Wed 30-Nov	Homework 8 due
Thu 01-Dec	Lecture 23: Strassen and Karatsuba	[notes] [slides]
	Homework 9 released	[homework 9]
Fri 02-Dec	Recitation 11: Computational Geometry	[recitation 11] [solutions] (kunal's notes)

Week 14

Tue 06-Dec	Lecture 24: The Algorithmic Magic of Polynomials	[notes] [slides]
Wed 07-Dec	Homework 9 orals	[solutions]
Thu 08-Dec	Lecture 25: The Fast Fourier Transform	[notes] [slides] (blank)
	Homework 9 orals
Fri 09-Dec	Recitation 12: FFT, Multiplication, Polynomials	[recitation 12] [solutions] (kunal's notes)
	Homework 9 orals

Finals

Wed 14-Dec	Final Exam Review Session
Fri 16-Dec	Final Exam (8:30am)