ALGORITMI RANDOMIZZATI ED APPROSSIMATI

Knowledge and understanding: Students will acquire basic knowledge about design and analysis of randomized and approximation algorithms.

Applying knowledge and understanding: students will be to able to apply the acquired knowledge in several fields and in particular searching for solutions to hard combinatorial problems.

Making judgements: Students will be able to evaluate the possibility of developing randomized and approximation algorithms in different application fields.Communication skills: students will acquire the necessary communication skills and appropriate linguistic skills to explain and clarify problems relative to advanced algorithms and their applications.

Learning skills: students will be able to adapt the acquire knowledge to new contexts as well and to understand the limits of applicability of algorithm techniques.

Brief description of the course topics:

• Foundation of probability
• Probabilistic analysis of algorithms
• Randomized algorithms: Las Vegas vs Montecarlo
• Brief introduction to NP-hard andNP-complete problems
• Examples of approximation algorithms

We will use some parts of the following textbooks

1. TH Cormen, CE Leiserson, RL Rivest, C Stein, Introduction to Algorithms

2. R Motwani, P Raghavan, Randomized Algorithms

3. DP Williamson, DB Shmoys, The Design of Approximation Algorithms