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:1515:00 CAB G11, Tuesday 14:1516:00 CAB G51; Important:

Credit Points:  8CP for Informatik Bachelor and Mathematik Bachelor (252020900L, 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 1516, 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, GoldreichLevin 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 APCLecture. The following
textbooks do not cover all topics of the course (neither is every
topic treated in these textbooks a topic of the course).

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. 
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 closedbook. 
Special Assignments:  Twice in the course of the term, we will hand out specially marked exercises (with reading material for selfstudy) 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 APCLecture, 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 closedbook. 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 posthaste 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. 
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 "inclass", 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, 1315  CAB G56  Sandro Coretti 
B  Wednesday, 1618  CAB G52  Robin Moser 
C  Friday, 1416  CAB G56  Vincent Kusters 
Students taking also the honours part should preferably go to group B (Wed 1618), together with the honours part exercises (Wed 1516, CAB G52).
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 efficiencypreserving, i.e., it must map an efficient distinguisher to an efficient distinguisher, but, as stated, it must not itself be efficiently computable.
Topic  Lecturer 

Random(ized) Search Trees  A. Steger 
Point Location  A. Steger 
Minimum Cut  E. Welzl 
Randomized Algebraic Algorithms  E. Welzl 
Lovász Local Lemma  E. Welzl 
Cryptography: Hardness, Indistinguishability, and Reductions  U. Maurer 
Introduction to PCP  T. Holenstein 
j
Calendar Week  Date  Topic  Exercises (by due date)  Solutions  Honours  Honours Solutions 

38  Monday, September 17  No lecture! As a preparation to this week's exercises, please read the Basics of Probabilistic Analysis.  exKW38.pdf^{*} 
exKW38solution.pdf 

Tuesday, September 18  Random(ized) Search Trees  
39  Monday, September 24  "  exKW39.pdf^{*} 
exKW39solution.pdf 

Tuesday, September 25  "  
40  Monday, October 1  " 
exKW40.pdf 
exKW40solution.pdf 
hex1.pdf 
hex1solution.pdf 
Tuesday, October 2  Point Location  
41  Monday, October 8  " 
exKW41.pdf
(update 21.1)
Special Assigmnent 1 (update 12.10) 
exKW41solution.pdf 
Honours Parts Assignment 1  
Tuesday, October 9  "  
42  Monday, October 15  Minimum Cut  exKW42.pdf^{*} 
exKW42solution.pdf 

Tuesday, October 16  "  
43  Monday, October 22  Randomized Algebraic Algorithms 
Special Assignment 1 is due
this Tuesday
exKW43.pdf^{*} 
exKW43solution.pdf 
hex2.pdf 
hex2solution.pdf 
Tuesday, October 23  "  
44  Monday, October 29  " 
exKW44.pdf^{(*)} (has a regular and an inclass part) 
exKW44solution.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 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  
Tuesday, November 13  "  
47  Monday, November 19  "  exKW47.pdf Special Assignment 2 (update 22.11) 
exKW47solution.pdf 
Honours Parts Assignment 2  
Tuesday, November 20  "  
48  Monday, November 26  "  exKW48.pdf^{*} 
exKW48solution.pdf 

Tuesday, November 27  "  
49  Monday, December 3  PCP 
Special Assignment 2 is due this Tuesday
exKW49.pdf^{*} 
exKW49solution.pdf 

Tuesday, December 4  "  
50  Monday, December 10  " 
exKW50.pdf 
exKW50solution.pdf 
Honours Parts Assignment 2 is due this Wednesday  Honours Parts Assignment 2 Solution 
Tuesday, December 11  "  
51  Monday, December 17  " 
exKW51.pdf^{*} 
exKW51solution.pdf 
Honours Parts Assignment 3 (update 17.1)  Honours Parts Assignment 3 Solution 
Tuesday, December 18  "  
Final Exam Grade Chart  
*) these exercises are "inclass" (see the section "Regular Exercises" above). All other exercises are "due" on Tuesday of the corresponding week. 
Date  Document(s)  Version  Place  Correction 

12.10.  spa1.pdf  9.10.  Ex. 2.a  s_1=0 instead of s_1=1 
22.11.  spa2.pdf  20.11.  Ex. 3  In Theorem 1, definition of R(C): D\not = E instead of D,E 
21.1.  exKW41solution.pdf  9.10.  Ex. 4  The threshold position is at (a_{i1}+a_{i+1}), not (a_i+a_{i+2}) 