CSE 421: Introduction to Algorithms
Spring, 2018
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
Course evaluation
Email list:
Class email list: cse421a_sp18 [archives]Please send any e-mail questions about the course to cse421staff18sp@cs.washington.edu.
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
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) | ||||
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 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.
- Homework 1 due Wednesday, 4-Apr at 1:30PM.
- Homework 2 due Wednesday, 11-Apr at 1:30PM.
- Homework 3 due Wednesday, 18-Apr at 1:30PM.
- Homework 4 due Wednesday, 25-Apr at 1:30PM.
- Homework 5 due Monday, 30-Apr at 1:30PM.
- Homework 6 due Wednesday, 9-May at 1:30PM.
- Homework 7 due Wednesday, 16-May at 1:30PM.
- Homework 8 due Wednesday, 23-May at 1:30PM.
- Homework 9 due Wednesday, 30-May at 1:30PM.
- Homework 10 due Monday, 4-June at 2:30PM.
| 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.