Algorithms, Probability, and Computing (2023)
Program Overview
Algorithms, Probability, and Computing (2023)
Program Overview
The Algorithms, Probability, and Computing program is designed to provide students with advanced design and analysis methods for algorithms and data structures. The preliminary list of topics includes:
- Bootstrapping Techniques
- Randomized Search Trees
- Point Location
- Linear Programming
- Randomized Algebraic Algorithms
- Parallel Algorithms
Lecturers and Assistants
The program is led by the following lecturers:
- Bernd Gärtner
- Rasmus Kyng
- Angelika Steger
- David Steurer
- Emo Welzl
The program assistants are:
- Ming Ding
- Emily Eberl
- Nicolas El Maalouly
- Cella Florescu
- Piotr Luczynski
- Simon Meierhans
- Federico Soldà
- Laurent Verdan
- Simon Weber
Course Structure
The program consists of lectures and exercise classes. The lectures are held on:
- Monday, 14-16, ML D 28
- Tuesday, 14-16, ML D 28
The exercise classes are held on:
- Wednesday, 14-16, CAB G 56
- Wednesday, 14-16, CAB G 57
- Wednesday, 16-18, CAB G 56
- Wednesday, 16-18, CAB G 57
Credit Points and Language
The program is worth 8 credit points for Informatik Bachelor and Mathematik Bachelor L, with a format of 4V + 2U + 1A. The language of instruction is English.
Contents and Literature
The program covers advanced design and analysis methods for algorithms and data structures. The preliminary list of topics includes:
- Bootstrapping Techniques
- Randomized Search Trees
- Point Location
- Linear Programming
- Randomized Algebraic Algorithms
- Parallel Algorithms The recommended literature includes:
- 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:
- Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein
- Randomized Algorithms by R. Motwani and P. Raghavan
- Computational Geometry - Algorithms and Applications by M. de Berg, O. Cheong, M. van Kreveld, M. Overmars
Prerequisites
The program requires familiarity with basic notions of probability theory, as covered in the course Algorithmen und Wahrscheinlichkeit. In particular, students should have a good understanding of the notions mentioned in the help sheet for the exam of that course.
Exams, Special Assignments, and Grading
The program includes an optional written midterm exam and a written final exam. The final grade is calculated as follows:
- 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 sat: 20% special assignments + 80% final exam The special assignments are due on the following dates:
- Special Assignment 1: October 17 - November 1
- Special Assignment 2: November 21 - December 12
Regular Exercises
Regular exercises are made available online on a weekly basis. Students are expected to solve the problems and attend the exercise classes. The exercises and their solutions are part of the material relevant for the two exams.
Schedule
The program schedule is as follows: | Calendar Week | Date | Topic | Exercises and SPAs | Solutions | | --- | --- | --- | --- | --- | | 38 | Monday, September 18, 2023 | No class | ex-KW38.pdf | solution-KW38.pdf | | 38 | Tuesday, September 19, 2023 | Bootstrapping Techniques: MST (1.1) | | | | 39 | Monday, September 25, 2023 | Bootstrapping Techniques: MinCut (1.2) | ex-KW39.pdf | solution-KW39.pdf | | 39 | Tuesday, September 26, 2023 | (Random) Search Trees (2.1, 2.2) | | | | 40 | Monday, October 2, 2023 | Random Search Trees (2.3-2.6) | ex-KW40.pdf | solution-KW40.pdf | | 40 | Tuesday, October 3, 2023 | Random Search Trees: Treap (2.7) | | | | 41 | Monday, October 9, 2023 | Point Location (3.1, 3.2) | ex-KW41.pdf | solution-KW41.pdf | | 41 | Tuesday, October 10, 2023 | Point Location (3.2 continued) | | | | 42 | Monday, October 16, 2023 | Point Location (3.3, 3.4) | ex-KW42.pdf | solution-KW42.pdf | | 42 | Tuesday, October 17, 2023 | Point Location (3.4 continued), Linear Programming (4.1, 4.2) | | | | 43 | Monday, October 23, 2023 | Linear Programming (4.2 continued, 4.3) | ex-KW43.pdf | solution-KW43.pdf | | 43 | Tuesday, October 24, 2023 | Linear Programming (4.4, 4.5) | | | | 44 | Monday, October 30, 2023 | Linear Programming (4.5 continued, 4.6) | Special Assignment 1 | solution-spa1.pdf | | 44 | Tuesday, October 31, 2023 | Linear Programming (4.6 continued) | | | | 45 | Monday, November 6, 2023 | Linear Programming (4.6 continued, 4.7) | ex-KW45.pdf | solution-KW45.pdf | | 45 | Tuesday, November 7, 2023 | Linear Programming (4.8 - 4.10) | | | | 46 | Monday, November 13, 2023 | Midterm | ex-KW46.pdf | solution-KW46.pdf | | 46 | Tuesday, November 14, 2023 | Randomized Algebraic Algorithms (5.1, 5.2) | | | | 47 | Monday, November 20, 2023 | Randomized Algebraic Algorithms (5.3, 5.4) | ex-KW47.pdf | solution-KW47.pdf | | 47 | Tuesday, November 21, 2023 | Randomized Algebraic Algorithms (5.4 continued, 5.6) | | | | 48 | Monday, November 27, 2023 | Randomized Algebraic Algorithms (5.6 continued) | ex-KW48.pdf | solution-KW48.pdf | | 48 | Tuesday, November 28, 2023 | Parallel Algorithms (6.1, 6.2) | | | | 49 | Monday, December 4, 2023 | Parallel Algorithms (6.2 continued, 6.3) | Special Assignment 2 | solution-spa2.pdf | | 49 | Tuesday, December 5, 2023 | Parallel Algorithms (6.3 continued, 6.4.1) | | | | 50 | Monday, December 11, 2023 | Parallel Algorithms (6.4.2) | ex-KW50.pdf | solution-KW50.pdf | | 50 | Tuesday, December 12, 2023 | Parallel Algorithms (6.5, review of 6.1-6.5) | | | | 51 | Monday, December 18, 2023 | Parallel Algorithms (6.6) | ex-KW51.pdf | solution-KW51.pdf | | 51 | Tuesday, December 19, 2023 | Parallel Algorithms (6.6 continued, note that 6.7 is not covered) | | |