For future lectures, this is a *tentative* schedule. The
exact contents are subject to change. Links to future materials
may also be broken.

Week 1

Topic

Week 1

Lecture 1

(Wed, Sep 27)

Intro, Stable Matching

Lecture 2

(Fri, Sep 29)

Stable Matching, Overview

Week 2

Lecture 3

(Mon, Oct 2)

Overview, Graph Traversal (BFS)

Lecture 4

(Wed, Oct 4)

Graph Traversal (DFS & Applications)

Topological Sort

Topological Sort

Week 3

Lecture 6

(Mon, Oct 9)

More Greedy Algorithms

Dijkstra's Algorithm

Dijkstra's Algorithm

Lecture 7

(Wed, Oct 11)

Minimum Spanning Trees:

Prim's and Kruskal's Algorithms and beyond

Prim's and Kruskal's Algorithms and beyond

Section 3

(Thu, Oct 12)

Problem Solving Strategy

Greedy Algorithms

Greedy Algorithms

Lecture 8

(Fri, Oct 13)

Divide and Conquer

Week 4

Lecture 9

(Mon, Oct 16)

Multiplication: Matrix, Integer, Polynomial

Strassen, Karatsuba, FFT

Strassen, Karatsuba, FFT

Lecture 10

(Wed, Oct 18)

Median, Quicksort

Beyond the Master Theorem

Beyond the Master Theorem

Section 4

(Thu, Oct 19)

Problem Solving Strategy

Divide and Conquer

Divide and Conquer

Week 5

Lecture 12

(Mon, Oct 23)

Dynamic Programming

Longest Increasing Subsequence, Knapsack

Longest Increasing Subsequence, Knapsack

Lecture 13

(Wed, Oct 25)

Dynamic Programming

RNA Secondary Structure, Edit Distance (Sequence Alignment)

RNA Secondary Structure, Edit Distance (Sequence Alignment)

Section 5

(Thu, Oct 26)

Problem Solving Strategy

Dynamic Programming

Dynamic Programming

Lecture 14

(Fri, Oct 27)

Dynamic Programming

Bellman-Ford algorithm, Applications

Bellman-Ford algorithm, Applications

Week 6

Lecture 16

(Wed, Nov 1)

MaxFlow/MinCut

Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm

Lecture 17

(Fri, Nov 3)

Network Flow in Polynomial Time

Week 7

Lecture 18

(Mon, Nov 6)

Applications of MaxFlow/MinCut I

(Fri, Nov 10)

Week 8

Lecture 19

(Mon, Nov 13)

Applications of MaxFlow/MinCut II

Lecture 20

(Wed, Nov 15)

Linear Programming

Section 8

(Thu, Nov 16)

Algorithmic Toolbox

Linear Programming

Linear Programming

Week 9

Lecture 23

(Wed, Nov 22)

NP-completeness I: Reductions

(Thu, Nov 23)

(Fri, Nov 24)

Week 10

Lecture 25

(Wed, Nov 29)

NP-Completeness III

Lecture 26

(Fri, Dec 1)

Approximation Algorithms

Week 11

Lecture 27

(Mon, Dec 4)

Dealing with NP-completeness

Lecture 28

(Wed, Dec 6)

Parametrized complexity

SAT Solvers

SAT Solvers

Exam Week

Final Exam

(Mon, Dec 11)

The final exam is scheduled at 2:30-4:20 pm in our regular classroom (CSE2 G20) at the time specified in the UW Final Exam Schedule for Autumn 2023.

This course website heavily follows the example of the website of CSE373 2019 Spring.