Tentative Schedule

Lecture	Topic	Slides	References
Part I: Graphs
Lec. 1 (01/03/22)	Stable Matchings	pptx/pdf, demo, proof	Sec 1, reading, video 1,2
Lec. 2 (01/05/22)	Graphs	pptx/pdf, proof	Sec 2, 3.1, video
Lec. 3 (01/07/22)	Breadth First Search	pptx/pdf, proof	Sec 3.2-3.4, App 1,2, video
Lec. 4 (01/10/22)	Depth-first search	pptx/pdf, proof	Sec 3.6, App 1, 2, video
Part II: Greedy Methods
Lec. 5 (01/12/22)	Interval Scheduling	pptx/pdf, proof	Sec 4.1, video
Lec. 6 (01/14/22)	Minimizing Lateness, Optimal Caching	pptx/pdf, proof	Sec 4.2-4.3, practice, video
Holiday (01/17/22)	Martin Luther King Day
Lec. 7 (01/19/22)	Dijkstra Algorithm	pptx/pdf, proof	Sec 4.4, practice, video
Lec. 8 (01/21/22)	Minimum Spinning Tree (by Jeremy Lin)	pptx/pdf, proof	Sec 4.5-4.6, video
Lec. 9 (01/24/22)	Huffman Codes	pptx/pdf, proof	Sec 4.8, universal code, video
Part III: Divide and Conquer
Lec. 10 (01/26/22)	Closest Points	pptx/pdf	Sec 5.1-5.2, Master Theorem++, video
Lec. 11 (01/28/22)	Median	pptx/pdf, proof	Sec 5.4-5.5, video
Lec. 12 (01/31/22)	Multiplication and Fast Fourier Transform	pptx/pdf	Sec 5.5, news, video
Lec. 13 (02/02/22)	Midterm review	pptx/pdf, proof	video
Special (02/04/22)	Midterm
Part IV: Dynamic Programming
Lec. 14 (02/07/22)	Weighted Interval Scheduling, Knapsack	pptx/pdf	Sec 6.1-6.2, 6.4, video
Lec. 15 (02/09/22)	RNA, Sequence Alignment	pptx/pdf	Sec 6.5-6.7, video
Lec. 16 (02/11/22)	Shortest Paths with Negative weights	pptx/pdf, proof	Sec 6.8, 6.10, video
Lec. 17 (02/14/22)	More Dynamic Programming	pptx/pdf	news, video
Part V: Network Flow
Lec. 18 (02/16/22)	Maxflow (by Sally Dong)	pdf	Sec 7.1, video
Lec. 19 (02/18/22)	Ford-Fulkerson	pptx/pdf, proof	Sec 7.2, video
Holiday (02/22/22)	Presidents' Day
Lec. 20 (02/23/22)	Applications of Maxflow	pptx/pdf	Sec 7.5-7.6, 7.10-7.11, video
Lec. 21 (02/25/22)	More Maxflow Algorithms	pptx/pdf	Sec 7.3, video
Part VI: NP completeness
Lec. 22 (02/28/22)	NP completeness	pptx/pdf, proof	Sec 8.1-8.3, Fine Grained Complexity, video
Lec. 23 (03/02/22)	NP completeness	pptx/pdf	Sec 8.4, 8.7-8.8, video
Lec. 24 (03/04/22)	Approximation Algorithms	pptx/pdf	Sec 11.3-11.4, video
Last Part
Lec. 25 (03/07/22)	Linear Programming	pptx/pdf	video
Lec. 26 (03/09/22)	Linear Programming	pptx/pdf	video
Lec. 27 (03/11/22)	Final review	pptx/pdf	video
Special (03/14/22)	Final

Slides with annotations (Some slides may not have annotations):
Lectures 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27.

Homeworks:

• Homework 1 due Wednesday, 12-Jan at 1:30PM.
• Homework 2 due Wednesday, 19-Jan at 1:30PM.
• Homework 3 due Wednesday, 26-Jan at 1:30PM.
• Homework 4 due Wednesday, 2-Feb at 1:30PM.
• Homework 5 due Wednesday, 16-Feb at 1:30PM.
• Homework 6 due Wednesday, 23-Feb at 1:30PM.
• Homework 7 due Wednesday, 2-Mar at 1:30PM.
• Homework 8 due Wednesday, 9-Mar at 1:30PM.

Sick Policy:

• If you feel sick or suspect COVID, do not come to class. There are recordings and slides for all lectures. Virtual mid-term and final can be arranged for medical reasons. Email yintat@uw for such an arrangement before the exam starts.

Late Policy:

• Homework is due at the start of class on the due date. 20% off after the due time. 40% off 1 day after the due time. 100% off 2 days after the due time. The deduction is counted question-wise. Please hand in whatever you finish first.
• There is extra credit for you to earn some extra marks. Therefore, no extension except for an emergency reason.

Regrade Policy:

• Put a regrade comment on homework in gradescope within 5 days after the grade is posted.

UW Policy:

• We follow the standard UW CSE policy for academic integrity.
• Please refer to university policies regarding disability accommodations or religious accommodations.

Office hours:

TA	Office hours	Room
Andreea Ghizila andreeag@uw	Mon 11:30-12:30pm	4th Floor breakout / Zoom
Sally Dong sallyqd@uw	Tue 11am-12noon	4th Floor breakout / Zoom
Jason Waataja jwaataja@uw	Tue 3-4pm	4th Floor breakout / Zoom
Jeremy Lin linjer23@uw	Tue 2-3pm	4th Floor breakout / Zoom
Ashwin Banwari ash1152@uw	Fri 2:30-3:30pm	5th Floor breakout / Zoom
Swati Padmanabhan pswati@uw	Sun 10:00-11:00am	Google Meet

Midterm exam:

• Time: 04-Feb-2022 (Friday)
• Location: CSE2 G20
• Open book and open notes, hard copies only
• Coverage: All topics through divide and conquer
• Sample midterm 1 (solutions).
• Sample midterm 2 (solutions).

Please try to solve the problems before looking at the solutions.

Final exam:

• Time: 14-Mar-2022 at 2:30-4:20 pm (Monday)
• Location: CSE2 G20
• Open book and open notes, hard copies only
• Coverage: All topics through NP completeness
• Sample final 1 (solutions).
• Sample final 2 (solutions).

Please try to solve the problems before looking at the solutions.