# 192.020 Randomized Algorithms This course is in all assigned curricula part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});This course is in at least 1 assigned curriculum part of the STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2023W

2023W, VU, 2.0h, 3.0EC

## Properties

• Semester hours: 2.0
• Credits: 3.0
• Type: VU Lecture and Exercise
• Format: Presence

## Learning outcomes

After successful completion of the course, students are able to...

• Explain terms and strategies associated with randomized algorithms;
• Intuitively and formally describe randomized algorithms for various problems, analyze them mathematically, and prove their properties;
• Apply probability calculations to analyze the performance of randomized algorithms;
• Identify application areas of randomized algorithms and select suitable algorithms for solving a given problem;
• Analyze unknown computational problems and design and analyze their own randomized solution procedures.

## Subject of course

Randomized algorithms are algorithms that make random decisions during their execution. Such approaches can significantly simplify or speed up the computation. However, we concede that the algorithms may produce incorrect results with a certain, limited probability, or that the algorithms are efficient only with a certain probability. This lecture covers fundamental principles, techniques, and applications of randomized algorithms. Through examples, we study their development and analysis, particularly with regard to limiting the error probability and demonstrating efficiency.

Possible topics include:

• Markov Chains, Random Walks and their applications
• Application of expected values and bounds on the deviation from them, concentration bounds
• The Monte Carlo method
• Randomized sorting algorithms
• The probabilistic method, applications, and derandomization
• Hashing and Bloom filters
• Linear programming and random rounding techniques
• Randomized complexity classes and theory
• Quantum computation and Grover's algorithm

## Teaching methods

Lectures and exercise units

Immanent

## Course dates

DayTimeDateLocationDescription
Thu10:00 - 12:0005.10.2023 - 25.01.2024Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Fri10:00 - 12:0001.12.2023Seminarraum FAV EG C (Seminarraum Gödel) Exercise
Mon10:00 - 12:0008.01.2024Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Mon14:00 - 16:0015.01.2024Seminarraum FAV 05 (Seminarraum 186) Exercise
Wed10:00 - 12:0024.01.2024Seminarraum FAV EG C (Seminarraum Gödel) Exercise
Randomized Algorithms - Single appointments
DayDateTimeLocationDescription
Thu05.10.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Thu12.10.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Thu19.10.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Thu09.11.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Thu16.11.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Thu23.11.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Thu30.11.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Fri01.12.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Exercise
Thu07.12.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Thu14.12.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Thu21.12.202310:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Mon08.01.202410:00 - 12:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Thu11.01.202410:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Mon15.01.202414:00 - 16:00Seminarraum FAV 05 (Seminarraum 186) Exercise
Thu18.01.202410:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise
Wed24.01.202410:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Exercise
Thu25.01.202410:00 - 12:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture/Exercise

## Examination modalities

• Solve and hand-in exercise sheets with theoretical questions
• Present and discuss the course content in an oral exam

The final grade is a combination of the performance in the exercises and the oral exam.

## Course registration

Begin End Deregistration end
11.09.2023 09:00 06.10.2023 23:59 15.10.2023 23:59

## Curricula

Study CodeObligationSemesterPrecon.Info
066 645 Data Science Mandatory elective
066 931 Logic and Computation Not specified
066 937 Software Engineering & Internet Computing Not specified

## Literature

No lecture notes are available.

English