Tutorials on Randomized Algorithms, summer semester 24/25

Tutorials for the lecture of prof. J. Sgall. We will be solving nice exercises about randomization and its use to design efficient algorithms and data structures.

Scheduled on Thursdays at 12:20 in S10 (scheduled during "Úmluva").

If you have any question, drop an email to vesely (zavináč) iuuk.mff.cuni.cz or ask before/during/after the tutorial. It'd be great if you ask during the class once something is not clear to you. If you wish to discuss a topic individually during a consultation, let me know.

What we have done

20 Feb	Introductory examples: Monty Hall problem, getting a fair coin from a biased coin (with unknown bias), opening up envelopes with unknown rewards, and simple examples of Markov chains. Exercises (covered 1, 2, and 4; zero knowledge graph isomorphism will be next time; exercises 5-8 are extra).
27 Feb	Collecting coupons and walking randomly on graphs. Exercises. First homework assignment appeared in the Owl postal system. Link to access the course in the Owl system for HW.
6 Mar	Complexity classes for randomized algorithms. Exercises (covered the first three)
13 Mar	Chernoff bounds. Exercises (we covered all of them, though the last one only briefly)
20 Mar	Yao's principle and lower bounds. Exercises (we discussed the first three in detail and the fourth briefly)
27 Mar	Eigenvalues of adjacency matrices. Exercises (we discussed the first three in detail)
3 Apr	Eigenvalues of adjacency matrices and expanders II. Exercises (we discussed all three, though the last one just quickly)
10 Apr	Eigenvalues of powers of a graph. Estimation of quantities by randomized algorithms, namely, for counting satisfying assignments of a DNF formula. Exercises (we discussed all four)
17 Apr	Substituted by Petr Chmel: Counting matchings. Exercises (discussed the first four)
24 Apr	Substituted by Jiří Sgall: Streaming algorithms. Exercises (discussed the first two to three)
1 May	Public holiday
8 May	Public holiday, again :-)

Credit for tutorials ("zápočet")

To get the credit in SIS, you need to obtain at least 2/3 of points from homework assignments (expected around 60 points). Additionally, I may give bonus homework (not counting towards the limit) and also for activity during the tutorials. You will have at least 13 days (before the beginning of the tutorial in two weeks) for each homework given. One correction of your solution is possible even after the deadline (unlimited before the deadline but I won't look at it every day ...).

Homework assignments are in the Postal Owl system; link to access the course..