Randomized AlgorithmsModule description #40667 / Version 2
- 6 CP
- Oral exam
- Graded
- Winter and summer semester
- English
This module description is not valid in the current semester (Winter semester 2026/27).
Current version (v8)
| Module / Version | #40667 / #2 |
|---|---|
| Validity | WS 2015/16 – WS 2015/16 |
| Available language(s) | English |
| Credit points | 6 |
| Person responsible for the module | Niedermeier, Rolf |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | English |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34351100 FG Algorithmik und Komplexitätstheorie (AKT) |
Contact
| Office | EN 23 |
|---|---|
| Contact person | Thielcke, Christlinde |
| E-mail address | lehre@akt.tu-berlin.de |
| Website | https://www.tu.berlin/akt/studium-lehre/lehrveranstaltungen |
Learning outcomes
Participants of this module know fundamental randomized methods for design and analysis of efficient algorithms. They can perform simple probabilistic analyses and are aware of the limitations of randomization.
Content
Introduction into the mathematical and algorithmic foundations of algorithm design and analysis using the resource “random bits”.
Particular topics are:
- randomized algorithms for graph problems and geometric problems
- the probabilistic method
- randomized complexity classes
Particular topics are:
- randomized algorithms for graph problems and geometric problems
- the probabilistic method
- randomized complexity classes
Module components
Compulsory area
The following courses are mandatory for this module:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Randomized Algorithms | Integrated course | 0434 L 236 | Winter and summer semester | – | 4 | ISIS |
Workload and credit points
Randomized Algorithms (Integrated course)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor-/Nachbereitung | 15 | 8 h | 120 h |
| 180 h | |||
The workload of the module adds up to 180 hours. The module therefore comprises 6 credit points.
Description of teaching and learning methods
The course material is presented in lectures. The lectures are accompanied by tutorials in which
an active participation and homework on the distributed work sheets is required.
an active participation and homework on the distributed work sheets is required.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
obligatory: Basic knowledge of algorithm design and analysis
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | English |
Exam description
Final oral exam determining the grade (MP).
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Winter and summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Please register at QISPOS or directly at the examination office.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
- Michael Mitzenmacher, Eli Upfal: Probability and Computing, Cambridge University Press, 2005.
- Rajeev Motwani, Prabhakar Raghavon: Randomized Algorithms, Cambridge University Press, 1995.
Assigned programs
This module is not used in any program.
Computer Science diploma
Technical Computer Science diploma
Technical Computer Science diploma
Miscellaneous
Not specified