MWF 1:30-2:20, Zoom Meeting ID: 97771906541

Office hours Zoom Meeting ID: 94137597308

M/W 2:30-3:20

Also, Tue 4:30-5:20 we have problem solving session at 99626064244

Please send any e-mail questions about the course to **cse421-staff@cs.washington.edu**.

Plesae use ed for course related questions.

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

** Grading Scheme (Roughly):**

Homework | 50% |

Midterm | 15-20% |

Final Exam | 30-35% |

Extra Credit Problems | Can increase final GPA by 0.1 |

Quizzes | Can Increase final GPA by 0.1 |

Lecture | Topic | Slides/Notes | Inclass Exercise | Reading Assignment |
---|---|---|---|---|

Lecture 1 (03/29/21) | Stable Matchings | pdf, Notes | Section 1.1 of KT | |

Lecture 2 (03/31/21) | Stable Matchings | pdf, Notes | Section 1.2 of KT | |

Lecture 3 (04/02/21) | Stable Matchings/Induction | pdf, Notes | ||

Lecture 4 (04/05/21) | Asymptotics | pdfNotes | in-class exercise | Chapter 2 of KT |

Lecture 5 (04/07/21) | Graphs, Trees | pdf, Notes | Section 3.1 of KT | |

Lecture 6 (04/09/21) | BFS | pdf, Notes | Section 3.2 of KT Induction on Graphs | |

Lecture 7 (04/12/21) | Connected Comps | pdf, Notes | Inclass Exercise | Section 3.3,3.4 of KT, sample alg+proof |

Lecture 8 (04/14/21) | Bipartiteness | pdf,Notes | Inclass Exercise | Section 3.2 of KT |

Lecture 9 (04/16/21) | DFS, Topological Sorting | pdf,Notes, Latex Notes | Section 3.6 of KT | |

Lecture 10 (04/19/21) | Greedy: Interval Scheduling/Partitioning | pdf, Notes, Latex Notes | Section 4.1,4.5 of KT | |

Lecture 11 (04/21/21) | Minimum Spanning Tree | pdf, Notes | Latex Notes | Section 4.4 of KT |

Lecture 12 (04/23/21) | Union Find DS | pdf,Notes | Supplementary Notes | Sections 4.6, 5.1 of KT |

Lecture 13 (04/26/21) | Divide and Conq: Closest Pair | pdf,Notes | Sections 5.1,5.2 of KT | |

Lecture 14 (04/28/21) | Divide and Conq: Integer Multiplication | pdf,Notes | Sections 5.4,5.5 of KT | |

Lecture 15 (04/30/21) | Divide and Conq: Midpoint | pdf,Notess | Section 4.4 of KT | |

(05/03/21) Midterm (1:30-2:35 and 10:00-11:05 PST) | ||||

Lecture 16 (05/05/21) | Approximation Algorithms | pdf, Notes | Vertex Cover Supplement, Set Cover Supplemeent | |

Lecture 17 (05/07/21) | Dijkstra's Algorithm, Algorithm Design By Induction | pdf,Notes | Supplement Notes for Dijkstra | Sections 5.1,5.2,5.4,5.8 of Manber's book |

Lecture 18 (05/10/21) | DP: Interval Scheduling | pdf, Notes | Section 6.1 of KT | |

Problem Solving 2 (05/11/21) | Problems 2,3 of HW5-2020 | Notes | video | |

Lecture 19 (05/12/21) | DP: Knapsack, | Section 6.2, 6.4 of KT | ||

Lecture 20 (05/14/21) | RNA Secondary Structure, Seq Alignment | pdf, Notes | Section 6.5 of KT | |

Lecture 21 (05/17/21) | DP: Longest Path in DAG, LIS, Shortest Path | pdf, Notes | Latex Notes | Section 6.6 of KT |

Problem Solving 3 (05/18/21) | Problems 1,2,3 of HW6-2020 | Notes | ||

