Documents

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

  • W 6 Sep — Graphs

  • F 8 Sep — BFS (definitions, properties, asymptotics)
    K&T 3.2, 3.3

  • M 11 Sep — BFS applications (bipartite)
    K&T 3.4, 3.5

  • W 13 Sep — DAGs and topological sorting
    K&T 3.6

Greedy Algorithms

  • F 15 Sep — topological sorting, intro to Dijkstra’s algorithm
    K&T 4.4

  • M 18 Sep — no class

  • W 20 Sep — Dijkstra’s algorithm
    K&T 4.4

  • F 22 Sep — Dijkstra’s algorithm, minimum spanning trees
    K&T 4.5

  • M 25 Sep — Implementing Prim’s MST algorithm
    K&T 4.6

  • W 27 Sep — Implementing Kruskal’s MST algorithm, Union-Find structure
    K&T 4.6

Exam 1