The course uses probabilistic techniques to dessign and analyze algorithms for solving problems.
Loosely we will follow Mitzenmacher-Upfal: "Probability and Computing" Cambridge UP 2005 .
Assumptions: Basic probability theory and a course on algorithm design (at the level of Dasgupta, Papadimitriou, Vazirani: Algorithms)
Administrative triviaEvaluation:
Below you will fing scanned version of my slides for
some of the classes
notes. May contain typos and ambiguities.
Slides in pdf:
Fingerprint Fingerprint Techniques (Pdf)
Expectation and random variables (Pdf)
Programming assignments: