# Algorithms, Probability, and Computing (2012)

Lecturers: Emo Welzl, contact person (CAB G39.2), Thomas Holenstein (CAB G23.1), Ueli Maurer (CAB H19.2), Angelika Steger, (CAB G38), Peter Widmayer (CAB H39.2) Timon Hertli (CAB G39.3), contact assistant. Sandro Coretti (CAB H17), Vincent Kusters (CAB G37.2), Robin Moser (CAB G19.2), assistants. Monday 13:15-15:00 CAB G11, Tuesday 14:15-16:00 CAB G51; Important: the first lecture is on Tuesday, September 18 the first exercise session is on Wednesday, September 19 8CP for Informatik Bachelor and Mathematik Bachelor (252-0209-00L, 4V + 2U + 1A) For interested students, there is now an optional honours part giving additional 2CP. The honours part consists of one additional exercise hour (Wed 15-16, CAB G52) per week. The grade will be composed of three additional special assignments and an oral presentation, counting 25% each. For questions, please contact Johannes Lengler or Robin Moser. English Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Randomized Algebraic Algorithms (matchings), Lovász Local Lemma, Cryptographic Reductions (XOR Lemma, Goldreich-Levin Theorem), Probabilistically Checkable Proofs (introduction). Notes for every topic will be handed out during the course. Reading assignments are Basics of Probabilistic Analysis for the APC-Lecture. The following textbooks do not cover all topics of the course (neither is every topic treated in these textbooks a topic of the course). Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest Randomized Algorithms by R. Motwani und P. Raghavan Computational Geometry - Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf Basic knowledge of Probability Theory and Theoretical Computer Science as provided by the lectures "Probability and Statistics" and "Theoretical Computer Science" of the Bachelor Programme.

### Regular Exercises

The weekly assignments are made available online by Tuesday evening (see schedule below). The "due date" is Tuesday the next week. If you would like your assistant to look over your solutions, we request that you hand them in by Tuesday 2pm.

We strongly recommend that you solve all problems on your own and attend the exercise classes. Your assistant is happy to look at your solutions at any time and correct/comment them. Although only the special assignments need to be solved and handed in mandatorily, all exercises and their solutions are part of the material relevant for the two exams.

Some of the exercises are marked as "in-class", which means that we do not expect you to solve them before the exercise class, instead, your assistant will solve them with you in class. Since handing in solutions is optional anyways, the only implication this has is that your assistant will proceed more slowly when discussing these exercises. For the regular ones, only the solutions will be presented and explained and we expect you to have looked at the problems beforehand if you wish to follow the class.

The exercise classes take place as follows:

Group Time Place Assistant
A Wednesday, 13-15 CAB G56 Sandro Coretti
B Wednesday, 16-18 CAB G52 Robin Moser
C Friday, 14-16 CAB G56 Vincent Kusters

Students taking also the honours part should preferably go to group B (Wed 16-18), together with the honours part exercises (Wed 15-16, CAB G52).

### Errata to the Lecture Notes

 p. 34 before Theorem 1.10 and then we delete the root item'' instead of and then we remove the root item''

Errata for Chapter 6

In Theorem 6.18, the following correction is necessary:
"there exists $\hat{b}$ and $\sigma$" --> "there exists $\sigma$"
and at the end of the theorem the following should be added:
"where $\hat{b}$ is any instance of $B$ (if one exists) for which $\Phi^{\beta(D,\hat{b})}(C) \geq \rho_2(\alpha)$.

Note that this means that the function $\phi_2$ is not necessarily efficiently computable (for some notion of efficiency), but this is also not necessary to obtain the hardness implication corollaries. What is required is that $\phi_2$ is efficiency-preserving, i.e., it must map an efficient distinguisher to an efficient distinguisher, but, as stated, it must not itself be efficiently computable.

### Contents

The coarse structure of this course will be as follows:
TopicLecturer
Random(ized) Search TreesA. Steger
Point LocationA. Steger
Minimum CutE. Welzl
Randomized Algebraic AlgorithmsE. Welzl
Lovász Local LemmaE. Welzl
Cryptography: Hardness, Indistinguishability, and ReductionsU. Maurer
Introduction to PCPT. Holenstein

### Preliminary Schedule

This schedule is preliminary and subject to change. The exact schedule will be updated on a weekly basis.

j
Calendar WeekDateTopic Exercises
(by due date)
Solutions HonoursHonours Solutions
38 Monday, September 17 No lecture! As a preparation to this week's exercises, please read the Basics of Probabilistic Analysis. ex-KW38.pdf*
ex-KW38-solution.pdf
Tuesday, September 18 Random(ized) Search Trees
39 Monday, September 24 " ex-KW39.pdf*
ex-KW39-solution.pdf
Tuesday, September 25 "
40 Monday, October 1 " ex-KW40.pdf
ex-KW40-solution.pdf
hex1.pdf
hex1-solution.pdf
Tuesday, October 2 Point Location
41 Monday, October 8 " ex-KW41.pdf (update 21.1)

Special Assigmnent 1 (update 12.10)

ex-KW41-solution.pdf
Honours Parts Assignment 1
Tuesday, October 9 "
42 Monday, October 15 Minimum Cut ex-KW42.pdf*
ex-KW42-solution.pdf
Tuesday, October 16 "
43 Monday, October 22 Randomized Algebraic Algorithms Special Assignment 1 is due this Tuesday ex-KW43-solution.pdf
hex2.pdf
hex2-solution.pdf
Tuesday, October 23 "
44 Monday, October 29 " ex-KW44.pdf(*)
(has a regular and an in-class part)
ex-KW44-solution.pdf
Honours Parts Assignment 1 is due this Wednesday Honours Parts Assignment 1 Solution
Tuesday, October 30 Lovász Local Lemma
45 Monday, November 5 " The midterm exam will be discussed. (we do not publish formal solutions for the midterm. Everything relevant should be on the slides, if you have questions, just ask.)
Tuesday, November 6 MIDTERM EXAM
Location: HG F7
Duration: 120 minutes
Exam content: everything until and including KW44

46 Monday, November 12 Cryptography: Hardness, Indistinguishability, and Reductions
Special Assignment 1 Slides

Tuesday, November 13 "
47 Monday, November 19 "
ex-KW47.pdf

Special Assignment 2 (update 22.11)

ex-KW47-solution.pdf
Honours Parts Assignment 2
Tuesday, November 20 "
48 Monday, November 26 "
ex-KW48.pdf*
ex-KW48-solution.pdf
Tuesday, November 27 "
49 Monday, December 3 PCP Special Assignment 2 is due this Tuesday ex-KW49-solution.pdf
Tuesday, December 4 "
50 Monday, December 10 " ex-KW50.pdf
ex-KW50-solution.pdf
Honours Parts Assignment 2 is due this Wednesday Honours Parts Assignment 2 Solution
Tuesday, December 11 "
51 Monday, December 17 " ex-KW51.pdf*
ex-KW51-solution.pdf
Honours Parts Assignment 3 (update 17.1) Honours Parts Assignment 3 Solution
Tuesday, December 18 "