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

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Algorithms, Probability, and Computing (2016)

Quick link: Lecture notes on local graph algorithms.

There will be a Q&A session on Monday, 6 Feb 2017, 10h30 in CAB G 51.

Material relavant for the final exam on 13 Feb: All topics that were covered in class, except the content of the lectures on 13 Dec, 19 Dec and 20 Dec.

Lecturers: Emo Welzl (CAB G 39.2), contact person,
Mohsen Ghaffari (CAB G 32.1),
Angelika Steger (CAB G 37.2),
Peter Widmayer (CAB H 39.2).
Assistants: Malte Milatz (CAB G 36.1), contact assistant,
Chidambaram Annamalai (CAB G 36.1),
Jerri Nummenpalo (CAB G 39.3),
May Szedlák (CAB G 36.2),
Manuel Wettstein (CAB G 19.2).
Lectures: Mon 13-15, CAB G 51,
Tue 14-16, CAB G 51.
Exercise: You are free to choose whichever group suits you best:
  • Wed 13-15 CAB G 56
  • Wed 13-15 CHN D 44 This one was cancelled due to low popularity.
  • 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:
  • Randomized search trees (P. Widmayer)
  • Point location (A. Steger)
  • Randomized algorithms for Minimum Cut (A. Steger)
  • Randomized algebraic algorithms (A. Steger)
  • Lovász Local Lemma (A. Steger)
  • Linear programming (E. Welzl)
  • Local Graph Algorithms (M. Ghaffari)
Literature:

Reading assignments are Basics of Probabilistic Analysis for the APC-Lecture.

Detailed lecture notes will be sold in the 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, 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: 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.

Exams, Special Assignments and Grading

There will be a written midterm exam and a written final exam. Furthermore, there will be two mandatory special assignments, the solution of which is due two weeks later. Your solution should be typeset in LaTeX.

The final grade of the whole course will be calculated as a weighted average of the grades for the final exam (60%), midterm exam (20%), and the special assignments (20%).

Special Assignment 1: Oct 11 – Oct 25.
Midterm Exam: On Tuesday, 1 November 2016, instead of the lecture. No written material will be permitted.
You may find previous midterms here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015.
Special Assignment 2: Nov 22 – Dec 6.
Final exam: Monday Feb 13.
You may find previous finals here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014.

Absence. If there are compelling reasons why you cannot attend the midterm 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. 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

Calendar Week Date Topic Exercises and SPAs
(by due date)
Solutions
38 As a preparation to this week's exercises, please read Basics of Probabilistic Analysis. ex-KW38.pdf solution-KW38.pdf
Tue
20.9.16
Randomized Search Trees (1.1, 1.2)
39 Mon
26.9.16
Randomized Search Trees (1.3) ex-KW39.pdf
inclass-KW39.pdf
solution-KW39.pdf
Tue
27.9.16
Randomized Search Trees (1.4, 1.5, 1.6)
40 Mon
3.10.16
Randomized Search Trees (1.7) ex-KW40.pdf solution-KW40.pdf
Tue
4.10.16
Point Location (2.1, 2.2)
41 Mon
10.10.16
Point Location (2.2, 2.3) ex-KW41.pdf
inclass-KW41.pdf
solution-KW41.pdf
Tue
11.10.16
Point Location (2.4).
Special Assignment 1 is published.
42 Mon
17.10.16
Minimum Cut (3.1, 3.2, 3.3) inclass-KW42.pdf solution-KW42.pdf
Tue
18.10.16
Minimum Cut (3.4)
Randomized Algebraic Algorithms (4.1)
43 Mon
24.10.16
Randomized Algebraic Algorithms (4.2, 4.3, 4.4) spa1.pdf solution-spa1.pdf
Tue
25.10.16
Randomized Algebraic Algorithms (4.4, 4.6)
44 Mon
31.10.16
Randomized Algebraic Algorithms (4.6) midterm.pdf No master solutions will be published.
Tue
1.11.16
Midterm exam

Place: HG E 3 (not the usual lecture hall!).
Time: Arrive not later than 14:00.
Duration: 120 minutes.

Update: Exam content: Everything covered in-class up to and including chapter 4.2. The Special Assignment as such is not part of the material relevant for the midterm, but of course the class topics covered by the Special Assignment can appear again.

45 Mon
7.11.16
Linear Programming (6.1, 6.2) ex-KW45.pdf solution-KW45.pdf
Tue
8.11.16
Linear Programming (6.2, 6.3)
46 Mon
14.11.16
Linear Programming (6.3, 6.4) ex-KW46.pdf solution-KW46.pdf
Tue
15.11.16
Linear Programming (6.5, 6.6.1)
47 Mon
21.11.16
Linear Programming (6.6.1, 6.6.2) ex-KW47.pdf
inclass-KW47.pdf
solution-KW47.pdf
Tue
22.11.16
Linear Programming (6.6.3, 6.7)
Special Assignment 2 is published.
48 Mon
28.11.16
Linear Programming (6.8, 6.9, 6.10) inclass-KW48.pdf solution-KW48.pdf
Tue
29.11.16
Local Graph Algorithms (Lecture notes) (8.1, 8.2)
The lecture notes will be updated as we go through the lecture.
49 Mon
5.12.16
Local Graph Algorithms
(8.3: Det. Coloring of General Graphs)
spa2.pdf solution-spa2.pdf
Tue
6.12.16
Local Graph Algorithms
(8.4: Network Decomposition)
50 Mon
12.12.16
Local Graph Algorithms
(8.5: Maximal Independent Set, 8.6: Sublog.-Time Rand. Coloring)
ex-KW50.pdf solution-KW50.pdf
Tue
13.12.16
Local Graph Algorithms
51 Mon
19.12.16
Local Graph Algorithms ex-KW51.pdf solution-KW51.pdf
Tue
20.12.16
Local Graph Algorithms

Last modified: Fri Jan 20 2017 13:26.