Analysis of Algorithms

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
CLR, Chapter 13-15, 18
Splay handout from Duke
Competitive analysis
Paging


Conclusions

Wrapup

Acknowledgments



Data Structures

Binary and binomial heaps
ppt  pdf

Fibonacci heaps
ppt   pdf

CLR Chapter 20

No comments: