|
CPS237 |
|||
|
|
Spring
2002 |
|
RANDOMIZED ALGORITHMS |
Current Homework:
HM1 due Jan 23: M&R: problems
1.1,1.2,1.3,1.4,1.5,1.8,1.10
Class Schedule and Class Notes:
|
Date |
Topic |
Readings |
|
|
Wed Jan 9 |
No Class (Makeup extra lecture Jan 16) |
|
|
|
Fri Jan
11 |
Introduction
to Randomized Algorithms: Notes(DK): Introduction to
Randomized Algorithms: Examples of Quicksort, BSP, MINCUT
PS,
PDF |
Ch. 1, pp 3-27 Appendix B: pp 433-437 |
|
|
Mon Jan 14 |
More
Examples of Randomized Algorithms:
Notes(JR):: Probability Theory Review Notes(AB):Why Ranomized Algs
and Example: partitioning a
3-colorable graph. Notes(AB): Examples: Secretly computing an average, k-wise
independence, linearity of expectation, quicksort. |
Ch. 1, pp 3-27 Appendix B: pp 433-437 |
|
|
Wed Jan 16 (extra lecture) |
Randomized
Game-Theoretic Techniques: Notes(DK): Complexity theory, game
tree evaluation. PS, PDF (Chapt.
2.1,2.2) Notes(DK): Adelman's Theorem, game
theory, lower bounds. PS, PDF (Chapt. 2.3) |
Ch. 2: pages 28-42 |
|
|
Fri Jan
18 |
Probabilistic
Analysis: Moments and Deviations: Notes(DK): Coupon collecting, stable
marriage, Markov inequality. PS, PDF (Chapt.
3.2,3.5,3.6) Notes(AB):Balls'n'boxes, lower
bounds, Spencer's graduation game. (Chapt 2.2.2, 3.1, 3.6, 5.1) |
Ch. 3: pages 43-66 Appendix C: Basic Probability Theory,
pages 438-446 |
|
|
Mon Jan
21 |
No Class (Martin Luther Holiday) |
|
|
|
Wed Jan
23 |
Probabilistic
Analysis: Tail Inequalities: Notes(DK): Chebyshev, Two point
sampling, Chernoff. PS, PDF Notes(AS): Facts related
to the Chernoff-Hoeffding bounds PS PDF Notes(AB): probabilistic inequalities, Chernoff bounds,
complexity classes. PS, PDF. (Chap. 2.3, 3.1-3.4, 4.1) |
Ch. 3: pages 43-66 Ch. 4: pages 67-100 |
|
|
Fri Jan
25 |
The
Probabilistic Method: Notes(AB):Randomized rounding,
probabilistic method. (Chap 4.3, 5.1, 5.2, 5.6) Notes(AS): Basics
regarding expectations and the probabilistic method PS
PDF |
Ch. 5: pages 101-126 |
|
|
Mon Jan 28 |
The
Probabilistic Method: Notes(DK): Median finding, Routing. PS, PDF (Chapt 4.2,5.4) Notes(AS): The Lov'asz
Local Lemma and Packet Routing PS PDF (Chapt 4.4,5.4.5) |
Ch. 5: pages 101-126 |
|
|
Wed Jan 30 |
The
Probabilistic Method: Notes(DK): Method of conditional
Probabilities and Expectations, Fingerprinting. PS, PDF Notes(AS): Pessimistic
estimators PS PDF Advanced Reading: Notes(AB):Analysis
of local optimization algorithms. Also
[Aldous-Vazirani, FOCS '94, pages 492-501] and [Dimitriou-Impagliazzo, STOC
'96, pages 304-313] |
Ch. 5: pages 101-126 |
|
|
Wed Feb 6 |
The
Probabilistic Method: Notes(DK): Expanders, Wiring, MAX
SAT. PS, PDF (Chapt 5.3,5.4) |
Ch. 5: pages 101-126 |
|
|
Fri Feb
8 |
Randomized
Algebraic Methods Notes(JR): Hashing Polynomials
and Algebraic Equations PS,
PDF Notes(DK): Fingerprints by
Polynomials, Perfect Matching, Hashing. PS, PDF.
|
Ch. 7: pages 161-196 |
|
|
Wed Feb 13 |
Randomized
Data Structures: Notes(JR): Universal Hash
Functions PS, PDF Notes(DK): More Hashing, Perfect
Hash Families, Treaps. PS, PDF Notes(AB):Universal and
perfect hashing. (Chap. 8.4, 8.5) |
Ch. 8: pages 197-233 |
|
|
Fri Feb
15 |
Randomized
Data Structures: Notes(DK): Treaps, Skip Lists,
Shortest Paths. PS, PDF |
Ch. 8: pages 197-233 |
|
|
Mon Feb 18 |
Randomized
Data Structures: Notes(DK): Shortest Paths. PS, PDF |
Ch. 8: pages 197-233 |
|
|
Fri Feb
22 |
Geometric
Algorithms: Notes(DK): Point location,
Randomized incremental construction. PS, PDF |
Ch. 9: pages 234-277 |
|
|
Mon Feb
25 |
Randomized
Geometric Algorithms: Notes(DK): Randomized incremental
construction, Trapezoidal decomposition. PS, PDF |
Ch. 9: pages 234-277 |
|
|
Wed Feb 27 (extra lecture) |
Randomized
Geometric Algorithms and Linear
Programming: Notes(DK): Trapezoidal decomposition/search structure,
Linear Programming. PS, PDF |
Ch. 9: pages 234-277 |
|
|
Fri
March 1 |
Randomized
Geometric Algorithms and Linear
Programming: Notes(DK): Linear Programming. PS, PDF |
Ch.9: pages 234-277 |
|
|
Mon March 4 |
Randomized
Graph Algorithms: Notes(DK): Minimum cuts, minimum
spanning trees. PS, PDF Notes(DK): Minimum spanning trees. PS, PDF Notes(AB)::A monte-carlo Minimum Cut algorithm.
(Chap. 1.1, 10.2) Notes(DK): Polling, Minimum Cut, Transitive Closure.
PS, PDF |
Ch. 10: pages 278-305 |
|
|
Wed March 6 |
Markov
Chains and Random Walks: Notes(DK): Markov Chains, Random
Walks. PS, PDF Notes(AB):Random walks and cover times.
(Chap 6.1, 6.3, 6.4, 6.5) |
Ch. 6: pages 127-160 |
|
|
week March 11 |
No Class (Spring Break Week) |
|
|
|
Wed March 20 3:45-5pm |
Markov
Chains and Random Walks: Notes(DK): Sampling using Markov
Chains, Eigenvalues. PS, PDF Notes(DK): Markov Chains for
Sampling, Volume, Expander Walks, Coupling. PS,
PDF |
Ch. 6: pages 127-160 |
|
|
Fri
March 22 |
Markov
Chains and Random Walks: Notes(AB):Resistive networks,
existence of expanders. (Chap 5.3, 6.2) Notes(AB):Expanders, eigenvalues, and rapid mixing. Randomized
Clique hardness reduction. PS, PDF. Notes(AB):Amplifying randomness via
random walks on expanders. (Chap 6.7, 6.8) Notes(LS): Expander graphs and pseudorandom number generators
for BPP PS PDF |
Ch. 6: pages 127-160 |
|
|
Mon March 25 |
Markov
Chains and Random Walks: Notes(AB):intro to approx counting| Noga's quick proof. PS,
PDF. (Chap 11.1) Notes(DK): DNF Counting. PS, PDF Notes(LS): Approximate #DNF(cont.) and the Chernoff Bound PS PDF |
Ch. 11: pages 306-334 |
|
|
Wed March 27 |
Randomized Approximate Counting: Notes(AB):Approximating the Permanent, part 1.
Chap 11.3) Notes(AB):Approximation the
Permanent, part 2. |
Ch. 11: pages 306-334 |
|
|
Mon
April 1 |
No Class (on travel; give extra lecture Feb 27) |
|
|
|
Fri
April 5 |
No Class (on travel; give
extra lecture April 17) |
|
|
|
Weds April 10 |
Randomized Parallel and Distributed Algorithms: Notes(DK): Coupling, Parallel Algorithms, Sorting. PS, PDF |
Ch. 12: pages 335-367 |
|
|
Fri
April 12 |
Parallel and
Distributed Algorithms: Notes(DK): Maximal Independent Set,
Perfect Matching. PS, PDF Notes(LS): Finding a maximal independent set is in NC PS PDF |
Ch. 12: pages 335-367 |
|
|
Mon
April 15 |
Randomized Online Algorithms: Notes(AB):Randomized
algorithms for on-line problems. (Chap 13.1, 13.3) Reading:
Motwani & Raghavan Chapter 13: pages 368-391 |
Ch. 13: pages 368-391 |
|
|
Weds
April 17(extra lecture) |
Randomized Number Theory and Algebra: Notes(AB):Intro to number-theoretic
algorithms. (Chap 14) |
Ch. 14: pages 392-428 |
|
|
Fri
April 19 |
|
Ch. 14: pages 392-428 |
|
Note: Class lecture notes indicated by DK, AB, AS,
LS were prepared by the following (and used with their prior permissions):
Notes(AB):
due to Avrim Blum, CMU
Notes(AS): due
to Aravind Srinivasan, Univ. Maryland
Notes(LS):
due to Leonard
Schulman, Georgia Institute of Technology