## 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

### 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. Direct counting method.

• W 29 Mar — More amortized analysis. Accounting method.

• F 31 Mar — Binomial trees and heaps

• M 3 Apr — Potential method, splay trees

• W 5 Apr — Analysis of splay trees

### Exam 2

• F 7 Apr — Exam 2
Covering divide & conquer, dynamic programming, network flow, and amortized analysis (through 29 March)

### Intractability

• M 10 Apr — Reductions
K&T 8.1

• W 12 Apr — Reductions, decision problems

• F 14 Apr — SAT, 3-SAT
K&T 8.2

• M 17 Apr — NP, NP-completeness
K&T 8.3

• W 19 Apr — CIRCUIT-SAT is NP-complete
K&T 8.4

• F 21 Apr — special guest lecture

### Strings, matching, and linear sorting

• M 24 Apr — Rabin-Karp matching

• W 26 Apr — Rabin-Karp matching, bucket sort

• F 28 Apr — radix sort

• M 1 May — radix sort