Analysis of Algorithms

Topic	Slides	In-class Demos	Reading
Introduction
Stable matching	pdf	Gale-Shapley
Greedy algorithms
Greed	pdf	Activity selection  Greed is good	CLR, Chapter 17
Shortest path	pdf		CLR, Chapter 25
Minimum spanning tree	pdf	Red rule, blue rule	CLR, Chapter 24
Divide-and-conquer paradigm
Divide and conquer	pdf	Counting inversions	CLR, Chapter 4, 8 31.2, 35.4
Linear time selection	pdf		CLR 10.3
Fast Fourier transform	pdf		CLR, Chapter 32
Dynamic programming
Dynamic programming	pdf		CLR, Chapter 16
Negative cycle	pdf		CLR, Chapter 26
Reductions
Linear time reductions	pdf		CLR, Chapter 31.5
Maximum flow	pdf	Augmenting path  Breadth-first search	CLR, Chapter 27.1, 27.2
Reductions to max flow	pdf		CLR, Chapter 27.3
Polynomial time reductions	pdf		CLR, Chapter 36
Intractability and coping with intractability
NP completeness	pdf	Longest path song by Daniel Barrett	CLR, Chapter 36
Approximation algorithms	pdf	List scheduling	CLR, Chapter 37 survey paper (optional)
Linear programming	pdf		Scientific American handout
Beyond worst case complexity
Average case analysis	pdf		CLR, Chapter 8
Amortized analysis	pdf	Dynamic table Splay trees	CLR, Chapter 13-15, 18 Splay handout from Duke
Competitive analysis	pdf	Paging
Conclusions
Wrapup	pdf		Top 10 algorithms
Acknowledgments	pdf
Data Structures
Binary and binomial heaps	ppt  pdf		Binomial heap applet
Fibonacci heaps	ppt   pdf		CLR Chapter 20