 |
 |
 |
 |
| |
|
|
|
| Lecturers: |
Angelika Steger,
contact person (CAB H19.2),
Thomas Holenstein
(CAB F53.2),
Ueli Maurer
(CAB H19.2), Peter Widmayer (CAB H39.2) |
|---|---|
| Assistants: |
Robin Moser (CAB G19.2), contact assistant. Divesh Aggarwal (CAB H32.1), Timon Hertli (CAB G39.3), Vincent Kusters (CAB G37.2), assistants. |
| Time: |
Monday 13:15-15:00 CAB G11, Tuesday 14:15-16:00 CAB G51; Important:
|
| Credit Points: | 8CP for Informatik Bachelor and Mathematik Bachelor (252-0209-00L, 4V + 2U + 1A) |
| 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).
|
| Prerequisites: | Basic knowledge of Probability Theory and Theoretical Computer Science as provided by the lectures "Probability and Statistics" and "Theory of Computing" 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: | Date and scope to be determined. 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: |
Date and location to be determined. 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 special assignments and any additional handouts distributed during the semester. 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, final exam 2007 pdf, final exam 2008 pdf, final exam 2009 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. |
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 | Vincent Kusters |
| B | Wednesday, 15-17 | CHN D48 | Timon Hertli |
| C | Friday, 14-16 | CAB G56 | Divesh Aggarwal |
| none so far |
| Topic | Lecturer |
|---|---|
| Random(ized) Search Trees | A. Steger |
| Point Location | P. Widmayer |
| Minimum Cut | P. Widmayer |
| Randomized Algebraic Algorithms | P. Widmayer |
| Lovász Local Lemma | A. Steger |
| Cryptographic Reductions | U. Maurer |
| Introduction to PCP | T. Holenstein |
| Calendar Week | Date | Topic | Exercises (by due date) | Solutions |
|---|---|---|---|---|
| 38 | Monday, September 19 | No lecture! As a preparation to this week's exercises, please read the Basics of Probabilistic Analysis. | ex-KW38.pdf* (update: 26.09.) |
ex-KW38-solution.pdf (update: 26.09.) |
| Tuesday, September 20 | Random(ized) Search Trees | |||
| 39 | Monday, September 26 | " | ex-KW39.pdf* | ex-KW39-solution.pdf |
| Tuesday, September 27 | " | |||
| 40 | Monday, October 3 | " | ex-KW40.pdf | ex-KW40-solution.pdf |
| Tuesday, October 4 | Point Location | |||
| 41 | Monday, October 10 | " |
ex-KW41.pdf
Also, we are handing out Special Assignment 1(update: 17.10.) this Tuesday |
ex-KW41-solution.pdf |
| Tuesday, October 11 | " | |||
| 42 | Monday, October 17 | Minimum Cut | ex-KW42.pdf* | ex-KW42-solution.pdf |
| Tuesday, October 18 | " | |||
| 43 | Monday, October 24 | Randomized Algebraic Algorithms |
ex-KW43.pdf* (update:25.10.) Special Assignment 1(update: 17.10.) is due this Tuesday |
ex-KW43-solution.pdf |
| Tuesday, October 25 | " | |||
| 44 | Monday, October 31 | " |
ex-KW44.pdf(*) (has a regular and an in-class part)
|
ex-KW44-solution.pdf |
| Tuesday, November 1 | Lovász Local Lemma | |||
| 45 | Monday, November 7 | " | Special Assignment 1 is returned and discussed |
spa1-solution.pdf (slides in prep...) |
| Tuesday, November 8 | Cryptographic Reductions Slides: APC11_slides1_handout.pdf |
|||
| 46 | Monday, November 14 | MIDTERM EXAM Location: ETF E1 Time: Please arrive at 13:00 Duration: 120 minutes Exam content: Chapters 1-5 |
ex-KW46.pdf*
In addition to this in-class exercise, we will discuss the solutions of the midterm exam. |
(we do not publish formal solutions for the midterm. Everything relevant should be on the slides, if you have questions, just ask.) |
| Tuesday, November 15 | Cryptographic Reductions (cont'd) | |||
| 47 | Monday, November 21 | " |
ex-KW47.pdf (update: 30.11.) Also, we are handing out Special Assignment 2 this Tuesday |
ex-KW47-solution.pdf |
| Tuesday, November 22 | " | |||
| 48 | Monday, November 28 | " |
ex-KW48.pdf*
Also, midterm grades are returned. |
ex-KW48-solution.pdf |
| Tuesday, November 29 | " | |||
| 49 | Monday, December 5 | PCP |
ex-KW49.pdf*
Special Assignment 2 is due |
ex-KW49-solution.pdf
|
| Tuesday, December 6 | " | |||
| 50 | Monday, December 12 | " | ex-KW50.pdf | ex-KW50-solution.pdf
|
| Tuesday, December 13 | " | |||
| 51 | Monday, December 19 | " |
ex-KW51.pdf* Also, Special Assignment 2 is returned and discussed this week |
ex-KW51-solution.pdf |
| Tuesday, December 20 | " | |||
| *) these exercises are "in-class" (see the section "Regular Exercises" above). All other exercises are "due" on Tuesday of the corresponding week. | ||||
| Date | Document(s) | Version | Place | Correction |
|---|---|---|---|---|
| 26.09. | ex-KW38.pdf | 09.09. | Ex. 6.d | The hint of course only applies for epsilon <= 1/2 (and that is where we use it) |
| 26.09. | ex-KW38-solution.pdf | 09.09. | Ex. 6.d | added footnote |
| 17.10. | spa1.pdf | 03.10. | Ex. 3.b | removed 'subtree-regular' from the hypothesis; this is obviously not necessary to prove 3.b, nor will you want this in the hypothesis for solving the later tasks |
| 25.10. | ex-KW43.pdf | 17.10. | Ex. 6 | removed this exercise; it is being postponed to next week because we are not there yet with the lecture |
| 17.11. | ex-KW47.pdf | 15.10. | Ex. 1 | slightly reformulated |
| 30.11. | ex-KW47.pdf | 17.11. | Ex. 4 | moved to Week 48 |