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) **

- Mitzenmacher and Upfal: Probability and Computing, Cambridge UP, 2005
- Moore and Merten: The Nature of Computation, Oxford UP, 2011.

**Administrative trivia: **

**Administrative triviaEvaluation: **

- 50% Exams
- 50% Individual presentation of solutions to problems, programminf assignments.
- New: The deadline for Assignment 2 is the December 15th

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):

* Class notes 1: IntroducciÃ³ (Pdf)*

* Class notes 2:
Basic probability and randomized algorithms (Pdf)*

* Class notes 3:
Karger's Randomized algorithm (Pdf)*

* Class notes 4: Expectation and Random Variables (Pdf)*

* Class notes 5:
Concentration (1) (Pdf)*

* Class notes :
Chernoff, Load Balancing and Sampling (Pdf)*

* Class notes:
Balls and Bins, (Pdf)*

* Class notes:
Bloom filter and Graphs, (Pdf)*

* Class Slides:
Phase Transition and Complex Nets, (Pdf)*

Solutions to some problems:

Problem sheets:

Programming assignments: