Algorithm and Complexity Analysis
Download Slides here:
Download Slides here:
Topic
|
Slides
|
In-class Demos
|
Reading
|
Introduction
| |||
Stable matching
| |||
Greedy algorithms
| |||
Greed
|
CLR, Chapter 17
| ||
Shortest path
|
CLR, Chapter 25
| ||
Minimum spanning tree
|
CLR, Chapter 24
| ||
Divide-and-conquer paradigm
| |||
Divide and conquer
|
CLR, Chapter 4, 8
31.2, 35.4 | ||
Linear time selection
|
CLR 10.3
| ||
Fast Fourier transform
|
CLR, Chapter 32
| ||
Dynamic programming
| |||
Dynamic programming
|
CLR, Chapter 16
| ||
Negative cycle
|
CLR, Chapter 26
| ||
Reductions
| |||
Linear time reductions
|
CLR, Chapter 31.5
| ||
Maximum flow
|
CLR, Chapter 27.1, 27.2
| ||
Reductions to max flow
|
CLR, Chapter 27.3
| ||
Polynomial time reductions
|
CLR, Chapter 36
| ||
Intractability and coping with intractability
| |||
NP completeness
|
Longest path song by Daniel Barrett
|
CLR, Chapter 36
| |
Approximation algorithms
|
CLR, Chapter 37
survey paper (optional) | ||
Linear programming
|
Scientific American handout
| ||
Beyond worst case complexity
| |||
Average case analysis
|
CLR, Chapter 8
| ||
Amortized analysis
| |||
Competitive analysis
|
Paging
| ||
Conclusions
| |||
Wrapup
| |||
Acknowledgments
| |||
Data Structures
| |||
Binary and binomial heaps
| |||
Fibonacci heaps
|
CLR Chapter 20
| ||