Schedule Syllabus Office Hours Course Staff | Gradescope Discussion Board | Problem Sets

cartoon of a Turing machine

Introduction to Algorithms

CSE 421 | Spring 2025

Course schedule and topics

 

March 31

Lecture 1

Thinking like a computer scientist

  • Preamble: course logistics, information, etc.
  • The stable matching algorithm
  • Pset 1 released due Apr 9th

Literature

  • K&T: 1

April 2

Lecture 2

The stable matching algorithm

  • Continuation of stable matching algorithm
  • The RAM model for computation

Literature

  • K&T: 1.2-2.4

April 3

Section 1

Overview and stable matchings

April 4

Lecture 3

Graph traversal

  • Overview of the course
  • Introduction to greedy algorithms

Literature

  • K&T: 3-3.2, 4.1

April 7

Lecture 4

Graph traversal

  • Breadth- and depth-first search
  • Pset 2 released due Apr 16th

Literature

  • K&T: 3.3-3.6, DPV: 4.2-4.3

April 9

Lecture 5

Topological sort and greedy algorithms

  • Topological sort
  • Principles of greedy algorithms
  • Exchange principle, greedy algorithm proof techniques
  • Minimum lateness problem

Literature

  • K&T: 4-4.2, DPV: 5-5.1

April 10

Section 2

Graph Traversal and Algorithm Proofs

April 11

Lecture 6

Greedy approximation and graph algorithms

  • Max cut problem and greedy approximation algorithm
  • Shortest path problem, Dijkstra's

Literature

  • K&T: 12.4,4.4-4.7, DPV: 4.4-4.7

April 14

Lecture 7

Minimum spanning trees

  • Minimum spanning trees
  • Prim's and Kruskal's algorithms
  • k-clustering of datapoints
  • Pset 3 released due Apr 23rd

Literature

  • K&T: 12.4,4.4-4.7, DPV: 4.4-4.7

April 16

Lecture 8

Divide and conquer algorithms

  • Binary search and mergesort
  • 2D Euclidean shortest distance
  • The master theorem

Literature

  • K&T: 5-5.4, DPV: 2.2-2.4

April 17

Section 3

Greedy algorithms

April 18

Lecture 9

Multiplication

  • Matrix, integer, and polynomial multiplication
  • Strassen's algorithm
  • Karatsuba's algorithm
  • Fast Fourier Transform
  • Convolution, Image processing

Literature

  • K&T: 5.5-5.6, DPV: 2.5-2.6

April 21

Lecture 10

Randomized divide and conquer

  • Median, Selection, and Quicksort
  • Derandomization
  • Pset 4 released due Apr 30th
  • Pset 4 ¾ released due May 7nd

Literature

  • K&T: 13.5, DPV: 2.4

April 23

Lecture 11

Dynamic programming I

  • Principles of dynamic programming
  • Tribonacci numbers
  • Edit distance

Literature

  • K&T: 6,6.2,6.6, DPV 6.3

April 24

Section 4

Divide and Conquer

April 25

Lecture 12

Dynamic programming II: The Knapsack problem

  • Brute force algorithm
  • Dynamic programming algorithm
  • Approximation algorithm

Literature

  • K&T: 6.4, 11.8, DPV 6.4

April 28

Lecture 13

Dynamic programming III

  • Space complexity
  • RNA secondary sequences
  • Top-down vs bottom-up

Literature

  • K&T: 6.1-6.3, 6.5, 6.8, DPV 6.6

April 30

Lecture 14

Dynamic programming IV

  • Bellman-Ford algorithm
  • Applications

Literature

  • K&T: 6.8-9, DPV 6.6

May 1

Section 5

May 1

Question & Answer

Question & Answer

  • With Professor Nirkhe. Location: CSE2 G01. Time: 5:30pm-7:30pm.
  • No planned topic. Bring any questions you have or topics you want clarified.
  • Recording quality may be wanting as it will be on whiteboard.

May 2

Lecture 15

Negative cycles and network flow

  • Detecting negative cycles with Bellman-Ford
  • Definition of max flow and min cut
  • Value of a flow, equivalent definitions
  • Greedy flow algorithm: Ford-Fulkerson

Literature

  • K&T: 7-7.2

May 5

Midterm

Midterm

  • Location: Lecture Hall CSE2 G20
  • Time: 1 Hour. Starts exactly at 3:30 and ends exactly at 4:30.
  • Disability Requests that are approved will be in CSE2 345 starting at 3:30 as well.
  • Contact head TAs to arrange your specific requirements. Otherwise we assume you are taking standard exam despite your disability requests.
  • You may bring 1 8.5x11 page of notes (both sides); see the midterm coversheet for details.

May 7

Lecture 16

Max flow/min cut

  • Max flow/min cut duality
  • Augmenting paths algorithm
  • Ford-Fulkerson algorithm
  • Application to bipartite matching

Literature

  • K&T: 7.2-7.5

May 9

Lecture 17

Network flow in polynomial time

  • Finding better augmenting paths
  • The Edmonds-Karp algorithm
  • Hall's theorem
  • Edge disjoint paths

Literature

  • K&T: 7.5-7.7,7.12

May 12

Lecture 18

Flow algorithm applications

  • Network connectivity
  • Capacity demands
  • Baseball winner problem

Literature

  • K&T: 7.5-7.7,7.12

May 14

Lecture 19

Linear programming I

Literature

  • DPV 7-7.3

May 16

Lecture 20

Linear programming II

Literature

  • DPV 7.4-7.5

May 19

Lecture 21

Linear programming III

Literature

  • DPV 7.6

May 20

Lecture 22

P vs NP and problems that are just too hard

Literature

May 23

Lecture 23

Non-deterministic polynomial time II

Literature

May 28

Lecture 24

Non-deterministic polynomial time III

Literature

May 30

Lecture 25

Non-deterministic polynomial time IV

Literature

June 2

Lecture 26

TBD

Literature

June 4

Lecture 27

TBD

Literature

June 5

Question & Answer

Question & Answer

  • With Professor Nirkhe. Location: CSE2 G01. Time: 5:30pm-7:30pm.
  • No planned topic. Bring any questions you have or topics you want clarified.
  • Recording quality may be wanting as it will be on whiteboard.

June 6

Lecture 28

TBD

Literature

June 12

Final

Final

  • Location: Lecture Hall CSE2 G20
  • Time: 2 Hour. Starts exactly at 2:30 and ends exactly at 4:30.
  • Disability Requests that are approved will be in TBD starting at 2:30 as well.
  • Contact head TAs to arrange your specific requirements. Otherwise we assume you are taking standard exam despite your disability requests.
  • You may bring 1 8.5x11 page of notes (both sides); see the final coversheet for details.
†. Course schedule and contents subject to change and will be announced throughout the term.