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)
Assistants: Timon Hertli (CAB G39.3), contact assistant.
Sandro Coretti (CAB H17), Vincent Kusters (CAB G37.2), Robin Moser (CAB G19.2), assistants.
Time: 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
Credit Points: 8CP for Informatik Bachelor and Mathematik Bachelor (252-0209-00L, 4V + 2U + 1A)
Honours part: 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.
Language: English
Contents: 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).
Literature: 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
Prerequisites: 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.

Exams, Special Assignments and Grading

Grading: There will be a written midterm exam and a written final exam (see below). The final grade will be composed by the final exam (60%), midterm exam (20%), and the special assignments (20%).
Midterm Exam: The midterm exam will take place on Tuesday, November 6 from 14:00 to 16:00. Relevant material is everything until and including KW44. The exam is written and closed-book.
Special Assignments: Twice in the course of the term, we will hand out specially marked exercises (with reading material for self-study) the solution of which (typeset in LaTeX or similar) is due two weeks later. Your solutions will be graded. You are welcome to discuss these exercises with your colleagues, but we expect you to hand in your own writeup. All material covered by the special assignments (and the regular exercises) is, unless stated otherwise, relevant for the (midterm and final) exams.
Final Exam: For the date and location, please consult myStudies.

The relevant material consists of the official lecture notes, the material from Basics of Probabilistic Analysis for the APC-Lecture, the material covered in the exercises, the special assignments and any additional handouts distributed during the semester. Not content are the sections 6.10 and 6.11 of the crypto lecture notes.

The exam is written and closed-book. No written material permitted.

Previous Exams: Midterm exam 2007 pdf,
midterm exam 2008 pdf,
midterm exam 2009 pdf,
midterm exam 2010 pdf,
midterm exam 2011 pdf,
final exam 2007 pdf,
final exam 2008 pdf,
final exam 2009 pdf,
final exam 2010 pdf,
final exam 2011 pdf
Conditions: Absence
If there are compelling reasons why you cannot attend either of the exams or hand in a special assignment on the due date foreseen, please contact us post-haste and we can look for a solution. Note, however, that we will grant requests of this type only in very exceptional cases (doctor's note, military service, funeral, etc.). Private events (vacation, sports, career fairs, etc.) are never sufficient grounds. As far as special assignments are concerned, you can hand them in to the contact assistant by email at any time before the due date, so there is no need to be present in person.

Exchange studens who depart before the end of term
Exchange students enrolled for APC in fall might want to return to their home university prior to the date of the final exam. If this applies to you and you nonetheless wish to be evaluated and given credits for APC, then as an alternative to returning to Zurich for the exam, there is the possibility for you to take the exam at your home university at the same time it takes place in Zurich. If you want to make use of this exam mode, you as a student are responsible for finding a professor at your home university who is willing to allocate resources for such a supervision and for establishing contact between us and the other party. At any rate, arrangements of this type have to be made very timely, preferrably at the beginning of the semester. If you contact us too late, we cannot help you.

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

ex-KW38-slides.pdf

Tuesday, September 18 Random(ized) Search Trees
39 Monday, September 24 " ex-KW39.pdf*
ex-KW39-solution.pdf

ex-KW39-slides.pdf

Tuesday, September 25 "
40 Monday, October 1 " ex-KW40.pdf
ex-KW40-solution.pdf

ex-KW40-slides.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

ex-KW41-slides.pdf

Honours Parts Assignment 1
Tuesday, October 9 "
42 Monday, October 15 Minimum Cut ex-KW42.pdf*
ex-KW42-solution.pdf

ex-KW42-slides.pdf

Tuesday, October 16 "
43 Monday, October 22 Randomized Algebraic Algorithms Special Assignment 1 is due this Tuesday

ex-KW43.pdf*

ex-KW43-solution.pdf

ex-KW43-slides.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

ex-KW44-slides.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.)

Midterm Slides

Grade Chart

Tuesday, November 6 MIDTERM EXAM
Location: HG F7
Time: Please arrive at 14:00
Duration: 120 minutes
Exam content: everything until and including KW44

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

Grade Chart

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

Special Assignment 2 (update 22.11)

ex-KW47-solution.pdf

ex-KW47-slides.pdf

Honours Parts Assignment 2
Tuesday, November 20 "
48 Monday, November 26 "
ex-KW48.pdf*
ex-KW48-solution.pdf

ex-KW48-slides.pdf

Tuesday, November 27 "
49 Monday, December 3 PCP Special Assignment 2 is due this Tuesday

ex-KW49.pdf*

ex-KW49-solution.pdf

ex-KW49-slides.pdf

Tuesday, December 4 "
50 Monday, December 10 " ex-KW50.pdf
ex-KW50-solution.pdf

ex-KW50-slides.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

ex-KW51-slides.pdf

Special Assignment 2 Slides

Grade Chart

Honours Parts Assignment 3 (update 17.1) Honours Parts Assignment 3 Solution
Tuesday, December 18 "
Final Exam Grade Chart

Total Grade Chart

*) these exercises are "in-class" (see the section "Regular Exercises" above). All other exercises are "due" on Tuesday of the corresponding week.

Errata to the Exercises and Solutions

Date Document(s) Version Place Correction
12.10.spa1.pdf9.10.Ex. 2.as_1=0 instead of s_1=1
22.11.spa2.pdf20.11.Ex. 3In Theorem 1, definition of R(C): D\not = E instead of D,E
21.1.ex-KW41-solution.pdf9.10.Ex. 4 The threshold position is at (a_{i-1}+a_{i+1}), not (a_i+a_{i+2})