Introduction to Algorithms

Thinking like a computer scientist

Writing algorithms and graph traversal

Reading: KT: 3-3.6, DPV: 4.2-4.3

Section 01

Graph traversal, DFS, BFS, applications

Directed graphs and greedy algorithms

Reading: KT: 4-4.2, DPV: 5-5.1

Greedy approximation and graph algorithms

Reading: KT: 12.4,4.4-4.7, DPV: 4.4-4.7

Section 02

More greedy algorithms

No lecture

Minimum spanning trees

Reading: KT: 5-5.4, DPV: 2.2-2.4

Section 03

Divide and conquer

Multiplication algorithms

Reading: KT: 5.5-5.6, DPV: 2.5-2.6

Derandomization, quick sort, and stable matching I

Reading: KT: 13.5, DPV: 2.4

Section 04

Stable matching II and midterm review

Reading: KT: 1

No lecture

Dynamic programming I

No worksheet. Section will be a midterm/early pset postmortem

Dynamic programming II

Reading: KT: 6,6.2,6.6, DPV 6.3

Dyanmic programming III

Reading: KT: 6.4, 11.8, DPV 6.4

Dynamic programming IV

Section 06

Network Flow

Reading: KT: 7-7.2

No lecture

Max Flow/Min Cut

Reading: KT: 7.2-7.5

Section 07

Network flow in polynomial time

Reading: KT: 7.5-7.7,7.12

Network flow applications

Non-deterministic polynomial time I

Reading: KT 8.1-8.4, DPV 8.1-8.3

Section 08

Non-deterministic polynomial time II

Non-deterministic polynomial time III

Reading: KT 8, DPV 8

Non-deterministic polynomial time IV

Section 09

Linear programming I

Reading: DPV 7-7.3

Linear programming II

Linear programming III

Section 10

Final Review / Epilogue