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 (2018)

Lecturers: Emo Welzl (CAB G 39.2), contact person,
Mohsen Ghaffari (CAB G 32.1),
Angelika Steger (CAB G 37.2),
David Steurer (CAB H 36.2),
Peter Widmayer (CAB H 39.2).
Assistants: Ahad N. Zehmakan (CAB G 39.3), contact assistant
Malte Milatz (CAB G 36.1),
Jerri Nummenpalo (CAB G 39.3),
Patrick Schnider (CAB G 36.2),
Zeno Vintschger,
Manuel Wettstein (CAB G 38).
Lectures: Mon 13-15, ML D 28,
Tue 14-16, HG D 1.2.
Exercise: You are free to choose whichever group suits you best:
  • Wed 13-15 CAB G 56
  • Wed 13-15 CHN D 44 Cancelled. Please go to the other group instead.
  • Wed 16-18 CAB G 52
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. Preliminary list of topics:
  • Minimum spanning trees (A. Steger)
  • Randomized search trees (A. Steger)
  • Point location (E. Welzl)
  • Linear programming (D. Steurer, E. Welzl)
  • Randomized algebraic algorithms (P. Widmayer)
  • Parallel algorithms (M. Ghaffari)
Literature:

The Lecture Notes

Chapter 6

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, C. Stein
  • Randomized Algorithms by R. Motwani und P. Raghavan
  • Computational Geometry - Algorithms and Applications by M. de Berg, O. Cheong, M. van Kreveld, M. Overmars
Prerequisites: Familiarity with basic notions of probability theory, cf. the course Algorithmen und Wahrscheinlichkeit. In particular, you should have a good understanding of the notions mentioned in the help sheet for the exam of that course. See also Basics of Probabilistic Analysis for the APC-Lecture.

Exams, Special Assignments and Grading

There will be an optional written midterm exam and a written final exam. Script or any other supplementary material for either exam is not permitted. Furthermore, we will hand out two special assignments (compulsory continuous performance assessment) whose solution (typeset in LaTeX) is due two weeks later and will be graded.

The final grade is 20% midterm exam + 20% special assignments + 60% final exam

OR

if the result of the midterm exam does not improve the final grade or has not been sitted: 20% special assignments + 80% final exam.

Special Assignment 1:

Oct 15 - Oct 29 at 2:15 pm.

Solution

Midterm Exam:

On Monday, November 5, instead of the lecture (13:00-15:00) and at the Hönggerberg campus, HPH G 1.
No written material will be permitted. The exam covers all material up to the lecture on October 30.

You may find previous midterms here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017.

Special Assignment 2:

Nov 20 - Dec 4 at 2:15 pm.

Solution

Final exam: On Tuesday, January 22, 14:00-17:00, and at the Hönggerberg campus, HIL F 41.
No written material will be permitted.
You may find previous finals here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017.

Absence. If there are compelling reasons why you cannot 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. As regards the final exam, ETH regulations apply.

Exchange students. 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, preferably at the beginning of the semester. If you contact us too late, we cannot help you.

Regular Exercises

Regular exercises are made available online on a weekly basis. Students are expected to (try and) solve the problems and attend the exercise classes. Your assistant is happy to look at your solutions and correct/comment them. All exercises and their solutions are part of the material relevant for the two exams.

Schedule

In the table below you can find the lecture dates and the preliminary topics. The exercises and their solutions will be published here.

Calendar Week Date Topic Exercises and SPAs
(by due date)
Solutions
38 Mon
17.9.18
No class. As a preparation to this week's exercises, please read Basics of Probabilistic Analysis. ex-KW38.pdf (only in-class exercises, no hand-in date) solution-KW38.pdf
Tue
18.9.18
Bootstrapping Techniques (1.1) Slides
39 Mon
24.9.18
Bootstrapping Techniques (1.2) ex-KW39.pdf solution-KW39.pdf
Tue
25.9.18
Random(ized) Search Trees (2.1) Slides
40 Mon
1.10.18
Random(ized) Search Trees (2.2, 2.3, and 2.4) ex-KW40.pdf solution-KW40.pdf
Tue
2.10.18
Random(ized) Search Trees (2.5 and 2.7)
41 Mon
8.10.18
Point Location (3.1) ex-KW41.pdf solution-KW41.pdf
Tue
9.10.18
Point Location (3.2)
42 Mon
15.10.18
Point Location (3.3 and 3.4) ex-KW42.pdf solution-KW42.pdf
Tue
16.10.18
Linear Programming (4.1 and 4.2) Slides
43 Mon
22.10.18
Linear Programming (4.3) ex-KW43.pdf solution-KW43.pdf
Tue
23.10.18

Linear Programming (4.4)
44 Mon
29.10.18
Linear Programming (4.5) ex-KW44.pdf + Special assignment 1 solution-KW44.pdf
Tue
30.10.18
Linear Programming (4.6)
45 Mon
5.11.18
Midterm (13-15, HPH G 1) ex-KW45.pdf+ Midterm Exam solution-KW45.pdf
Tue
6.11.18
Linear Programming (4.7 and 4.8)
46 Mon
12.11.18
Linear Programming (4.9 and 4.10) ex-KW46.pdf solution-KW46.pdf
Tue
13.11.18
Randomized Algebraic Algorithms (5.1 and 5.2)
47 Mon
19.11.18
Randomized Algebraic Algorithms (5.3) ex-KW47.pdf solution-KW47.pdf
Tue
20.11.18
Randomized Algebraic Algorithms (5.4 and 5.5)
48 Mon
26.11.18
Randomized Algebraic Algorithms (5.6) ex-KW48.pdf solution-KW48.pdf
Tue
27.11.18
Parallel Algorithms (6.1 and 6.2)
49 Mon
3.12.18
Parallel Algorithms (6.3) ex-KW49.pdf + Special assignment 2 solution-KW49.pdf
Tue
4.12.18
Parallel Algorithms (6.4)
50 Mon
10.12.18
Parallel Algorithms (6.5) ex-KW50.pdf solution-KW50.pdf
Tue
11.12.18
Parallel Algorithms (6.6)
51 Mon
17.12.18
Parallel Algorithms (6.7 and 6.8) ex-KW51.pdf solution-KW51.pdf
Tue
18.12.18
Parallel Algorithms (6.9, 6.10, and 6.11)