Assignments

Many of the assignments are gratefully based on materials from Brent Heeringa.

Activities/Lectures

Suggested readings are in italics. K&T refers to Algorithm Design by Kleinberg and Tardos.

Introduction to Algorithms

Graphs

Greedy Algorithms

Exam 1

Divide and Conquer

Dynamic Programming

  • M 9 Oct — Intro to dynamic programming

  • W 11 Oct — DP example: hi/lo-stress jobs

  • M 16 Oct — 2D dynamic programming

  • W 18 Oct — Matrix chain multiplication

  • F 20 Oct — Matrix chain mult; Floyd-Warshall algorithm (all-pairs shortest paths with arbitrary weights + cycle detection)

Network flow

  • M 22 Oct — Introduction to network flow

  • W 24 Oct — Ford-Fulkerson algorithm

  • F 26 Oct — Network flow applications

  • M 29 Oct — Max flow/min cut theorem

Amortized analysis

Exam 2

Intractability

  • M 12 Nov — Intro to reductions
    K&T 8.1

  • W 14 Nov — Reductions

  • F 16 Nov — SAT, 3-SAT
    K&T 8.2

  • M 19 Nov — NP, NP-completeness
    K&T 8.3

  • M 26 Nov — CIRCUIT-SAT is NP-complete
    K&T 8.4

  • W 28 Nov — NP-hard video games

Strings, matching, and linear sorting

Final exam