MWF 1:302:20, MUE 153
Office hours M 2:304:00, Tu 5:006:00 in CSE 562
Please send any email questions about the course to cse421staff18sp@cs.washington.edu.
Plesae use Canvas's builtin discussion board for course related questions.
We will cover almost all of chapters 18 of the Kleinberg/Tardos text plus some additional material from later chapters. In addition, I recommend reading chapter 5 of Introduction to Algorithms: A Creative Approach, by Udi Manber, AddisonWesley 1989. This book has a unique point of view on algorithm design.
Another handy reference is Steven Skiena's Stonybrook Algorithm Repository
Lecture  Topic  Slides  References  

Lecture 1 (03/26/18)  Stable Matchings  slide, slide(pdf)  Sec 1.1 of KT Practice of stable matching 

Lecture 2 (03/28/18)  Stable Matchings  slide, slide(pdf)  Sec 2.3 of KT  
Lecture 3 (03/30/18)  Complexity, Graphs  slide, slide(pdf)  Sec 2, 3.1 of KT  
Lecture 4 (04/02/18)  Breadth First Search  slide, slide(pdf)  Sec 3.2, 3.3, 3.4 of KT  
Lecture 5 (04/04/18)  Depth First Search  slide, slide(pdf)  Sec 3.2, 3.5 of KT  
Lecture 6 (04/06/18)  Interval Scheduling  slide, slide(pdf)  Sec 4.1 of KT  
Lecture 7 (04/09/18)  Minimizing Lateness  slide, slide(pdf)  Sec 4.2 of KT  
Lecture 8 (04/11/18)  Optimal Caching  slide, slide(pdf)  Sec 4.3 of KT  
Lecture 9 (04/13/18)  Dijkstra Algorithm  slide, slide(pdf)  Sec 4.4 of KT  
Lecture 10 (04/16/18)  Minimum Spinning Tree, Union Find  slide, slide(pdf)  Sec 4.5, 4.6 of KT  
Lecture 11 (04/18/18)  Closest Points  slide, slide(pdf)  Sec 5.1, 5.4 of KT  
Lecture 12 (04/20/18)  Master Theorem  slide, slide(pdf)  Sec 5.2 of KT  
Lecture 13 (04/23/18)  Multiplication  slide, slide(pdf)  Sec 5.5, 5.6 of KT  
Lecture 14 (04/25/18)  Multiplication  slide, slide(pdf)  Sec 5.5, 5.6 of KT  
Lecture 15 (04/27/18)  Midterm review  slide, slide(pdf)  Sec 13.5 of KT  
(04/30/18) Midterm (GWN 201)  
Lecture 16 (05/02/18)  Dynamic Programming: Weighted Interval Scheduling, Knapsack  slide, slide(pdf)  Sec 6.1, 6.2, 6.4 of KT  
Lecture 17 (05/04/18)  Knapsack, RNA, Sequence Alignment  slide, slide(pdf)  Sec 6.5, 6.6, 6.7 of KT  
Lecture 18 (05/07/18)  Longest Path in a DAG, Longest Increasing Subsequence, Shortest Paths with Negative weights  slide, slide(pdf)  Sec 6.10 of KT  
Lecture 19 (05/09/18)  Vertex Cover / Set Cover  slide, slide(pdf)  None  
Lecture 20 (05/11/18)  Compression  slide, slide(pdf)  Sec 4.8 of KT  
Lecture 21 (05/14/18)  Maxflow  Canvas  Sec 7 of KT  
Lecture 22 (05/16/18)  Maxflow  Canvas  Sec 7 of KT  
Lecture 23 (05/18/18)  Applications of Maxflow  slide, slide(pdf)  Sec 7 of KT  
Lecture 24 (05/21/18)  EdmondsKarp Algorithm and More Applications  slide, slide(pdf)  Sec 7 of KT  
Lecture 25 (05/23/18)  Reductions, NPCompleteness  slide, slide(pdf)  Sec 8 of KT  
Lecture 26 (05/25/18)  NPCompleteness, Linear Programming (Bonus)  slide, slide(pdf)  Sec 8 of KT  
(05/28/18) Memorial Day  
Lecture 27 (05/30/18)  Convex Programming (Bonus)  None  
Lecture 28 (06/01/18)  Final Review  Canvas  None  
(06/04/18) Final Exam (14:3016:20, GWN 301) 
Homeworks [Grading guidelines]:
Homework submission is due via Canvas
Late Policy: Unless otherwise announced, 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 questionwise. So, please hand in whatever you finish first. Note that 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 canvas within 5 days after the grade is posted.
TA  Office hours (from Apr 2  June 1) 
Room 
Benjamin Jones  Mon 10:30am11:20am  CSE 007 
Mathew Luo  Tue 11:30am  12:20pm  CSE 007 
Angli Liu  Tue 2:30pm3:20pm  CSE 007 
Guanghao Ye  Tue 4:00pm4:50pm  CSE 220 
Thomas Merth  Wed 10:30am11:20am  CSE 007 
Aditya Saraf  Thu 12:30pm 1:20pm  CSE 007 
Sai Nimmagadda  Fri 11:30am12:20pm  CSE 007 
Exams: