CSE591 Randomized/Approximation Algorithms

Homework 3

• Aldous and Fill. Reversible Markov Chains and Random Walks on Graphs, Online Book.

Problem 4

• A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensk. The electrical resistance of a graph captures its commute and cover times. STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing. ACM. February 1989

Homework 2

Problem 1

• Chernoff bound

Problem 2

• Union bound, (Boole's inequality)

---

Term: FALL 08 Name: CSE 591 Section: 79117 Instructor: KONJEVOD Course ID: 79117 Location: TEMPE CAMPUS

REQUIRED RANDOMIZED ALGORITHMS Look Inside This Book Author: MOTWANI

ISBN: 9780521474658

Used: $51.75    New: $69.00   

Quantity:

REQUIRED APPROXIMATION ALGORITHMS Look Inside This Book Author: VAZIRANI

ISBN: 9783540653677

Used: $37.50    New: $50.00   

Quantity: