## CSE 421: Introduction to Algorithms

#### Yin Tat Lee

MWF 1:30-2:20, MUE 153
Office hours M 2:30-4:00, Tu 5:00-6:00 in CSE 562

##### Email list:
Class email list: cse421a_sp18     [archives]

Plesae use Canvas's builtin discussion board for course related questions.

##### Textbook:
Algorithm Design by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2006.

We will cover almost all of chapters 1-8 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, Addison-Wesley 1989. This book has a unique point of view on algorithm design.

Another handy reference is Steven Skiena's Stonybrook Algorithm Repository

 Homework 50% Midterm 15% Final Exam 35%

##### Lecture Slides
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) Edmonds-Karp Algorithm and More Applications slide, slide(pdf) Sec 7 of KT
Lecture 25 (05/23/18) Reductions, NP-Completeness slide, slide(pdf) Sec 8 of KT
Lecture 26 (05/25/18) NP-Completeness, 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:30-16:20, GWN 301)

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 question-wise. 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:30am-11:20am CSE 007 Mathew Luo Tue 11:30am - 12:20pm CSE 007 Angli Liu Tue 2:30pm-3:20pm CSE 007 Guanghao Ye Tue 4:00pm-4:50pm CSE 220 Thomas Merth Wed 10:30am-11:20am CSE 007 Aditya Saraf Thu 12:30pm- 1:20pm CSE 007 Sai Nimmagadda Fri 11:30am-12:20pm CSE 007

Exams:

• Midterm exam:
In GWN 201 at the regular class time on Monday, 30-Apr-2018. This will be open book and open notes, hard copies only. The coverage includes all topics through divide and conquer. An old sample midterm is available along with sample solutions. Please try to solve the problems before looking at the asnwer sheet.
• Final exam:
In GWN 301 on Monday, 04-June-2018 at 2:30-4:20 pm as shown in the UW exam schedule. This will be open book and open notes, hard copies only.
There is an practice final from previous offerings of the course. Here is a solutions to the sample final. Here is another old final. And here is the solution.

Portions of the CSE 421 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 421 Web: © 1993-2018, Paul G. Allen School of Computer Science and Engineering, University of Washington.