Home | Bookmarks | Papers | Blog |

3:30 - 4:45 TuTh, 103B3 Engineering Hall

Announcement

Office hours: 17:00-19:00 on Thursday, DCL 2111. Please email if you plan to come.

1. | 1/16 |
Introduction Course summary (PS, tex) Notes - Quicksort/BSP (ps, tex) |

2. | 1/18 | Minimum Cut (1.1), Las Vegas and Monte Carlo algorithms (1.2) |

3. | 1/23 | Game Tree Evaluation (2.1), Occupancy problems (3.1) The Markov and Chebyshev Inequalities (3.2) |

4. | 1/25 | Markov's inequality, Chebyshev's inequality, Lazy Select (html, ps, latex ) |

5. | 1/30 | 3.4 Two point sampling, 3.6 The coupon collector's problem (3.6.!), |

6. | 2/1 | 4.1 Chernoff Bound, 4.2 Routing in a parallel computer (html, ps, latex). |

7. | 2/6 | 4.3 A wiring problem - random rounding |

8. | 2/8 | 8.2 Random Treaps |

9. | 2/13 | 8.3 Skip list, 8.4 Hash Tables |

10. | 2/15 | 8.5 Hashing with O(1) Search Time |

11. | 2/20 | PAC Learning and VC Dimension |

12. | 2/22 | Proving the existance of small epsilon-nets (Alon & Spencer 220-230) |

13. | 2/27 | Small epsilon-nets - cont' + range-searching data-structures |

14. | 3/1 | 9.2 Another variant of quick-sort and Convex hull in the plane. Introduction to Clarkson abstract framework. |

15. | 3/6 | The exponential decay lemma, clarkson bound on the sum of squared expectations, cuttings, convex-hull in 3d. |

16. | 3/8 | Vertical decomposition, Diameter in 3d. |

3/13 | Spring Vacation | |

3/15 | Spring Vacation | |

17. | 3/20 | 9.10 Linear programming. |

18. | 3/22 | 10.1 All pairs shortest path |

19. | 3/27 | Witnesses for binary matrix multiplication |

20. | 3/29 | Faster Min-Cut algorithm |

21. | 4/3 | Linear time MST |

22. | 4/5 | Number theory and algebra |

23. | 4/10 | Primality testing |

24. | 4/12 | Sphere in higher dimensions and its concentration of mass |

25. | 4/17 | The Johnson Lindenstraus lemma |

26. | 4/19 | The probabilistic method - 5.1, 5.2 |

27. | 4/24 | 5.3 Expanding graphs, 5.3.1 Probability Amplification |

28. | 4/26 | MAX CUT/MAX 2SAT Approximation using Semi-definite programming |

29. | 5/1 | Approximate NN search and locality sensitive hashing |

1. | Due: 2/6 | Homework 1 (PS, tex) |

2. | Due: 2/20 | Homework 2 (PS, tex) |

3. | Due: 3/6 | Homework 3 (PS, tex) |

4. | Due: 3/20 | Homework 4 (PS, tex) |

5. | Due: 4/10 | Homework 5 (PS, tex) |

6. | Due: 5/10 | Homework 6 (PS, tex) |

- 2.2, 2.3, 3.6.2, 3.6.3
- 4.4 Martingles

- Main book:

Randomized Algorithms, Motwani and Raghavan.

Errata. - The probabilistic method, 2ed, Noga Alon and Joel Spencer.

- The Discrepancy Method, Bernard Chazelle.
- Computational Geometry: An Introduction Through Randomized Algorithms, Ketan Mulmuley

- Randomized Algorithms, CMU.
- Randomized Algorithms, UIUC 1999.
- Randoimized Algorithms, Duke.