## 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.