Department of Computer Science  Institute of Theoretical Computer Science  CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
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). David Steurer (CAB H 36.2), 

Assistants: 
Jerri Nummenpalo (CAB G 39.3), contact assistant Malte Milatz (CAB G 36.1), Ahad N. Zehmakan (CAB G 39.3), Jara Uitto (CAB G 19.3), Manuel Wettstein (CAB G 19.2). 
Lectures: 
Mon 1315, CAB G 51, Tue 1416, CAB G 51. 
Exercise:  You are free to choose whichever group suits you best:

Credit Points:  8CP for Informatik Bachelor and Mathematik Bachelor (252020900L, 4V + 2U + 1A) 
Language:  English 
Contents: 
Advanced design and analysis methods for algorithms and data structures.
Preliminary list of topics:

Literature: 
Reading assignments are Basics of Probabilistic Analysis for the APCLecture. 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).

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. 
There will be a written midterm exam and a written final exam. Furthermore, there will be two mandatory special assignments (SPAs), 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%).
Oct 10 – Oct 24 at 2:15 pm.  
Midterm Exam: 
On Monday, 30 October 2017, instead of the
lecture (13:0015:00) and at the Hönggerberg campus. No written material will be permitted. The exam covers all material up to the lecture on October 24. You may find previous midterms here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015. 2016. 
Special assignment 2 (Minor update on 22.11.): 
Nov 21 – Dec 5. 
Final exam:  Feb 10, 2018 You may find previous finals here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016. 
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 posthaste 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 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.
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 18.9.17 
No class. As a preparation to this week's exercises, please read Basics of Probabilistic Analysis.  exKW38.pdf (only inclass exercises, no handin date)  solutionKW38.pdf 
Tue 19.9.17 
First lecture. Randomized Search Trees (1.1, 1.2)  
39  Mon 25.9.17 
Randomized Search Trees (1.3, 1.4)  exKW39.pdf inclassKW39.pdf 
solutionKW39.pdf 
Tue 26.9.17 
Randomized Search Trees (1.5, 1.6, 1.7)  
40  Mon 2.10.17 
Point Location (2, 2.1, 2.2 up to fractional cascading)  exKW40.pdf  solutionKW40.pdf 
Tue 3.10.17 
Point Location (2.2, 2.3)  
41  Mon 9.10.17 
Point location (2.4)  exKW41.pdf inclassKW41.pdf 
solutionKW41.pdf 
Tue 10.10.17 
Randomized Algebraic Algorithms (4.1, 4.2) Special assignment 1 published 

42  Mon 16.10.17 
Randomized Algebraic Algorithms (4.3, 4.5)  inclassKW42.pdf  solutionKW42.pdf 
Tue 17.10.17 
Randomized Algebraic Algorithms (4.4, 4.6 until the proof of Lemma 4.4)  
43  Mon 23.10.17 
Randomized Algebraic Algorithms (4.6)  spa1.pdf will be discussed.  spa1solution.pdf 
Tue 24.10.17 
Minimum Cut (3.1, 3.2, 3.3) Special assignment 1 deadline 

44  Mon 30.10.17 
Midterm exam (13:0015:00) in HIL E1 (Hönggerberg)  midterm.pdf will be discussed.  No solutions are provided. 
Tue 31.10.17 
Minimum Cut (3.4)  
45  Mon 6.11.17 
Linear Programming (6.1, 6.2, Toolbox of transormations)  exKW45.pdf  solutionKW45.pdf 
Tue 7.11.17 
Linear Programming (6.3, KleeMinty cube example)  
46  Mon 13.11.17 
Linear Programming (6.4, 6.5.1)  exKW46.pdf  solutionKW46.pdf 
Tue 14.11.17 
Linear Programming (6.5.2, 6.6: 6.6.1, 6.6.2)  
47  Mon 20.11.17 
Linear Programming (6.6.3)  exKW47.pdf inclassKW47.pdf  solutionKW47.pdf 
Tue 21.11.17 
Linear Programming (6.7, 6.8) Special assignment 2 published. (Minor update on 22.11.) 

48  Mon 27.11.17 
Linear Programming (6.9, 6.10)  inclassKW48.pdf  solutionKW48.pdf 
Tue 28.11.17 
Local Graph Algorithms (8.1, 8.2, 8.2.1, 8.2.2)  
49  Mon 4.12.17 
Local Graph Algorithms (8.2.2, 8.3, 8.3.2)  inclassKW49.pdf and Special assignment 2 will be discussed.  solutionKW49.pdf spa2solution.pdf 
Tue 5.12.17 
Local Graph Algorithms (8.4.1 (Theorem 8.16 only with O(Delta^2 log(Delta)) bound), 8.4.2, 8.6, 8.6.1) Special assignment 2 deadline 

50  Mon 11.12.17 
Local Graph Algorithms (8.6.2 and a O(log^2 n) analysis of Luby's algorithm)  exKW50.pdf  solutionKW50.pdf 
Tue 12.12.17 
Local Graph Algorithms (8.7, 8.7.1, 8.7.2)  
51  Mon 18.12.17 
Local Graph Algorithms (8.5, 8.5.1 (proofs only for strong diam. netw. decomp.), 8.5.2. (we only showed the existence part), 8.5.3)  exKW51.pdf inclassKW51.pdf  solutionKW51.pdf 
Tue 19.12.17 
Local Graph Algorithms (8.8) 