Algorithms, Probability, and Computing (2023)
| Lecturers: |
Bernd Gärtner (OAT Z15), Rasmus Kyng (OAT Z21.1), Angelika Steger (OAT Z27), David Steurer (OAT Z22.2), Emo Welzl (OAT Z13.2) |
|---|---|
| Assistants: |
Ming Ding (OAT Z21.2), contact assistant, Emily Eberl, Nicolas El Maalouly (OAT Z18), Cella Florescu, Piotr Luczynski, Simon Meierhans (OAT Z21.2), Federico Soldà (OAT Z21.2), contact assistant, Laurent Verdan, Simon Weber (OAT Z18) |
| Moodle: | We use Moodle in this course. Please check the Moodle page regularly. |
| Lectures: |
Mon 14-16, ML D 28, Tue 14-16, ML D 28 |
| Exercise: |
|
| 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:
|
| Literature: |
Lecture Notes
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: | 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 and an interactive version of it. |
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 17 - Nov 1 (one additional day). |
|---|---|
| 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, 2020, 2021, 2022. |
| Special Assignment 2: | Nov 21 - Dec 12 (one additional week). |
| 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, 2020, 2021, 2022. |
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 18.9.23 |
No class. As a preparation to this week's exercises, please read Basics of Probabilistic Analysis or go through this interactive version of it. | ex-KW38.pdf (only in-class exercises, no hand-in date) | solution-KW38.pdf |
| Tue 19.9.23 |
Bootstrapping Techniques: MST (1.1) | |||
| 39 | Mon 25.9.23 |
Bootstrapping Techniques: MinCut (1.2) | ex-KW39.pdf | solution-KW39.pdf |
| Tue 26.9.23 |
(Random) Search Trees (2.1, 2.2) | |||
| 40 | Mon 2.10.23 |
Random Search Trees (2.3-2.6) | ex-KW40.pdf | solution-KW40.pdf |
| Tue 3.10.23 |
Random Search Trees: Treap (2.7) | |||
| 41 | Mon 9.10.23 |
Point Location (3.1, 3.2) | ex-KW41.pdf | solution-KW41.pdf |
| Tue 10.10.23 |
Point Location (3.2 continued) | |||
| 42 | Mon 16.10.23 |
Point Location (3.3, 3.4) | ex-KW42.pdf | solution-KW42.pdf |
| Tue 17.10.23 |
Point Location (3.4 continued), Linear Programming (4.1, 4.2) | |||
| 43 | Mon 23.10.23 |
Linear Programming (4.2 continued, 4.3) | ex-KW43.pdf (in-class) | solution-KW43.pdf |
| Tue 24.10.23 |
Linear Programming (4.4, 4.5) | |||
| 44 | Mon 30.10.23 |
Linear Programming (4.5 continued, 4.6) | Special Assignment 1 (updated) | solution-spa1.pdf |
| Tue 31.10.23 |
Linear Programming (4.6 continued) | |||
| 45 | Mon 6.11.23 |
Linear Programming (4.6 continued, 4.7) | ex-KW45.pdf (in-class) | solution-KW45.pdf |
| Tue 7.11.23 |
Linear Programming (4.8 - 4.10) | |||
| 46 | Mon 13.11.23 |
Midterm | ex-KW46.pdf | solution-KW46.pdf |
| Tue 14.11.23 |
Randomized Algebraic Algorithms (5.1, 5.2) | |||
| 47 | Mon 20.11.23 |
Randomized Algebraic Algorithms (5.3, 5.4) | ex-KW47.pdf | solution-KW47.pdf |
| Tue 21.11.23 |
Randomized Algebraic Algorithms (5.4 continued, 5.6) | |||
| 48 | Mon 27.11.23 |
Randomized Algebraic Algorithms (5.6 continued) | ex-KW48.pdf (in-class) | solution-KW48.pdf |
| Tue 28.11.23 |
Parallel Algorithms (6.1, 6.2) | |||
| 49 | Mon 4.12.23 |
Parallel Algorithms (6.2 continued, 6.3) | Special Assignment 2 (updated v3) | solution-spa2.pdf |
| Tue 5.12.23 |
Parallel Algorithms (6.3 continued, 6.4.1) | |||
| 50 | Mon 11.12.23 |
Parallel Algorithms (6.4.2) | ex-KW50.pdf | solution-KW50.pdf |
| Tue 12.12.23 |
Parallel Algorithms (6.5, review of 6.1-6.5) | |||
| 51 | Mon 18.12.23 |
Parallel Algorithms (6.6) | ex-KW51.pdf | solution-KW51.pdf |
| Tue 19.12.23 |
Parallel Algorithms (6.6 continued, note that 6.7 is not covered) |