Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Algorithms, Probability, and Computing (2010)

Algorithms, Probability, and Computing (2010)

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).
  • 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 "Theory of Computing" of the Bachelor Programme.

Exams

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.

Exercises

The weekly assignments are available online Tuesday. The due date is Tuesday the next week.
We recommend that you solve the problems on your own and attend the exercises. Note, however, special assignments as described above.
There are three exercise sessions per week:
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

Errata (script)

Chapter 5.3page 8Paragraph preceding Corollary 5.4: "Condition (5.3) then reduces ..." should be "Condition (5.1) then reduces ..."
Chapter 5.5page 21Statement of Lemma 5.12: "R'(J) = ..." should be "R'(T) = ..."
Chapter 5.5middle of page 25The equality after "using Lemma 5.13 we must have", is in fact an inequality: ∑pT(A) ≥ ...
Chapter 6.6page 21Proof 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.2page 13Proof of Lemma 7.1: (namely A' = RA)
Chapter 7.6.3page 21Exercise 7.3: Claim is incorrect. It is only possible to show a generalized reduction
Chapter 8.3page 12,13Every occurence of "Theorem 8.1" should be replaced by "Theorem 8.3"
Chapter 8.4.4page 25In the paragraph "Checking the gates" of "Unprovable statements are rejected", M is the XOR over Eii (there is no Eij)
Chapter 8.4.4page 26In 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 ..."

Contents/Schedule

WeekDateTopicExercisesSolutions
1Mon 20. 9:no lecture preparation exercisesslides
Tue 21. 9:Random(ized) Search Trees
2Mon 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 0slides
3Mon 4.10:Point Location1.17, (1.19), 1.26, 1.36, 1.39 (due Mon, Oct 11)master solution, slides
Tue 5.10: "
4Mon 11.10: " 2.1, 2.2, 2.4, 2.5, 2.9, 2.11 (due Mon, Oct 18)master solution, slides
Tue 12.10: "
5Mon 18.10:Max Flowfirst special assignment (due Mon, Nov 1)
Tue 19.10: "
6Mon 25.10:Min Cutin-class exercise sheet 4master solution, slides
Tue 26.10: "
7Mon 1.11:Randomized Algebraic Algorithmsfirst special assignment is duemaster 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
8Mon 8.11:Lovász Local Lemma (chapter 5 distributed separately)
Tue 9.11: "
9Mon 15.11:Midterm Examslides
Tue 16.11: "exercise sheet 6 (due Mon, Nov 22)master solution, slides
10Mon 22.11:Cryptographic Reductions (chapter 7 distributed separately)second special assignment (due on Mon, Dec 6)
Tue 23.11: "
11Mon 29.11: "in-class exercise sheet 7master solution
Tue 30.11: "
12Mon 6.12: "second special assignment is duemaster solution, slides
Tue 7.12:PCP Theoremexercise sheet 8 (due Mon, Dec 13)master solution, slides
13Mon 13.12: "exercise sheet 9 (due Mon, Dec 20)master solution, slides
Tue 14.12: "
14Mon 20.12: "
Tue 21.12: "