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) Sec 5.1, 5.4
Another appraoch
Lec. 13 (10/24/18) Master Theorem / Multiplication Sec 5.2, 5.5, 5.6
Lec. 14 (10/26/18) Midterm review Canvas None
(10/29/18) Midterm
Lec. 15 (10/31/18) Multiplication Sec 5.5, 5.6
Lec. 16 (11/02/18) Weighted Interval Scheduling Sec 6.1, 6.2
Lec. 17 (11/05/18) Knapsack Sec 6.4
Lec. 18 (11/07/18) RNA, Sequence Alignment Sec 6.5, 6.6
Lec. 19 (11/09/18) Longest Path in a DAG Sec 6.5, 6.6
(11/12/18) Veterans Day
Lec. 20 (11/14/18) Shortest Paths with Negative weights Sec 6.10
Lec. 21 (11/16/18) Maxflow Sec 7.1, 7.2
Lec. 22 (11/19/18) Maxflow Sec 7.1, 7.2
Lec. 23 (11/21/18) Vertex Cover / Set Cover Sec 11.3
(11/23/18) Thanksgiving
Lec. 24 (11/26/18) Applications of Maxflow Sec 7.5, 7.10
Lec. 25 (11/28/18) Edmonds-Karp Algorithm None
Lec. 26 (11/30/18) Reductions, NP-Completeness Sec 8
Lec. 27 (12/03/18) Linear Programming None
Lec. 28 (12/05/18) Convex Programming None
Lec. 29 (12/07/18) Final review Canvas None
(12/10/18) Final

Homeworks: [Grading guidelines]

Submission is due via Canvas
  • 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, 21-Nov at 1:30PM.
  • Homework 9 due Wednesday, 5-Dec at 1:30PM.
  • Homework 10 due Monday, 10-Dec at 2:30PM.
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.

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:

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