Karel Král

kralka (AT) iuuk.mff.cuni.cz

Tutorials. Credit requirements. Useful links.

NDMI025 - Randomized Algorithms

Thursday 12:20, zoom

Lectures prof. Jiří Sgall

Tutorials are held in English (unless everybody speaks Czech).

Solved exercises

Solved examples (last update Jun 3)

What happened

Jun 3

PCP and inaproximability, notes tutorial13.pdf (the solutions contain literature for that)

May 27

Notes tutorial12.pdf

Min sketch from Section 5.4 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf

We will finish the gap preserving reductions and hardness of approximation next time: chapter 16 (has section on max label cover) of The Design of Approximation Algorithms (Williamson, Shmoys) available online

May 20

Hashing, uses etc tutorial11.pdf.

3blue1brown blockchain (video on youtube)

a use of Merkle tree (video on youtube)

https://en.wikipedia.org/wiki/Merkle_tree

May 13

Derandomization, Yao, hash functions tutorial10.pdf.

May 6

Electrical networks theory tutorial9.pdf.

Apr 29

Coupling again, intro to streaming algorithms.

Problems from tutorial8.pdf

Homework 2 hw2.pdf, by May 16

Apr 22

Matchings, IP protocol for permanent.

Problems from tutorial7.pdf

Apr 15

Counting, permanents and determinants, matchings.

Problems from tutorial6.pdf

Apr 8

Equivalence of norms (inequalities with Euclidean and Manhattan norm), coupling lemma and mixing time on a hypercube.

Problems from tutorial5.pdf

Apr 1

First three problems from tutorial4.pdf

Next tutorial we start with the fourth problem. You might want to review Courant-Fischer (wikipedia)

Distributed discrete log algorithm (half page self-contained proof): Breaking the Circuit Size Barrier for Secure Computation Under DDH, Boyle, Gilboa, Ishai Section 3.1.

Mar 25

Complexity classes, Chernoff bound and amplification.

Tutorial notes: tutorial3.pdf

Homework 1 hw1.pdf, by April 10

Mar 18

Second tutorial notes: tutorial2.pdf

Mar 11

First tutorial notes: tutorial1.pdf

Mar 4

We start next week (most probably).

Credit requirements

See SIS:

To pass the tutorials it is required to get at least a half of total points for homeworks assigned during the semester conditioned on regular attendance. If the student does not attend the tutorials regularly, two thirds of total points will be required. Due to the requirements, additional attempts to pass the tutorial are not allowed. The exam is oral. The requirements correspond to the syllabus as covered by the lectures. Passing the turorials is required before taking the exam.