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

<< Courses in 2017-2018