Randomized Algorithms
and other applications of probability thinking in computer scienceCarsten DammSommersemester 2024
We study algorithms from various areas (like, for instance matrix algebra, identity testing, string matching, boolean functions, graph theory, sorting and others) and analyze their time/space/randomness requirements. We will also consider applications of “the probabilistic method” to other problems of interest for computer scientists.
Good mastering of probability notions is a prerequisite as well as algorithmic understanding and programming capabilities.
- Lecture notes
A set of lecture notes is provided via Stud.IP. It profits a lot of the excellent lecture notes Randomness and Computation by Alistair Sinclair.
Some further lecture notes and books we might use
- German lecture notes by Thomas Worsch (KIT).
- Randomized Algorithms by Sabine Storandt (then U Freiburg)
- Notes on Randomized Algorithms by James Aspnes (U Yale)
- P. Raghavan and R. Motwani: Randomized Algorithms. Cambridge University Press; 1995
- S. Jukna: Crashkurs Mathematik für Informatiker. Vieweg+Teubner Verlag; 2008
- Schedule
We will have a mixture of lecture/exercise-sessions on
- mondays 10:15-11:45 (weekly, starting April 8, 2024) and
- tuesdays 10:15-11:45 (biweekly, starting April 16. 2024).
Both will take place in IfI 0.101.
- Formalia
- Enrollment: Please register at Stud.IP for this course to get access to all information.
- Implemented Modules: see HISinOne
- Exam: will take place in July
- it will be an oral exam, I will set up time slots to choose from individually
- minimum requirement for taking part is essential contributions to solving the exercise problems, that will be given during the course
- deadline for registering to the exam at Flexnow: July 7, 2024 (attention: this is also the deadline for retiring from the exam!)