CS444-Spring '08. WHAT TO READ BEFORE CLASS
This shows what I intend to cover in each class, and may be used
as a guide for preparation. After the class I will edit the entries so
they become a "diary" of what was actually covered.
1. January 22, 2008: Described course. Began review of concepts
and notations from Probability: random experiment, sample space,
events, probability measure.
2. January 24, 2008: Conditional probablity and independence;
Examples, including sampling r times with and without replacement from a set of
n elements; the Monte Hall game; k-wise independence.
3. January 29, 2008: Mutual independence, repeated trials,
derangement probability for random permutations via
inclusion/exclusion; Random Variables and Expectation; frequency
function; the method of indicators; an O(n) algorithm for random
permutation of 1,...,n; and O(n+r) algorithm for a random placement of
r balls into n boxes.
4. January 31, 2008: Floyd-Rivest (Las Vegas) algorithm for
selection, and its analysis.
5. February 5, 2008: Finish analysis, tuning parameters. Coupon
collecting.
6. February 7, 2008: Min-Cut problem, Kargers' contraction
algorithm for unweighted graphs.
7. February 12, 2008: Boosting in Monte-Carlo; gives an O(n^4)
with negligible failure probability. Adapting Kargers algorithm for
weighted graphs. The Karger-Stein Fast-cut algorithm.
8. February 14, 2008: Finish analysis: O(n^2) time and space,
succeeds with probability at least c/log(n). Now Boost. Begin Poisson
as limit of Binomials and Poisson heuristic.
9. February 19, 2008: Poisson heuristic and several
applications to balls-in-boxes. Sharp threshold for coupon
collecting. Monte-carlo and approximation of integrals.
10. February 21, 2008: Some facts from continuous
probability. Von-Neumann's inverse distribution function method for
generating non-uniform random numbers. The Seigel-Zambuto randomized
algorithm for approximating a definite integral.
11. February 26, 2008: Random graphs and the two models. Edge
threshold for a random graph on n vertices to be connected. Begin
graphical evolution.
12. February 28, 2008: Begin probabilistic method: probabilistic
lower bound for the Ramsey number R(k,k);
13. March 4, 2008: Continue. Tournaments and Hamiltonian paths;
existence of a tournament with at least n!/2^(n-1) Hamiltonian paths.
14. March 6, 2008: Big cuts; every graph with n vertices and m
edges has a cut of size at least m/2. Discussed special case of
covering set
(bigshots). The secretary problem.
15. March 11, 2008: conclusion. Begin fingerprinting, and
examples: verifying univariate polynomial identities.
16. March 13, 2008: Multivariate polynomial identities: the
Schwartz-Zippel algorithm and the Schwartz-Zippel thm bounding the algorithms
error probability.
17. March 25, 2008: Planar graphs; Eulers' relation; the crossing
number of a graph, the crossing lemma and its probabilistic proof.
(*) March 27, 2008: MIDTERM
18. April 1, 2008: Verifying a database via fingerprints. Begin
string matching.
19. April 3, 2008: The Karp-Rabin string matching algorithm.
20. April 8, 2008: Random graphs and threshold functions. The
size of the largest clique in G (in the G(n,1/2) model).
21 April 10, 2008: Finished computation showing clique number is
asymptoticlly sure to be near log([n/log n]^2).
Satisfiability: alg
for 3-sat formulas that satisfies at least 7/8 of the clauses.
22. April 15, 2008: Method of conditional probabilities to
derandomize random assignment of a 3-sat formula.
Papadimitrious'
prababilistic 2-sat algorithm and the random walk on the integers.
23. April 17, 2008: Proof that the expected number of steps for
Papadimitriou's algorithm for 2-sat is O(n^2), assuming
there is a
satisfying assignment. Review properties of random walk on the
integers, with and without reflecting barriers/absorbing states.
Begin
primality testing.
24. April 22, 2008: Fermats compositeness test, Fermats "little"
thm, its cost via repeated squaring. Carmichael numbers (composites
that usually fool Fermat); a Monte-Carlo algorithm for
compositeness based on Fermat.
25. April 24, 2008: Non-trivial squareroots of 1 mod(n); Miller's
test, Rabin's lemma, the Miller-Rabin algorithm.
26. April 29, 2008: Other randomized and deterministic
compositeness and primality tests - summary. Generating pseudo random
numbers - Von Neumann's method, Linear congruential
generators. Testing random number generators; Marsaglia's
theorem. Generating random objects, e.g. binary trees, polygons, etc.
27. May 1, 2008: Linear programming in R^2 and the randomized
incremental algorithm for it. Backward analysis.