|
CPS237 |
|||
|
|
Spring
2006 |
|
RANDOMIZED ALGORITHMS |
Current Homework:
Class Schedule and Class Notes:
|
Date |
Topic |
Readings |
|
|
Room D243 11:40am-12:55pm Thurs Jan 12 |
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 |
|
|
Room D243 11:40am-12:55pm Tues Jan 17 |
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 V_cking'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 |
|
|
Room D243 11:40am-12:55pm Thurs Jan 19 |
Probabilistic
Analysis: Tail Inequalities: Notes(JR): Probability
Theory Review, PDF Notes(SH): On the Occupancy problem, Markov and Chebyshev
inequalities PDF 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.
(Ch. 2.3, 3.1-3.4, 4.1) Notes(LS):
Approximate #DNF(cont.) and the
Chernoff Bound PS
PDF Notes(LS): Further
Applications of Chernoff Bounds PS
PDF Notes(CG): Chernoff bounds: coin flipping and randomized
rounding. (Ch. 4.1) PDF |
MR: Ch. 3: pages 43-66 Ch. 4: pages 67-100 MU: Ch. 2-4 |
|
|
Room D243 11:40am-12:55pm Tues Jan 24 |
The Probabilistic Method: Introduction and Random
Graphs Notes(AB):Randomized
rounding, probabilistic method. ( Ch. p 4.3, 5.1, 5.2, 5.6) Notes(AS): Basics regarding expectations and the
probabilistic method PS
PDF Notes(AS): The vertex-connectivity of random graphs PS
PDF Notes(CG): Random Graphs and use of Markov and Chebychev Tail
Bounds PDF
(Ch. 8.5, 3.2) Notes(SH): Introduction
to the probabilistic method PDF |
MR:Ch. 5: pages 101-126 MU: Ch. 6 |
|
|
Room D243 11:40am-12:55pm Thurs Jan 26 |
The Probabilistic Method: 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(DK): Median
finding, Routing. PS,
PDF
Notes(SH): Chernoff
Bound (4.1), Routing in a parallel computer (4.2) PDF |
MR: Ch. 5: pages 101-126 Chap 4.2,5.4 Chap 4.4,5.4.5 MU: Ch. 4 & 6 |
|
|
Room D243 11:40am-12:55pm Tues Jan 31 |
The Probabilistic Method: Conditional Probabilities
and Estimators Notes(DK): Method
of conditional Probabilities and Expectations, Fingerprinting. PS,
PDF
Notes(SH): Conditional
probabilities, and further examples 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] |
MR: Ch. 5: pages 101-126 MU: Ch. 6 |
|
|
Room D240 1pm-2:15pm Wends Feb 1 |
Making Randomized Algorithms Determionistic: Lovasz
Local Lemma and Expanders Notes(SH): Lovasz Local
Lemma and Applications PDF Notes(AS): The Lov'asz 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 Auxillary 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 |
|
|
Room D243 11:40am-12:55pm Thurs Feb 2 |
Randomized Parallel Algorithms:
Sorting & Maximal Independent Set Notes(DK): Parallel
Algorithms, Sorting. PS,
PDF Notes(DK): Maximal
Independent Set, Perfect Matching. PS,
PDF |
MR: Ch. 12: pages 335-367 |
|
|
Room D243 11:40am-12:55pm Tues Feb 7 |
Randomized Parallel
and Distributed Algorithms: Perfect Matching 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 |
|
|
Room D240 1pm-2:15pm Wends Feb 8 |
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 |
|
|
Room D243 11:40am-12:55pm Thurs Feb 9 |
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 |
|
|
Room D243 11:40am-12:55pm Tues Feb 14 |
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 |
|
|
Room D243 11:40am-12:55pm Thurs Feb 16 |
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 |
|
|
Room D243 11:40am-12:55pm -Tues Feb 21 |
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(SH): VC Dimension PDF |
MR: Ch. 9: pages 234-277 |
|
|
Room D243 11:40am-12:55pm Thurs Feb 23 |
Randomized Geometric Algorithms and Linear Programming: Notes(DK): Trapezoidal
decomposition/search structure, Linear Programming. PS,
PDF Notes(DK): Linear
Programming. PS,
PDF |
MR: Ch. 9: pages 234-277 |
|
|
Room D243 11:40am-12:55pm -Tues Feb 28 |
Probabilistic Games: Introduction
to Equilibria Theory and Algorithms |
Handouts |
|
|
Room D243 11:40am-12:55pm Thurs March 2 |
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 |
|
|
Room D243 11:40am-12:55pm Tues March 7 |
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 |
|
|
Room D243 11:40am-12:55pm -Thurs March 9 |
Markov and Monte Carlo Simulations of Physical and Chemical
Systems: The Metropolis and Gillespi Algorithms Example: randomized simulations of self-assembled DNA
nanostructures and DNA motors |
handouts |
|
|
March 11-19 |
Spring Break
– Do a few random things ! |
|
|
|
Room D243 11:40am-12:55pm Tues March 21 |
Markov
Chains & Random Walks: Expanders,
eigenvalues, and Rapid Mixing Notes(AB):existence
of expanders. Notes(AB):intro
to approx counting| Notes(AB):Expanders,
eigenvalues, and rapid mixing. Randomized Clique hardness reduction. PS,
PDF. Notes(AB): Eigenvalue
Separation for Rapid Mixing PS,
PDF. o Jerrum & Sinclair
survey on rapid mixing o Many other surveys/lecture notes
by Mark Jerrum. o Chapter on
Coupling by Mark Jerrum |
MR: Ch. 6: pages 127-160 Chap 5.3, 6.2 MU: Ch. 7, 10, & 11 |
|
|
Room D240 1pm-2:15pm Wends March 22 |
Markov
Chains & Random Walks: Mixing Times: 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 Conductance: Notes(SV): Isoperimetric
coefficients and mixing times PS,
PDF Notes(SV): Conductance,
PS,
PDF |
MR: Ch. 6: pages 127-160 MU: Ch. 7, 10, &
11 |
|
|
Room D243 11:40am-12:55pm Thurs March 23 |
Markov Chains & Random Walks: Randomized Approximate
Counting Notes(LS): Approximate
counting vs. approximate sampling
PS
PDF Notes(LS): Sampling
graph colorings PS
PDF Notes(DK): Sampling
using Markov Chains, Eigenvalues. PS,
PDF Notes(DK): Markov
Chains for Sampling, Volume, Expander Walks, Coupling. PS,
PDF 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 |
|
|
Room D243 11:40am-12:55pm Tues March 28 |
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 |
Handouts and MR: Ch. 11: pages 306-334 MU: Ch. 7, 10, &
11 |
|
|
Room D243 11:40am-12:55pm -Thurs March 30 |
Compact
Sensing: Randomized
Algorithms and Lower Bounds in Group Testing |
Handouts |
|
|
Room D243 11:40am-12:55pm Tues April 4 |
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 |
MR: Ch. 14: pages 392-428 |
|
|
Room D240 1pm-2:15pm Wends April 5 |
Introduction to Quantum Algorithms: Primary Readings: Notes (UV): Quantum
Gates & Circuits Notes(RC): First Part of Introduction
to Quantum Information Processing: Qubits, Measurement, Quantum Teleportation Notes(UV): Reversible
Computation Mathematical Overview: Notes(UV): Hilbert
Spaces & Tensor Products Secondary Readings: Notes(MM): Quantum
Operations Notes(MM): Dirac
Notation & Quantum Mechanics Notes(MM): Quantum
Gates, Tensor Operations, Probabilistic Computation via Quantum Computation Notes(MM): Quantum
Measurement Notes(MM): Qubit
Operations Notes(RC): Approximate
Universal Sets of Gates Notes(RC): Quantum
Nonlocality: Bell Inequality |
|
|
|
Room D243 11:40am-12:55pm Thurs April 6 |
Quantum
Algorithms using the Fourier Basis, Introduction Fourier Basis: Notes(UV): Fourier
Basis & Quantum Simulations of a Probabilistic Circuit Secondary Reading on Probabilistic Simulation: Notes(MM): Probabilistic
Computation via Quantum Computation Simon’s
Algorithm: Notes(UV): Simon's
Quantum Algorithm Notes(UV): Fourier
Transforms & Simon's Quantum Algorithm |
|
|
|
Room D243 11:40am-12:55pm Tues April 11 |
Quantum
Algorithms using the Fourier Basis, Cont Review of Quantum Fourier Transform: 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 |
|
|
Room D240 1pm-2:15pm Wends April 12 |
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 |
|
|
Room D240 1pm-2:15pm Thurs April 13 |
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 |
|
|
|
Room D243 11:40am-12:55pm Tues April 18 |
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 |
Handouts |
|
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