Difference between revisions of "CSE591 Randomized/Approximation Algorithms"
From esoterum.org
(New page: -------------------------------------------------------------------------------- Term: FALL 08 Name: CSE 591 Section: 79117 Instructor: KONJEVOD Course ID: 79117 Location: TEMPE CAMPUS...) |
|||
| (7 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | === Homework 4 === | ||
| + | '''Problem 1''' | ||
| + | *Bonnie Berger, Peter W. Shor [http://delivery.acm.org.ezproxy1.lib.asu.edu/10.1145/330000/320203/p236-berger.pdf?key1=320203&key2=6247278221&coll=portal&dl=ACM&CFID=10949569&CFTOKEN=52685087 | ||
| + | Approximation alogorithms for the maximum acyclic subgraph problem]. SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, January 1990. | ||
| + | |||
| + | |||
| + | |||
| + | === Homework 3 === | ||
| + | *[http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f05/Site/Materials/Lectures/Lecture23/lecture23.ppt Random walks, universal traversal sequences, and the complexity of maze problems], slides | ||
| + | *Aldous and Fill. [http://stat-www.berkeley.edu/users/aldous/RWG/book.html Reversible Markov Chains and Random Walks on Graphs], Online Book. | ||
| + | '''Problem 1''' | ||
| + | *(?) Peter G. Doyle J. Laurie Snell. [http://www.ee.technion.ac.il/~adam/FUN/RWEN.pdf Random walks and electric networks]. Version 35 January 2000 Copyright (C) 1999, 2000 Peter G. Doyle and J. Laurie Snell Derived from work(s) Copyright (C) 1984 The Mathematical Association of America | ||
| + | |||
| + | '''Problem 4''' | ||
| + | * A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensk. [http://delivery.acm.org.ezproxy1.lib.asu.edu/10.1145/80000/73062/p574-chandra.pdf?key1=73062&key2=6517224221&coll=portal&dl=ACM&CFID=10949569&CFTOKEN=52685087 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''' | ||
| + | *[http://en.wikipedia.org/wiki/Chernoff_bound Chernoff bound] | ||
| + | '''Problem 2''' | ||
| + | *[http://en.wikipedia.org/wiki/Boole's_inequality Union bound], (Boole's inequality) | ||
| + | |||
Latest revision as of 01:11, 8 December 2008
Homework 4
Problem 1
- Bonnie Berger, Peter W. Shor [http://delivery.acm.org.ezproxy1.lib.asu.edu/10.1145/330000/320203/p236-berger.pdf?key1=320203&key2=6247278221&coll=portal&dl=ACM&CFID=10949569&CFTOKEN=52685087
Approximation alogorithms for the maximum acyclic subgraph problem]. SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, January 1990.
Homework 3
- Random walks, universal traversal sequences, and the complexity of maze problems, slides
- Aldous and Fill. Reversible Markov Chains and Random Walks on Graphs, Online Book.
Problem 1
- (?) Peter G. Doyle J. Laurie Snell. Random walks and electric networks. Version 35 January 2000 Copyright (C) 1999, 2000 Peter G. Doyle and J. Laurie Snell Derived from work(s) Copyright (C) 1984 The Mathematical Association of America
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
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:
