Tutorials on Randomized Algorithms, summer semester 22/23

Tuesday 10:40

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.

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

Note about the room: we will be using either S7 or S321, which is the corridor of KAM/IUUK opposite to S3. Before every tutorial, I will specify the place in the table below (hopefully I'll be able to tell you the place a week in advance). If we are in S7, then I'll write that on the board in S321; in the other case, S7 will be occupied by somebody else.

14 Feb	S321	Introductory examples: Monty Hall problem, opening up envelopes with unknown rewards, graph isomorphism interactive zero knowledge protocol, and simple examples of Markov chains. Exercises (3f and 3g will be next time; the PDF is edited since printing before the tutorial).
21 Feb	S7	substituted by Jiří Sgall: Collecting coupons and walking randomly on graphs. Exercises. First homework assignment appeared in the Owl postal system.
28 Feb	S7	Plan: complexity classes for randomized algorithms and eigenvalues recap. Exercises (We went over the first three and explained that the adjacency matrices of d-regular graphs have all eigenvalues in [-d,d].
7 Mar	S7	substituted by Jiří Sgall: Eigenvalues continued and Chernoff bounds. Exercises
14 Mar	S321	Eigenvalues of complete and complete bipartite graphs, and expansion properties of random bipartite graphs. Covered problems (the other ones on the printouts will be next time).
21 Mar	S7	Eigenvalues and graph properties, bounding the Euclidean norm in terms of the ell_1 norm (sum of absolute values), total variation distance between distributions, and a variant of the Coverage algorithm for counting satisfying assignments for DNF formulas. Covered problems (we'll finish the last one next time)
28 Mar	S6	Approximate counting of satisfying assignments and matchings. Covered problems (the last one will be next time)
4 Apr	S7	Approximate counting of matchings. Problems (covered the first two; the third one about estimating permanent is not so important and follows just from properties of expectation, and the last one about an interactive protocol for permanent is quite involved, you can look for instance at lecture notes from Edinburgh Univ.)
11 Apr	S7	Coupling of Markov chains. Exercises (from sampling colorings, we have done only 3a) so far, the rest will be next time).
18 Apr	S7	Streaming algorithms: intro (sums and averages), finding the majority element (if there's any) and the Misra-Gries algorithm to find heavy hitters. Outline of the tutorial. Study sources: Apart from lecture notes by A. Chakrabarti, there's a nice book Small Summaries for Big Data by G. Cormode and K. Yi.
25 Apr	S307	Plan: lecture on streaming algorithms by Jiří Sgall, room is S307 (the office of Prof. Sgall).
2 May	-	Cancelled (no lecture before & I'm away)
9 May	S7	Streaming algorithms: K Minimum Values sketch and Count-Min sketch. Outline of the tutorial (we didn't cover the last two questions about Count-Min).
16 May	S7	Yao's principle and lower bounds. Covered problems

Credit for tutorials

To get credit in SIS, you need to obtain at least 2/3 of points from homework assignments. This turns out to be 59 points in the end. 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. After the deadline, the assignments will be for a half of points, but I can give you a hint.

Homework assignments are in the Postal Owl system; drop me an email if you don't know what is it, or need the enrollment token.