Department of Computer Science  Institute of Theoretical Computer Science  CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Lecturers: 
Bernd Gärtner (CAB G 31.1), Mohsen Ghaffari (CAB G 32.1), Angelika Steger (CAB G 37.2), David Steurer (CAB H 36.2), 

Assistants: 
ChihHung Liu (CAB G 19.3), contact assistant Christoph Grunau, Hung Phuc Hoang (CAB G 19.2), Jorge Luis Toro Pozo (CNB F 100.5), Zeno Vintschger, Manuel Wettstein (CAB G 38), Ahad N. Zehmakan (CAB G 39.3). 
Lectures: 
Mon 1315, ML D 28, Tue 1416, HG D 1.1. 
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: 
The Lecture Notes

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 APCLecture. 
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.Oct 15  Oct 29 at 2:15 pm.  
On Monday, November 4, instead of the
lecture (13:0015:00) and at the Hönggerberg campus, HPV G 4. No written material will be permitted. The exam covers Chapter 1~4.3, exKW38~exKW43, and Special Assignment 1. You may find previous midterms here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017. 2018. 

Nov 19  Dec 3 at 2:15 pm.  
Nov 20  Dec 4 at 2:15 pm.  
Final exam:  On Tuesday, February 4, 14:0017:00 and at the Hönggerberg campus, HIL G 15. No written material will be permitted. You may find previous finals here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017. 2018. 
Absence. If there are compelling reasons why you cannot 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 16.9.18 
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 17.9.18 
Bootstrapping Techniques (1.1) Slides  
39  Mon 23.9.18 
Bootstrapping Techniques (1.2)  exKW39.pdf (updated 23.09.2019 for a typo in Exercise~2.ii.a)  solutionKW39.pdf (updated 27.09.2019) 
Tue 24.9.18 
Random(ized) Search Trees (2.1) Slides  
40  Mon 30.9.19 
Random(ized) Search Trees (2.2, 2.3, and 2.4)  exKW40.pdf (updated 30.09 for Exercise 3(c))  solutionKW40.pdf 
Tue 01.10.19 
Random(ized) Search Trees (2.5 and 2.7)  
41  Mon 07.10.19 
Point Location (3.1)  exKW41.pdf  solutionKW41.pdf 
Tue 08.10.19 
Point Location (3.2 and 3.3)  
42  Mon 14.10.19 
Point Location (3.4)  exKW42.pdf  solutionKW42.pdf 
Tue 15.10.19 
Linear Programming (4.1 and 4.2)  
43  Mon 21.10.19 
Linear Programming (4.3 and 4.4)  exKW43.pdf (inclass)  solutionKW43.pdf 
Tue 22.10.19 
Linear Programming (4.5)  
44  Mon 28.10.19 
Linear Programming (4.6)  Special Assignment 1  Solution 
Tue 29.10.19 
Linear Programming (4.6)  
45  Mon 4.11.19 
Midterm (1315, HPV G 4)  exKW45.pdf (inclass)  solutionKW45.pdf 
Tue 5.11.19 
Linear Programming (4.7 and 4.8)  
46  Mon 11.11.19 
Linear Programming (4.9 and 4.10)  exKW46.pdf  solutionKW46.pdf 
Tue 12.11.19 
Randomized Algebraic Algorithms (5.1 and 5.2)  
47  Mon 18.11.19 
Randomized Algebraic Algorithms (5.3)  exKW47.pdf  solutionKW47.pdf 
Tue 19.11.19 
Randomized Algebraic Algorithms (5.4 and 5.5)  
48  Mon 25.11.19 
Randomized Algebraic Algorithms (5.6)  exKW48.pdf (inclass)  solutionKW48.pdf 
Tue 26.11.19 
Parallel Algorithms (6.1 and 6.2)  
49  Mon 2.12.19 
Parallel Algorithms (6.3)  Special Assignment 2 & Midterm  Solution 
Tue 3.12.19 
Parallel Algorithms (6.4)  
50  Mon 9.12.19 
Parallel Algorithms (6.5)  exKW50.pdf  solutionKW50.pdf 
Tue 10.12.19 
Parallel Algorithms (6.6)  
50  Mon 16.12.19 
Parallel Algorithms (6.7 and 6.8)  exKW51.pdf  solutionKW51.pdf 
Tue 17.12.19 
Parallel Algorithms (6.9 and 6.10) 