Random Alborithms (Fall 2018, Master Inovation and Research in Informatics)

Grades Final Grade

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)

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

Administrative triviaEvaluation:

• 50% Exams
• 50% Individual presentation of solutions to problems, programminf assignments.

Below you will fing scanned version of my slides for some of the classes notes. May contain typos and ambiguities.


Slides in pdf:

Basic probability (Pdf)

Fingerprint Fingerprint Techniques (Pdf)

Expectation and random variables (Pdf)

Concentration

Balls-Bins and Hashing (Pdf)

Markov Chains (pdf)

Hmw 1(pdf)

Solutions to*in Hmw1 (pdf)

Hmw 2 (pdf)

Solutions to*in Hmw2 (pdf)

Hmw3 (pdf)

Solutions to*in Hmw3 (pdf)

Hmw4 (pdf)

Solutions to*in Hmw4 (pdf)

Hmw5 (pdf)

Solutions to*in Hmw5 (pdf)

Hmw6 (pdf)

Programming assignments:

Assignment 1(pdf) (Dec 13)