Random Alborithms (Fall 2019, Master Inovation and
Research in Informatics)
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.
Slides of lectures will appear in this
page as the course progeresses.
Administrative trivia:
Solution to Final and grades
Final solution (pdf)
RA finald
grades (pdf)
Below you will find a copy of the slides for
some of the classes
notes. May contain typos and ambiguities.
Slides in pdf
1 Basic probability
(Pdf)
2 Fingerprint
Fingerprint Techniques (Pdf)
3 Expectation
and random variables (Pdf)
Concentration
Balls-Bins and
Hashing (Pdf)
Markov Chains (pdf)
Homework
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)
Solutions
toall in Hmw6 (pdf)
ASSIGNMENT 1
Assignment1
(pdf)
Interesting papers to read
Trailing
the dovetail shuffle to its lair
Past exam and solution
Quiz1-2018
Sol
Quiz1-2018 (pdf)
quiz2-18RA.pdf
quiz2-18-SOL.pdf
Final-18.pdf
Final18-sol.pdf