## CSE 421: Introduction to Algorithms

#### Yin Tat Lee

MWF 1:30-2:20, CSE2 G20
Office hours Monday 2:30-3:30pm in CSE 562 or zoom

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

##### Tentative Schedule
 Lecture Topic Slides References Part I: Graphs Lec. 1 (01/03/22) Stable Matchings pptx/pdf, demo, proof Sec 1, reading, video 1,2 Lec. 2 (01/05/22) Graphs pptx/pdf, proof Sec 2, 3.1, video Lec. 3 (01/07/22) Breadth First Search pptx/pdf, proof Sec 3.2-3.4, App 1,2, video Lec. 4 (01/10/22) Depth-first search pptx/pdf, proof Sec 3.6, App 1, 2, video Part II: Greedy Methods Lec. 5 (01/12/22) Interval Scheduling pptx/pdf, proof Sec 4.1, video Lec. 6 (01/14/22) Minimizing Lateness, Optimal Caching pptx/pdf, proof Sec 4.2-4.3, practice, video Holiday (01/17/22) Martin Luther King Day Lec. 7 (01/19/22) Dijkstra Algorithm pptx/pdf, proof Sec 4.4, practice, video Lec. 8 (01/21/22) Minimum Spinning Tree (by Jeremy Lin) pptx/pdf, proof Sec 4.5-4.6, video Lec. 9 (01/24/22) Huffman Codes pptx/pdf, proof Sec 4.8, universal code, video Part III: Divide and Conquer Lec. 10 (01/26/22) Closest Points pptx/pdf Sec 5.1-5.2, Master Theorem++, video Lec. 11 (01/28/22) Median pptx/pdf, proof Sec 5.4-5.5, video Lec. 12 (01/31/22) Multiplication and Fast Fourier Transform pptx/pdf Sec 5.5, news, video Lec. 13 (02/02/22) Midterm review pptx/pdf, proof video Special (02/04/22) Midterm Part IV: Dynamic Programming Lec. 14 (02/07/22) Weighted Interval Scheduling, Knapsack pptx/pdf Sec 6.1-6.2, 6.4, video Lec. 15 (02/09/22) RNA, Sequence Alignment pptx/pdf Sec 6.5-6.7, video Lec. 16 (02/11/22) Shortest Paths with Negative weights pptx/pdf, proof Sec 6.8, 6.10, video Lec. 17 (02/14/22) More Dynamic Programming pptx/pdf news, video Part V: Network Flow Lec. 18 (02/16/22) Maxflow (by Sally Dong) pdf Sec 7.1, video Lec. 19 (02/18/22) Ford-Fulkerson pptx/pdf, proof Sec 7.2, video Holiday (02/22/22) Presidents' Day Lec. 20 (02/23/22) Applications of Maxflow pptx/pdf Sec 7.5-7.6, 7.10-7.11, video Lec. 21 (02/25/22) More Maxflow Algorithms pptx/pdf Sec 7.3, video Part VI: NP completeness Lec. 22 (02/28/22) NP completeness pptx/pdf, proof Sec 8.1-8.3, Fine Grained Complexity, video Lec. 23 (03/02/22) NP completeness pptx/pdf Sec 8.4, 8.7-8.8, video Lec. 24 (03/04/22) Approximation Algorithms pptx/pdf Sec 11.3-11.4, video Last Part Lec. 25 (03/07/22) Linear Programming pptx/pdf video Lec. 26 (03/09/22) Linear Programming pptx/pdf video Lec. 27 (03/11/22) Final review pptx/pdf video Special (03/14/22) Final
Slides with annotations (Some slides may not have annotations):
Lectures 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27.

#### Homeworks:

##### Sick Policy:
• If you feel sick or suspect COVID, do not come to class. There are recordings and slides for all lectures. Virtual mid-term and final can be arranged for medical reasons. Email yintat@uw for such an arrangement before the exam starts.
##### 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.
• Put a regrade comment on homework in gradescope within 5 days after the grade is posted.

#### Office hours:

 TA Office hours Room Andreea Ghizilaandreeag@uw Mon 11:30-12:30pm 4th Floor breakout / Zoom Sally Dongsallyqd@uw Tue 11am-12noon 4th Floor breakout / Zoom Jason Waatajajwaataja@uw Tue 3-4pm 4th Floor breakout / Zoom Jeremy Linlinjer23@uw Tue 2-3pm 4th Floor breakout / Zoom Ashwin Banwariash1152@uw Fri 2:30-3:30pm 5th Floor breakout / Zoom Swati Padmanabhanpswati@uw Sun 10:00-11:00am Google Meet

#### 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-2022, Paul G. Allen School of Computer Science and Engineering, University of Washington.