CSE 421: Introduction to Algorithms

Autumn, 2018

Yin Tat Lee

MWF 1:30-2:20, THO 101
Office hours M 2:30-3:30, Tu 4:30-5:30 in CSE 562
Links:
Grading Scheme (Roughly):
  • Homework (50%)
  • Midterm (20%)
  • Final (30%)
Turning machine

Tentative Schedule
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

Homeworks: [Grading guidelines]

Submission is due via Canvas
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 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.

Office hours:

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

Midterm exam:

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

Final exam:

Please try to solve the problems before looking at the 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.