# RANDOMIZED METHODS IN COMPUTER SCIENCE

2023/2024
Official course title
RANDOMIZED METHODS IN COMPUTER SCIENCE
Course code
PHD189-2 (AF:497968 AR:279260)
Modality
On campus classes
ECTS credits
4
Degree level
Corso di Dottorato (D.M.45)
Educational sector code
INF/01
Period
Annual
Course year
1
Where
VENEZIA
Moodle
Go to Moodle page
The concept of randomness is an essential part of modern algorithm design. Informally, randomness amounts to choosing one out of a predefined set of options by flipping a coin. In this course, we will show how randomness is present in algorithms research in two different ways: (1) in the design of the algorithms themselves, and (2) in their analyses. The first amounts to allowing the algorithm to probabilistically choose between multiple options during its execution. Here, we show via classical examples how such power can lead to a better performance with respect to making exclusively deterministic choices. The second aspect deals with analysing algorithms on inputs that are subject to randomness, i.e., inputs that follow a certain distribution. Here, we will see how to give rigorous statements regarding an algorithm's behaviour on such inputs, i.e., we will give probabilistic guarantees (e.g., guarantees that hold in expectation or with high probability). In turn, this will help us better understand the complexity of the problems that these algorithms are solving.
At the end of the course, the student will be able to:
1) understand the classical approaches of incorporating randomness in algorithm design,
2) perform probabilistic analyses of algorithms in non-deterministic settings.
- algorithms and data structures
- probability theory
Revision of Basics in Probability Theory,
Coupon Collector and Contention Resolution,
Yao's Principle and the Secretary Problem,
The Probabilistic Method,
Some Classical Randomized Algorithms: Min-Cut, Polynomial Identity Testing, and Quicksort,