Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Lecturers: |
Emo Welzl, contact person
(CAB G39.2), Thomas Holenstein (CAB F53.2), Ueli Maurer (CAB H19.2), Angelika Steger (CAB H19.2), Peter Widmayer (CAB H39.2) |
---|---|
Assistants: |
Martin Jaggi, contact assistant
(CAB G33.3), Andrea Francke (CAB G19.2), Robin Moser (CAB G19.2) |
Time: |
Monday 13:15-15:00 CAB G11, Tuesday 14:15-16:00 CAB G51; begin: Tuesday, September 21, 2010 Important: Exercise sessions already start Wednesday, September 22, 13:15, CAB G56 |
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, Network Flows, 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: | Monday, November 15, 13:15 - 15:00, CAB G11. Material is everything till November 2 (meaning until the end of Chapter 6.6). The lecture notes and any other supplementary material for the exam are not permitted. In the preceeding week of November 8 there will be no new exercise sheet. In the exercise session we will repeat the material for the exam, and you are of course welcome to ask questions. |
Special Assignments: | Twice in the course of 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. The material of the special assignments is relevant for the (midterm and final) exams. |
Exam Material: | As in the lecture notes (cut point for mid term will be announced) plus the material from Basics of Probabilistic Analysis for the APC-Lecture and from the special assignments. |
Final Exam: | Tuesday, February 8, 09:00 - 12:00, HIL F61 (Hönggerberg, Sessionsprüfung). The lecture notes and any other supplementary material are not permitted for the exam. |
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 |
Remarks: |
For those students who are not able to do the midterm exam
because of some crucial reason (military service, etc.) there is the
opportunity of a written and oral exam two weeks after the midterm
exam. ETH students who are at a foreign university during fall have to do a written exam there under supervision and at the same time the exam takes place at ETH. If any of the reasons above prevent you from taking the exam at the indicated time and location, please inform one of the assistants at the beginning of the semester. |
Nr. | Time | Place | Assistant |
---|---|---|---|
1 | Wednesday 13:15-15:00 | CAB G 56 | Martin Jaggi |
2 | Wednesday 15:15-17:00 | CHN D 48 | Robin Moser |
3 | Friday 14:15-16:00 | CAB G 56 | Andrea Francke |
Chapter 5.3 | page 8 | Paragraph preceding Corollary 5.4: "Condition (5.3) then reduces ..." should be "Condition (5.1) then reduces ..." |
Chapter 5.5 | page 21 | Statement of Lemma 5.12: "R'(J) = ..." should be "R'(T) = ..." |
Chapter 5.5 | middle of page 25 | The equality after "using Lemma 5.13 we must have", is in fact an inequality: ∑pT(A) ≥ ... |
Chapter 6.6 | page 21 | Proof of Lemma 6.6, line 4: "Each of these ci is an odd ..." should be "Each of these ki is an odd ..." |
Chapter 7.4.2 | page 13 | Proof of Lemma 7.1: (namely A' = RA) |
Chapter 7.6.3 | page 21 | Exercise 7.3: Claim is incorrect. It is only possible to show a generalized reduction |
Chapter 8.3 | page 12,13 | Every occurence of "Theorem 8.1" should be replaced by "Theorem 8.3" |
Chapter 8.4.4 | page 25 | In the paragraph "Checking the gates" of "Unprovable statements are rejected", M is the XOR over Eii (there is no Eij) |
Chapter 8.4.4 | page 26 | In the case 2 of "Unprovable statements are rejected", the third bullet point "and the query LDw(diag(abt)) returns ..." should be read as "LDw(abT) returns ..." |
Week | Date | Topic | Exercises | Solutions |
---|---|---|---|---|
1 | Mon 20. 9: | no lecture | preparation exercises | slides |
Tue 21. 9: | Random(ized) Search Trees | |||
2 | Mon 27. 9: | (complementary slides) | 1.7, 1.9, 1.10, 1.14 (due Mon, Oct 4) | master solution, slides |
Tue 28. 9: | " | in-class exercise sheet 0 | slides | |
3 | Mon 4.10: | Point Location | 1.17, (1.19), 1.26, 1.36, 1.39 (due Mon, Oct 11) | master solution, slides |
Tue 5.10: | " | |||
4 | Mon 11.10: | " | 2.1, 2.2, 2.4, 2.5, 2.9, 2.11 (due Mon, Oct 18) | master solution, slides |
Tue 12.10: | " | |||
5 | Mon 18.10: | Max Flow | first special assignment (due Mon, Nov 1) | |
Tue 19.10: | " | |||
6 | Mon 25.10: | Min Cut | in-class exercise sheet 4 | master solution, slides |
Tue 26.10: | " | |||
7 | Mon 1.11: | Randomized Algebraic Algorithms | first special assignment is due | master solution, slides |
Tue 2.11: | Perfect Matchings in Planar Graphs (chapter 6.6 distributed separately) | exercise sheet 5 (due Mon, Nov 8) | master solution, slides | |
8 | Mon 8.11: | Lovász Local Lemma (chapter 5 distributed separately) | ||
Tue 9.11: | " | |||
9 | Mon 15.11: | Midterm Exam | slides | |
Tue 16.11: | " | exercise sheet 6 (due Mon, Nov 22) | master solution, slides | |
10 | Mon 22.11: | Cryptographic Reductions (chapter 7 distributed separately) | second special assignment (due on Mon, Dec 6) | |
Tue 23.11: | " | |||
11 | Mon 29.11: | " | in-class exercise sheet 7 | master solution |
Tue 30.11: | " | |||
12 | Mon 6.12: | " | second special assignment is due | master solution, slides |
Tue 7.12: | PCP Theorem | exercise sheet 8 (due Mon, Dec 13) | master solution, slides | |
13 | Mon 13.12: | " | exercise sheet 9 (due Mon, Dec 20) | master solution, slides |
Tue 14.12: | " | |||
14 | Mon 20.12: | " | ||
Tue 21.12: | " |