COMP 250P Syllabus, Spring 2007

Text: Probability and Computing: Randomized Algorithms and Probabilistic Analysis
by Michael Mitzenmacher and Eli Upfal
Cambridge University Press

A text I have used previously is available online at: Probability and Algorithms

Some other books:

Probability and Statistics with Reliability, Queueing, and Computer Science Applications, 2nd Edition
by Kishor Trivedi
Wiley-Interscience, 2001

Randomized Algorithms
by Rajeev Motwani and Prabhakar Raghavan
Cambridge University Press, 1995

Topics: We will cover much of the material in Chapters 1-9.

Possible additional topics:

• Types of randomized algorithms: Monte Carlo, Las Vegas, Sherwood, RP, BPP
• Conditional probabilities, Markov chains, Hidden Markov Models
• Pseudorandom numbers
• Simulated annealing
• Genetic algorithms
• Primality testing and factoring
• Queuing theory
• An index page linking some further topics

Topics actually covered:

• Jan 18: Sections 1.1-2 Axioms, verifying polynomial equality
• Jan 23: Sections 1.3-4 Verifying matrix multiplication, min-cut
• Jan 23: Sections 2.1 -3 Expectation and Bernoulli and binomial random variables