Room wwh317, Tuesday 5-6:50
Text: The Probabilistic Method, Noga Alon and Joel Spencer, John Wiley & Sons, 3rd 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.
The language of preference for the course is LaTeX but all forms of TeX are accepted. Please clarify which form of TeX is being used. Please send both the .tex and the .pdf files.
A special note: Working together on the assignments is encouraged. However, everyone must hand in their separate assignment and it should be written in cribe
February -1 (thanks Krzysztof!) pdf
February 7 (thanks George!) jpg jpg jpg jpg jpg jpg jpg jpg jpg jpg
Assignment 1 due January 31, in class postscript LaTeX pdf
Assignment 2 due February 7, in class postscript LaTeX pdf
Assignment 3 due February 14, in class (NOTE: Problem 2 NOT to be handed in) postscript LaTeX pdf
Assignment 1 due January 31, in class postscript LaTeX pdf
Assignment 2 due February 7, in class postscript LaTeX pdf
