The course uses probabilistic techniques to dessign and analyze algorithms for 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)
Below you will fing scanned version of my class
notes. May contain typos and ambiguities. There are just a sketch of
what I plan to explain on the blackboard
Copy of my personal class notes (pdf):
Solutions to some problems: