**Teacher**

Roberto DiPietro

Department of Mathematics, University of Padua

roberto.dipietro[at]unipd.it

INF01

**Aim**

We have been educated to think to algorithms as mathematical tool that compute in a precise way the intended function (think about computing the median). However, when the amount of data is overwhelming, or the required time to compute a precise algorithm is exceeding the available time, we could be willing to sacrifice a bit of the precision to have a huge improvement in some other dimension (e.g. memory occupation, computation time). This is exactly where randomized algorithms are at hand. In this short course, useful statistics tools will be first revised, and later some randomized algorithm of general interest will be discussed, as well as the general underlying principles and possible applications.

**Syllabus**

- Introduction to Randomized Algorithms

- Markov, Chebyshev, and Chernoff inequalities

- Coupon Collecting – with use cases

- Stable Marriage – with use cases

- Median finding – with use cases

**Course requirements**

None

**Examination modality**

None

**Schedule**

13 March, 16:00-18:00

20 March, 16:00-18:00

27 March, 16:00-18:00

**Location**

Meeting Room HIT, via Luzzati 4