Lecture 22 (05/19/21) | Network Flow | pdf,Notes | Section 7.1 of KT | |

Lecture 23 (05/21/21) | Max Flow-Min Cut, Maximum matching | pdf,Notes | Section 7.2 of KT | |

Lecture 24 (05/24/21) | Edge Disjoint paths, Matchings | pdf, Notes | Section 7.6 of KT | |

Problem Solving 4 (05/25/21) | Problems 1,3 of HW7-2020 | Notes | ||

Lecture 25 (05/26/21) | Hall's Conidtion, Image Segmentation | pdf, Notes | Section 7.6 of KT | |

Lecture 26 (05/28/21) | Polynomial Time Reductions | pdf, Notes | Section 7.9, 8.1 of KT | |

(05/31/21) No Class: Memorial Day | ||||

Problem Solving 5 (06/01/21) | Problems 2,3 of HW8-2020 | Notes | ||

Lecture 27 (06/02/21) | NP-Completeness | Section 7.10,7.11,8.3 of KT | ||

Lecture 28 (06/04/21) | Bellman Ford Algorithm, Extra Materials | |||

(06/07/21) Final Exam (2:30-5:30 and 10:00-1:00 PST) |

**Homeworks**
[Grading guidelines]:

Homework submission is due via Gradescope

- Homework 1 due Thursday, 8-April at 11:59PM.
- Homework 2 due Thursday, 15-April at 11:59PM.
- Homework 3 due Thursday, 22-April at 11:59PM.
- Homework 4 due Thursday, 29-April at 11:59PM.
- Homework 5 due Thursday, 13-May at 11:59PM.
- Homework 6 due Thursday, 20-May at 11:59PM.
- Homework 7 due Thursday, 27-May at 11:59PM.
- Homework 8 due Friday, 04-May at 11:59PM.

TA |
Office hours |
Meeting Id |

Savanna J Yee | Mon 10:00 AM-10:50 AM | 97332958862 |

Mickey Moonkaen | Mon 4:00 PM-4:50 PM | 94908850680 |

Todor Dimitrov | Tue 9:00 AM-9:50 AM | 7606986951 |

Albert Liang Zhong | Tues 12:30 PM-1:20 PM | 95015984293 |

Aidan Arieh Gottlieb | Tue 2:30 PM-3:20 PM | 2075377702 |

Yunkyu Song | Tue 5:30 PM-6:20 PM | 91882309072 |

Chase Lee | Wed 8:00 AM-8:50 AM | 97185046505 |

Liangyu Zhao | Wed 4:00 PM-4:50 PM | 3215688552 |

Mrigank Arora | Thu 9:00 AM-9:50 AM | 98031098493 |

Johnson Kuang | Thu 11:00 AM-11:50 AM | 7935407872 |

Notes for problem solving session on 04/27/21

**Exams:**

**Midterm exam**:

At 1:30-2:35 (PM) and 10:00-11:05 (PM) Monday 03-May-2021 This will be open book and open notes, hard copies only. You are not allowed to access internet. The coverage includes all topics through divide and conquer. An old sample midterm with sample solutions is available. Here is Midterm exam of 2020. No solutions will be posted for this midterm. Please try to solve the problems. I will upload the solutions by Friday. There will be a review session on Saturday, 01-May-2021 at 10:00 am, Zoom Meeting ID: 5948822807. Please bring your questions. Here are notes for midterm review session Here are recorded video, Slides for the review session.**Final exam**:

At 2:30-5:30 (PM) and 10:00 (PM)-1:00 (AM) on Monday 7-Jun-2021. Similar to midterm, it will be open book and open notes, hard copies only.

There is a practice final from previous offerings of the course. here is the solutions to the sample final. Here is another old final. And here is the solution. More Practice Problems There will be a review session on Saturday, 05-Jun-2021 at 10:00 am. in Zoom Meeting ID: 5948822807. Please bring your questions. Here are slides for reviewing final. Notes and recorded video.

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