|
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): Linear
Programming. PS,
PDF Notes(SH):
VC Dimension PDF |
MR: Ch. 9: pages 234-277 |
|
|
1:00PM -
2:30PM Wed Feb 20 |
Randomized
Complexity Theory and Game-Theoretic Techniques for Lower Bounds: Notes(DK): Complexity
theory, game tree evaluation. PS,
PDF
(Ch. 2.1,2.2) Notes(DK): Adelman's
Theorem, game theory, lower bounds. PS,
PDF
(Ch. 2.3) Notes(SH): Las Vegas and Monte Carlo algorithms (Ch. 1.2),
Complexity Classes (Ch. 1.5) PDF Notes(CG): Complexity classes, Identity checking. PDF
[Ch. 7.1, 7.2, 7.4] Notes(CG): Lower bounds on randomized algorithms. PDF
[Ch. 2.1, 2.2] Notes(LS):
Application of Games to Randomized Distributed
Communication PS
PDF |
MR: Ch. 2: pages 28-42 MU: Ch. 13 |
|
|
1:00PM -
2:30PM Wed Feb 27 |
Introduction to Game Theory and Nash Equilibrium Definitions of
Probabilistic Games: Introduction
by Theodore L.
Turocy (Texas A&M University)
& Bernhard von Stengel (London School of Economics) Equilibrium
Theory: Introduction [PDF] by Amit
Agarwal & Vikas Bansal |
|
|
|
1:00PM -
2:30PM Fri Feb 29 |
Sparse
Approximations of Game Strategies:
Randomized & Deterministic Algorithms Constant Factor Approximation of Nash Equilibrium: [PPT] - 0.5 Approximation of Nash
Equilibria in polynomial time
[PDF] - 0.38
Approximation of Nash Equilibria in polynomial time [PDF] Epsilon Factor Randomized Approximation of Nash Equilibrium: - Althofer‘s
Randomized Approximation via Algebraic Simplification [PDF] - Lipton’s Epsilon
Approximation of Nash Equilibria in subexponential time [PDF] Epsilon Factor Deterministic Approximation of Nash
Equilibrium: - Hofmeister-Lefmannt Deterministic Approximation via Pessimistic Estimators [PDF] - Young Greedyt Deterministic
Approximation via Pessimistic
Estimators [PDF] |
|
|
|
1:00PM -
2:30PM Fri Feb 29 Mon March 3 |
Markov
Chains & Random Walks: Introduction & Relation to Electrical Networks Notes(DS): Random
Walks and Electrical Networks, PDF o
The book Random Walks and
Electric Networks by Doyle and
Snell is online. Notes(DK): Markov
Chains, Random Walks. PS,
PDF Notes(AB):Random
walks and cover times. Notes(AB):Resistive
networks |
MR: Ch. 6: pages 127-160 Chap 6.1, 6.3,
6.4, 6.5 MU: Ch. 7, 10,
& 11 +handouts |
|
|
Wed n March 5 |
Markov
Chains & Random Walks:
Mixing Times, Coupling
& Conductance: Notes(LS):
Markov Chain Monte Carlo. Mixing times PS
PDF Notes(SV):
Basic
parameters, PS, PDF Coupling: Notes(LS): Markov Chain Monte Carlo. Strong stationary times,
coupling PS
PDF Notes(LS): Strong stationary time for riffle shuffle PS
PDF o Also, Chapter on
Coupling by Mark Jerrum Conductance: Notes(SV): Isoperimetric
coefficients and mixing times PS, PDF Notes(SV): Conductance,
PS, PDF |
MR: Ch. 6: pages 127-160 Chap 5.3, 6.2 MU: Ch. 7, 10,
& 11 |
|
|
March 10-14 |
Spring
Break – Do a few random things ! |
|
|
|
1:00PM - 2:30PM Wed March 19 |
Markov
Chains & Random Walks: Randomized
Approximate Counting Notes(LS): Approximate counting vs. approximate
sampling PS
PDF Exponential Rate of Decay Near Stationary PS
PDF Exponential Rate of Decay Near Stationary PS
PDF Using
Coupling Analysis for Mixing Rate for
Random Walk on Grid and Shuffle PS
PDF Using
Coupling Analysis for Sampling graph
colorings PS
PDF Notes(DK): Sampling
using Markov Chains, Eigenvalues. PS,
PDF
Markov
Chains for Sampling, Volume, Expander Walks, Coupling. PS,
PDF Auxiliary Lectures: Notes(SV): Algorithms
based on random walks, PS, PDF Notes(AB):Amplifying
randomness via random walks on expanders. (Chap 6.7, 6.8) |
MR: Ch. 11: pages 306-334 MU: Ch. 7, 10, & 11 |
|
|
1:00PM -
2:30PM Mon March 24 |
Markov and Monte Carlo Simulations of
Physical and Chemical Systems: -The Metropolis
and Gillespi Algorithms -
Randomized simulations and Stochastic Analysis of Self-assembled DNA
Nanostructures and DNA Motors |
|
|
|
1:00PM -
2:30PM Wed March 26 |
Markov Chains & Random Walks:
Permanent and Volume of a Convex Polyhedron Notes(LS): Approximating the Permanent PS
PDF Notes(AB):Approximating
the Permanent, part 1. Chap 11.3) Notes(AB):Approximation
the Permanent, part 2. Notes(SV): Convex
optimization I., PS, PDF Notes(SV): Convex
optimization II PS, PDF Notes(SV): The
ball walk, PS, PDF Notes(SV): Hit-and-run,
PS, PDF |
MR: Ch. 14: pages 392-428 |
|
|
1:00PM -
2:30PM Wed April 2 |
Randomized
Techniques in Number Theory & Algebra: Hashing Polynomials Notes(CG): Identity checking. PDF
[Ch. 7.1, 7.2, 7.4] Notes(JR): Randomized
Tests for Polynomial Equality PS
PDF |
|
|
|
1:00PM -
2:30PM Wed April 9 |
Introduction
to Quantum Algorithms, Part I: Primary Readings: Notes(RC):
First Part of Introduction
to Quantum Information Processing: Qubits, Measurement, Quantum Teleportation Notes (UV): Quantum
Gates & Circuits Mathematical Overview: Notes(UV): Hilbert
Spaces & Tensor Products Secondary Readings: Notes(MM):
Quantum
Operations Notes(MM):
Quantum
Gates, Tensor Operations, Probabilistic Computation via Quantum Computation Notes(MM):
Dirac
Notation & Quantum Mechanics Notes(MM):
Quantum
Measurement Notes(MM):
Qubit
Operations |
|
|
|
1:00PM -
2:30PM Mon April 11 |
Introduction
to Quantum Algorithms, Part II: Primary Readings: Notes(UV): Reversible
Computation Notes(UV): Fourier
Basis & Quantum Simulations of a Probabilistic Circuit Notes(MM):
Probabilistic
Computation via Quantum Computation Secondary Readings: Notes(RC):
Approximate
Universal Sets of Gates Notes(RC):
Quantum
Nonlocality: Bell Inequality |
|
|
|
1:00PM -
2:30PM Mon April 14 |
Quantum
Algorithms using the Fourier Basis, Cont Simon’s
Algorithm & Review of
Quantum Fourier Transform: Notes(UV): Simon's
Quantum Algorithm Notes(UV):
Fourier
Transforms Shor’s
Factorizion Algorithm: Notes(UV):
Shor's
Quantum Factoring Algorithm: Preliminaries Notes(UV):
Shor's
Quantum Factoring Algorithm: Details Notes(RC): Introduction
to Quantum Information Processing,
Quantum Period Finding Algorithm Kitaev’s
Factorization Algorithm via Approx. Eigenvalues of Unitary Matrices: Notes(UV):
Kitaev's
Factoring Algorithm Notes(MM): Quantum
Factoring Quantum
Algorithm for Discrete Log: Notes(UV):
Quantum
Algorithm for Discrete Log |
Handouts: Shor's
Quantum Factoring Algorithm Preprint |
|
|
1:00PM -
2:30PM Wends April 16 |
Quantum
Searching Grover's
Quantum Search Algorithm: Notes(MM): Quantum
Searching Notes(MM): Quantum
Searching (modified
version of same lecture) Notes(RC): Introduction
to Quantum Information Processing, Quantum Search Algorithm |
Handouts: Grover's
Quantum Search Algorithm Reprint Overveiw
of Grover's Quantum Search Algorithm Tight
Bounds for Quantum Search Grover's
Quantum Median Algorithm |
|
|
|
Quantum
Algorithms: Error Correction Notes(UV):
How
Sensitive is a Quantum Algorithm to Pertubations? Notes(MM): Quantum
Error Correction Notes(MM): Quantum
Error Correction continued Notes(AL): Quantum
Error Correction |
|
|
|
|
Quantum
Information Processing & Quantum Cryptography Notes(RC): Quantum
Cryptography: Key Distribution & Commitment Notes(RC): Quantum
Teleportation Notes(RC): Quantum
Communication Complexity Notes(RC): Quantum
Fingerprints |
|
|
Note: Class lecture notes indicated by LA, AB, DS,
DK, JR, LS, AS, SV, UV. SH, GC were prepared by the following:
Notes(AB):
due to Avrim Blum, CMU
Notes(DS): due to Peter G.
Doyle and J Laurie Snell, AMS free software
Notes(GC):
due to Anupam Gupta and Shuchi Chawla,
CMU
Notes(AL): due to Andrew
J. Landahl, University of New Mexico
Notes(MM):
due to Michele Mosca, University of Waterloo
Notes(RC):
due to Richard Cleve, University of Calgary
Notes(LS):
due to Leonard
Schulman, Georgia Institute of Technology
Notes(AS): due
to Aravind Srinivasan, University of
Maryland
Notes(SV): due
to Santosh S. Vempala, MIT
Notes(UV): due to Umesh Vazirani, UC Berkeley
Notes(SH): due to Sariel
Har-Peled, UIUC