CS444-Spring '08. HANDOUTS AND NOTES

Handouts

1. The Floyd-Rivest Algorithm

Notes

CS206 Course Notes on Probability (W. Steiger, 2001)

• 1. Set Theory; Basic Ingredients of Probability; Conditional Probability and
  Independence. (and as .pdf).
  
• 2. Counting and Combinatorics). (and as .pdf).
  
• 3. Random Variables, Independence; Bernoulli Trials; Expectation;
  Coupon Collecting. (and as .pdf).
  
• 4. Variance; Tchebycheffs Inequality; Law of Large Numbers; Generating Functions. (and as .pdf).
  
• 5. Random walk on the integers, positive paths, the ballot theorem, recurrence (and as .pdf).

CS174 (U. Cal. Berkeley) Course notes on Probability and Combinatorics (Prof. Alistair Sinclair, '98)

• 1. Elementary probability. Many applications to the balls-in-boxes experiment. (and as .pdf).
  
• 2. More probability and application to random permutations. (and as .pdf).
  
• 3. Threshold phenomena in random graphs. (and as .pdf).
  
• 4. The fingerprinting idea and applications in verifying identities and in string matching.

Class Summaries (what was covered in each class)

• Class 19, April 3, 2008, The Karp-Rabin algorithm.
• Class 20, April 8, 2008, Random graphs and threshold functions. Max-clique for G(n,1/2).
• Class 21, April 10, 2008, For G in G(n,1/2), the max clique size is close to
  2log n - 2loglog n with prob -> 1. Begin max 3-sat.
• Class 22, April 15, 2008, derandomization of random assignment for 3-sat via the method of
  conditional probabilities. Papadimitriou's alg for 2-sat, and the random walk on the integers.
• Class 23, April 17, 2008, proof that if there is a satisfying assignment of a 2-sat formula, the expected number of steps
  for Papadimitriou's algorithm to terminate is O(n^2). Review properties of random walk on the integers.
  Begin primality testing.
• Class 24, April 22, 2008, Fermat's compositeness test, its cost via repeated squaring, Carmichael numbers,
  a Monte-Carlo compositeness test using Fermat, that succeeds for non-Carmichael composites.
• Class 25, April 24, 2008, non-trivial squareroots of 1 and Millers test; the Miller-Rabin algorithm.
• Class 26, April 29, 2008, summary for primality testing. Begin random number generation: Linear congruential
  generators; testing generators; Marsaglia's thm.
• Class 27, May 1, 2008, composite generators as antidote for sparsity in R^d. Linear programming, the randomized, incremental algorithm, backward analysis.