*** New for 2006: Analysis of Breadth First Search on Random Graphs
Text: The Probabilistic Method, Noga Alon and Joel Spencer, John Wiley & Sons, 2nd Edition. This course could be called The Probabilistic Method or The Erdos Method or, my favorite, Erdos Magic. We will study a variety of random structures with particular emphasis on Random Graphs. We will analyze various algorithms on those structures. We will use random structures to prove the existence of combinatorial objects (this is, more specifically, the Erdos Magic) such as colorings, tournaments, and simultaneous roundoffs. We give methods (2nd moment method, Janson's Inequality, ...) that allow us to estimate and/or bound probabilities, particularly very small probabilities. (A basic knowledge of probability -- expectation, variance, binomial distribution and the like, would be helpful but is not required.) (Also, a prior acquaintance with Discrete Mathematics - graphs, trees, colorings, ... - would be helpful but is not required.) A common theme throughout the course is asymptotic estimation. There will be plenty of big-Ohs, little-ohs, Thetas and Omegas. Grading: Last time we had assignments every week or so that were part of the grade plus an oral exam at the end. I expect to do the same this time around.