MWF 1:30-2:20, THO 101

Office hours M 2:30-3:30, Tu 4:30-5:30 in CSE 562

- Course evaluation: https://uw.iasystem.org/survey/200292
- Assignment: Canvas
- Discussion: Piazza
- Mailing List: cse421a_au18 [archives]
- Email TA and instructor: cse421staff18au@cs.washington.edu
- Textbook: Algorithm Design by Jon Kleinberg and Eva Tardos

We will cover chapters 1-8. - Reference: Introduction to Algorithms by CLRS

- Homework (50%)
- Midterm (20%)
- Final (30%)

Lecture | Topic | Slides | References |

Lec. 1 (09/26/18) | Stable Matchings | slide, slide(pdf) demo, proof |
Sec 1 story |

Lec. 2 (09/28/18) | Stable Matchings | slide, slide(pdf) note |
Sec 2 fair division |

Lec. 3 (10/01/18) | Graphs | slide, slide(pdf) note |
Sec 2, 3.1 |

Lec. 4 (10/03/18) | Breadth First Search | slide, slide(pdf) note |
Sec 3.2-3.4 application: (1) |

Lec. 5 (10/05/18) | Applications of BFS Depth-first search |
slide, slide(pdf) note |
Sec 3.2-3.4 application: (1) |

Lec. 6 (10/08/18) | Topological sort Interval Scheduling |
slide, slide(pdf) note |
Sec 3.5 / Sec 4.1 application: (1) |

Lec. 7 (10/10/18) | Minimizing Lateness | slide, slide(pdf) note |
Sec 4.2 |

Lec. 8 (10/12/18) | Optimal Caching | slide, slide(pdf) note |
Sec 4.3 k-server problem |

Lec. 9 (10/15/18) | Dijkstra Algorithm | slide, slide(pdf) note |
Sec 4.4 A* search |

Lec. 10 (10/17/18) | Minimum Spinning Tree | slide, slide(pdf) note |
Sec 4.5-4.6 log(log(n)) proof |

Lec. 11 (10/19/18) | Compression | slide, slide(pdf) note |
Sec 4.8 |

Lec. 12 (10/22/18) | Closest Points | slide, slide(pdf) note |
Sec 5.1, 5.4 Another appraoch |

Lec. 13 (10/24/18) | Median / Multiplication | slide, slide(pdf) | Sec 5.2, 5.5 |

Lec. 14 (10/26/18) | Midterm review | Canvas | None |

(10/29/18) Midterm |
|||

Lec. 15 (10/31/18) | Weighted Interval Scheduling / Knapsack | slide, slide(pdf) | Sec 6.1, 6.2, 6.4 |

Lec. 16 (11/02/18) | RNA, Sequence Alignment | slide, slide(pdf) note |
Sec 6.5, 6.6 |

Lec. 17 (11/05/18) | Shortest Paths with Negative weights | slide, slide(pdf) note |
6.10 |

Lec. 18 (11/07/18) | Polynomial Multiplication | slide, slide(pdf) note |
Sec 5.6 |

Lec. 19 (11/09/18) | Polynomial Multiplication | notenote | Sec 5.6 |

(11/12/18) Veterans Day |
|||

Lec. 20 (11/14/18) | Maxflow | slide, slide(pdf) note |
Sec 7.1, 7.2 |

Lec. 21 (11/16/18) | Maxflow | slide, slide(pdf) note |
Sec 7.1, 7.2, 7.5 |

Lec. 22 (11/19/18) | Edmonds-Karp Algorithm | slide, slide(pdf) note |
None |

Lec. 23 (11/21/18) | Vertex Cover / Set Cover | slide(pdf) | Sec 11.3 |

(11/23/18) Thanksgiving |
|||

Lec. 24 (11/26/18) | Applications of Maxflow | slide, slide(pdf) note, note, note |
Sec 7.10, 7.11, 7.12 |

Lec. 25 (11/28/18) | Reductions, NP-Completeness | slide, slide(pdf) note |
Sec 8 |

Lec. 26 (11/30/18) | Reductions, NP-Completeness | slide, slide(pdf) | Sec 8 |

Lec. 27 (12/03/18) | Linear Programming | slide, slide(pdf) note |
None |

Lec. 28 (12/05/18) | Convex Programming | None | None |

Lec. 29 (12/07/18) | Final review | Canvas | None |

(12/10/18) Final |

- Homework 1 due Wednesday, 03-Oct at 1:30PM.
- Homework 2 due Wednesday, 10-Oct at 1:30PM.
- Homework 3 due Wednesday, 17-Oct at 1:30PM.
- Homework 4 due Wednesday, 24-Oct at 1:30PM.
- Homework 5 due Monday, 29-Oct at 1:30PM.
- Homework 6 due Wednesday, 7-Nov at 1:30PM.
- Homework 7 due Wednesday, 14-Nov at 1:30PM.
- Homework 8 due Wednesday, 28-Nov at 1:30PM.
- Homework 9 due Wednesday, 5-Dec at 1:30PM.
- Homework 10 due Monday, 10-Dec at 2:30PM.

- 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.

- Put a regrade comment on homework in canvas within 5 days after the grade is posted.
- If the TA forget to reply, please email the TA via the staff email and indicates who is the TA in the email.

TA |
Office hours (from Oct 01 - Dec 07) |
Room |

Dongkai Xu | Mon 10:30am-11:30am | CSE 007 |

Xin Yang | Mon 04:30pm - 05:30pm | CSE 007 |

Mathew Luo | Tue 11:30am-12:30pm | CSE 007 |

Swati Padmanabhan | Tue 12:30pm-01:30pm | CSE 007 |

Guanghao Ye | Tue 03:00pm-04:00pm | CSE 007 |

Faye Yu | Wed 10:30am- 11:30am | CSE 220 |

Zongyuan Chen | Thu 01:30pm-02:30pm | CSE 007 |

Leiyi Zhang | Fri 11:30am-12:30pm | CSE 007 |

- Time: 29-Oct-2018 (Monday)
- Location: THO 101
- Open book and open notes, hard copies only
- Coverage: All topics through divide and conquer
- Sample midterm 1 (solutions).
- Sample midterm 2 (solutions).

- Time: 10-Dec-2018 at 2:30-4:20 pm (Monday)

as shown in the exam schedule - Location: GWN 301
- Open book and open notes, hard copies only
- Coverage: All except lecture 23, 27, 28
- Sample final 1 (solutions).
- Sample final 2 (solutions).

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.