Documents

Assignments

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

Lectures

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

LECTURE NOTES PDF

Introduction to Algorithms

  • W 18 Jan — Stable matchings and the Gale-Shapley algorithm
    K&T Ch. 1, including Solved Exercises

  • F 20 Jan — Proof of Gale-Shapley algorithm correctness

  • M 23 Jan — Data representations for Gale-Shapley
    K&T Ch. 2

  • W 25 Jan — Asymptotic analysis

  • F 27 Jan — Asymptotic analysis II (Complexity zoo)

  • M 30 Jan — Largest sum subinterval problem

Graphs

  • W 1 Feb — More LSS, intro to graphs (representation, paths, cycles, trees)
    K&T 3.1

  • F 3 Feb — BFS (definitions, properties, asymptotics)
    K&T 3.2, 3.3

  • M 6 Feb — Bipartite graphs, directed graphs
    K&T 3.4, 3.5

  • W 8 Feb — DAGs and topological sorting
    K&T 3.6

Greedy Algorithms

  • F 10 Feb, M 13 Feb — Dijkstra’s Algorithm
    K&T 4.4

  • W 15 Feb — Kruskal’s and Prim’s MST algorithms
    K&T 4.5

  • F 17 Feb — Implementing Prim’s algorithm
    K&T 4.6

  • W 22 Feb — Implementing Kruskal’s algorithm, Union-Find structure
    K&T 4.6

Exam 1

  • F 24 Feb — Exam 1
    Covering asymptotic analysis, graphs, and greedy algorithms

Divide and Conquer

  • M 27 Feb — Integer multiplication, Master Theorem
    K&T 5.1, 5.2, 5.5

  • W 1 Mar — Matrix multiplication, FFT intro
    K&T 5.6

  • F 3 Mar — FFT [ slides ]
    K&T 5.6

Dynamic Programming

Network Flow

  • M 13 Mar — Network flow I (definitions, Ford-Fulkerson algorithm)
    K&T 7.1

  • W 15 Mar — Network flow II (F-F algo examples, flows and cuts)
    K&T 7.2

  • F 17 Mar — Network flow III (max flow/min cut theorem)
    K&T 7.5, 7.6

Spring break

Amortized analysis

  • M 27 Mar — Intro to amortized analysis. Aggregate method, accounting method

  • W 29 Mar — Binomial trees and heaps

  • F 31 Mar — Potential method, splay trees

  • M 3 Apr — Analysis of splay trees

Exam 2

  • W 5 Apr — Exam 2
    Covering divide & conquer, DP, network flow, and a bit of amortized analysis

Intractability

  • F 7 Apr — Reductions
    K&T 8.1

  • M 10 Apr — SAT, 3-SAT
    K&T 8.2

  • W 12 Apr — NP, NP-completeness
    K&T 8.3

  • F 14 Apr — CIRCUIT-SAT is NP-complete
    K&T 8.4

  • M 17 Apr — Lots of things are NP-complete
    (3-SAT, SAT, independent set, vertex cover, set cover, travelling salesman, hamiltonian circuit)
    K&T 8.4, 8.5

Strings and matching

  • W 19 Apr — Rabin-Karp matching

  • F 21 Apr — Rabin-Karp matching II

  • M 24 Apr — Radix sort

  • W 26 Apr — Suffix tries I

  • F 28 Apr — Suffix tries II

  • M 1 May — Suffix tries III

Final exam

  • M 8 May — Final exam (Cumulative)