|
CPS237 |
|||
|
|
Spring
2008 |
|
RANDOMIZED ALGORITHMS |
Current Homework:
Class Schedule and Class Notes:
|
Date |
Topic |
Readings |
|
|
1:00PM -
2:30PM Wed Jan 9 |
Introduction
to Randomized Algorithms: Examples
of Randomized Algorithms Notes(DK):
Introduction to Randomized Algorithms: Examples of Quicksort,
BSP, MINCUT PS,
PDF 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. Notes(SH):
Introduction - QuickSort, started to
speak about BSP PDF Notes(CG):
Introduction PDF |
MR: Ch. 1, pp 3-27 MU: Ch. 1 |
|
|
1:00PM -
2:30PM Fri Jan 11 |
Probabilistic Analysis: Moments and
Deviations: Notes(JR):
Probability
Theory Review, PDF Notes(DK):
Coupon
collecting, stable marriage, Markov inequality.
PS,
PDF
(Ch. 3.2,3.5,3.6) Notes(AB):Balls'n'boxes,
lower bounds, Spencer's graduation game. (Ch.t 2.2.2, 3.1, 3.6, 5.1) Notes(CG):
Balls and bins: the power of two
choices PDF o
Berthold Vicking's presentation
on the power of two choices. |
MR: Ch. 3: pages 43-66 Appendix
B: pp 433-437 Appendix
C: Basic Probability Theory, pages 438-446 MU: Ch. 2-4 |
|
|
1:00PM -
2:30PM Mon Jan 14 |
Probabilistic
Analysis: Tail Inequalities: Notes(JR):
Probability
Theory Review, PDF Notes(AB): probabilistic inequalities, Chernoff bounds,
complexity classes. PS,
PDF.
(Ch. 2.3, 3.1-3.4, 4.1) Notes(CG): Chernoff bounds: coin flipping and randomized
rounding. (Ch. 4.1) PDF Notes(AS): Facts related
to the Chernoff-Hoeffding bounds PS PDF Applications
of Tail Bounds: Notes(SH):
On the Occupancy problem, Markov and
Chebyshev inequalities PDF Notes(SH):
(First part of lecture) Chernoff Bound
(4.1) PDF Notes(DK): Chebyshev,
Two point sampling, Chernoff. PS,
PDF Notes(LS): Approximate #DNF(cont.) and the Chernoff Bound PS
PDF |
MR: Ch. 3: pages 43-66 Ch. 4: pages 67-100 MU: Ch. 2-4 |
|
|
1:00PM -
2:30PM Wed Jan 16 |
The
Probabilistic Method: Connectivity of Random
Graphs: Notes(AS): Basics regarding
expectations and the probabilistic method PS PDF Notes(SH):
(First part of lecture) Introduction to
the probabilistic method PDF Notes(CG): Random Graphs and use of Markov and Chebychev Tail
Bounds PDF
(Ch. 8.5, 3.2) Notes(AS): The
vertex-connectivity of random graphs PS PDF |
MR:Ch. 5: pages 101-126 MU: Ch. 6 |
|
|
1:00PM -
2:30PM Fri Jan 18 |
The
Probabilistic Method: Randomized Algorithm Design Applications Notes(SH):
Randomized selection (Ch. 3.3) and
Two-point sampling (Ch. 3.4) PDF Notes(CG):
Sampling, Medians of Means method and
DNF counting (Ch. 11.1, 11.2) PDF Notes(SH):
The Coupon Collector's Problem (Ch. 3.5,
3.6) PDF Notes(SH):
(Later part of lecture) Routing in a
parallel computer (4.2) PDF Notes(DK): Median
finding, Routing. PS,
PDF
|
MR: Ch. 5: pages 101-126 Chap 4.2,5.4 Chap 4.4,5.4.5 MU: Ch. 4
& 6 |
|
|
1pm-2:30pm Wed Jan 23 |
The
Probabilistic Method: Conditional Probabilities and Estimators Notes(AB):Randomized
rounding, probabilistic method. ( Ch. p 4.3, 5.1, 5.2, 5.6) Notes(SH):
(Later part of lecture) Randomized
Rounding for Maximum Satisfiability PDF Notes(SH): Conditional probabilities, and further examples PDF Notes(AS): Pessimistic
estimators PS PDF Notes(DK): Method
of conditional Probabilities and Expectations, Fingerprinting. 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] |
MR: Ch. 5: pages 101-126 MU: Ch. 6 |
|
|
1:00PM - 2:30PM Fri Feb 1 |
Making
Randomized Algorithms Deterministic: Lovasz Local Lemma and Expanders Notes(SH):
Lovasz Local Lemma and Applications PDF Notes(AS): The Lovasz
Local Lemma and Packet Routing PS PDF o
The Leighton Maggs Rao
paper:
sections 2 and 3.1 are the relevant ones. Notes(DK): Expanders,
Wiring, MAX SAT. PS,
PDF Auxiliary
Lectures: Lipschitz
functions, Martingales, and Concentration of Measure. (MR 4.4, AS Ch.7 (2nd ed.)) Notes(CG):
Martingales, concentration of geometric
TSP (AS Ch.7 (2nd ed.)) o
Some notes on the TSP
argument. PDF Notes(SH):
Martingles (Ch. 4.4) PDF Notes(SH):
Martingles II( Ch. 4.4) PDF |
MR: Chap 4.4 Ch. 5: pages 101-126 Ch. 5.3,5.4 |
|
|
1:00PM -
2:30PM Mon Feb 4 |
Randomized Parallel Algorithms: Sorting, Maximal Independent
Set & Perfect Matching Notes(DK): Parallel
Algorithms, Sorting. PS,
PDF Notes(DK): Maximal
Independent Set, Perfect Matching. PS,
PDF Notes(LS):
Finding a perfect matching:
Rabin-Vazirani and Mulmuley-Vazirani-Vazirani PS
PDF Notes(CG):
Finding perfect matchings randomly PDF
[MR 7.3, 12.4] |
MR: Ch. 12: pages 335-367 |
|
|
1pm-2:30pm Wends Feb 6 |
Randomized
Data Structures: Universal and perfect Hashing Notes(JR): Universal
Hash Functions PS, PDF Notes(DK): More
Hashing, Perfect Hash Families, Treaps.
PS,
PDF Notes(AB):Universal
and perfect hashing. |
MR: Ch. 8: pages 197-233 Ch. 8.4, 8.5 MU: Ch. 13 |
|
|
1:00PM -
2:30PM Wends Feb 13 |
More
Randomized Data Structures: Skip Lists, Treaps Notes(LA): Hashing,
Skip Lists PS,
PDF Notes(CG):
Occupancy Problems and Hashing PDF (Ch. 3.1, 3.6, 8.4) Notes(DK):
Treaps,
Skip Lists, Shortest Paths. PS,
PDF Notes(DK): More
Hashing, Perfect Hash Families, Treaps.
PS,
PDF Notes(DK):
Treaps,
Skip Lists, Shortest Paths. PS,
PDF |
MR: Ch. 8: pages 197-233 Ch:
10: pages 278-288 |
|
|
1:00PM -
2:30PM Fri Feb 15 |
Randomized
Graph Algorithms: Shortest Paths, Min Cuts, and Min Spanning Trees Notes(DK): Shortest
Paths. PS,
PDF
Notes(DK): Minimum
cuts, minimum spanning trees. PS,
PDF Notes(DK): Minimum
spanning trees. PS,
PDF Notes(AB):A
monte-carlo Minimum Cut algorithm. Notes(DK): Polling,
Minimum Cut, Transitive Closure. PS,
PDF Notes(SH):
Minimum Cut (1.1, 10.2) PDF Notes(CG):
Randomized Min Cut and related topics PDF
(Ch. 1.1, 10.2) |
MR: Ch.9: pages 234-277 Ch. 1.1, 10.2 |
|
|
11:30AM -
1:00PM Mon Feb 18 |
Randomized Online Algorithms: Notes(AB):Randomized
algorithms for on-line problems. (Ch. 13.1, 13.3) Reading:
MR Ch 13: pages 368-391 |
MR: Ch. 13: pages 368-391 |
|
|
1:00PM -
2:30PM Mon Feb 18 |
Randomized
Geometric Algorithms: Introduction Notes(DK):
Randomized
incremental construction, Trapezoidal decomposition. PS,
PDF Notes(DK): Point
location, Randomized incremental construction. PS,
PDF o
Raimund Seidel's survey
on backwards analysis. o
Ken Clarkson's survey
on randomness in geometric algorithms. o
Survey
by Pankaj Agarwal and Sandeep Sen. Notes(DK): Trapezoidal
decomposition/search structure, Linear Programming. PS,
PDF Notes(DK): |