Algorithms, Probability, and Computing (2020)

Lecturers:	Bernd Gärtner (CAB G 31.1), Mohsen Ghaffari (CAB G 32.1), Rasmus Kyng (CAB H 33.1), David Steurer (CAB H 36.2),
Assistants:	Daniel Bertschinger (CAB G 19.2), Ming Ding (CAB H 31.1), Manuela Fischer (CAB G 32.2), Jeff Giliberti, Christoph Grunau (CAB G 16.2), contact assistant Meghana Mallik Reddy (CAB G 36.2), Federico Soldà (CAB H 31.2), Manuel Wiedmer, Goran Zuzic (CAB G 32.1)
Moodle:	We use Moodle in this course. Please check the Moodle page regularly.
Lectures:	Mon 14-16, Online, Tue 14-16, Online
Exercise:	Wed 14-16, Online, Wed 14-16, Online, Wed 16-18, Online, Wed 16-18, Online
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: Bootstrapping Techniques (B. Gärtner) Randomized search trees (B. Gärtner) Point location (B. Gärtner, R. Kyng) Linear programming (R. Kyng, D. Steurer) Randomized algebraic algorithms (D. Steurer) Parallel algorithms (M. Ghaffari)
Literature:	The Lecture Notes Notations Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 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 13 - Oct 27 at 10 pm.
Solution
Midterm Exam:	No written material will be permitted. You may find previous midterms here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019.
Special Assignment 2:	Nov 17 - Dec 1 at 10 pm.
Solution
Final exam:	No written material will be permitted. You may find previous finals here: 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019.

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 please take a look at the following website for current regulations.

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 14.9.20	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 15.9.20	Bootstrapping Techniques (1.1)
39	Mon 21.9.20	Bootstrapping Techniques (1.2)	ex-KW39.pdf	solution-KW39.pdf
	Tue 22.9.20	Random(ized) Search Trees (2.1, 2.2)
40	Mon 28.9.20	Random(ized) Search Trees (2.3, 2.5)	ex-KW40.pdf	solution-KW40.pdf
	Tue 29.9.20	Random(ized) Search Trees (2.6, 2.7)
41	Mon 05.10.20	Point Location (3.1, 3.2)	ex-KW41.pdf	solution-KW41.pdf
	Tue 06.10.20	Point Location (3.2)
42	Mon 12.10.20	Point Location (3.3, 3.4)	ex-KW42.pdf	solution-KW42.pdf
	Tue 13.10.20	Linear Programming (4.1, 4.2)
43	Mon 19.10.20	Linear Programming (4.3, 4.4)	ex-KW43.pdf (in-class)	solution-KW43.pdf
	Tue 20.10.20	Linear Programming (4.5)
44	Mon 26.10.20	Linear Programming (4.6)	Special Assignment 1	Solution
	Tue 27.10.20	Linear Programming (4.6)
45	Mon 2.11.20	Linear Programming (4.7)	ex-KW45.pdf (in-class)	solution-KW45.pdf
	Tue 3.11.20	Q&A session
46	Mon 9.11.20	Linear Programming (4.8, 4.9, 4.10)	ex-KW46.pdf	solution-KW46.pdf
	Tue 10.11.20	Randomized Algebraic Algorithms (5.1, 5.2)
47	Mon 16.11.20	Randomized Algebraic Algorithms (5.3, 5.4)	ex-KW47.pdf	solution-KW47.pdf
	Tue 17.11.20	Randomized Algebraic Algorithms (5.4)
48	Mon 23.11.20	Randomized Algebraic Algorithms (5.6)	ex-KW48.pdf (in-class)	solution-KW48.pdf
	Tue 24.11.20	Parallel Algorithms (6.1, 6.2)
49	Mon 30.11.20	Parallel Algorithms (6.3)	Special Assignment 2	Solution
	Tue 1.12.20	Parallel Algorithms (6.4)
50	Mon 7.12.20	Parallel Algorithms (6.4, 6.5)	ex-KW50.pdf	solution-KW50.pdf
	Tue 8.12.20	Parallel Algorithms (6.5)
51	Mon 14.12.20	Parallel Algorithms (6.6)	ex-KW51.pdf	solution-KW51.pdf
	Tue 15.12.20	Parallel Algorithms (6.6)