RANDOMIZED AND APPROXIMATION ALGORITHMS

Academic Year 2024/2025 - Teacher: Vincenzo CUTELLO

Expected Learning Outcomes

Knowledge and understanding: students will acquire the knowledge necessary to design and implement randomized and approximate algorithms.

Applying knowledge and understanding: students will learn how to apply the learnt techniques in various fields and, in particular, in the search for solutions of computationally hard combinatorial problems.

Making judgements: students will be able to evaluate the possibility of developing randomized and approximate algorithms in the search for algorithmic solution of problems in several application fields.

Communication Skills: they will also acquire the necesasry communications skills and an adequate and appropriate capacity of communicating and explaining problems related to advanced algorithms and their applications.

Learning skills: finally, students will gain the ability to adapt the acquired knowledge to new fields and to understand the application limits of algorithms techniques.

Course Structure

Lessons will be given in the classroom

Required Prerequisites

A good knowledge of discrete and continuous mathematics along with a deep knowledeg of Algorithms. I

Attendance of Lessons

Attendance is strongly advised to better understand the topics and how they are linked.

Detailed Course Content

Overall content of the course:

Basics of probabilty theory
Randomized algorithms
Probabilistic analysis of algorithms
Examples of NP-hard problems and approximate algorithms

Textbook Information

Presentation material and lecture notes provided by the professor and the following textbook

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

Course Planning

	Subjects	Text References
1	Introduction to Probability Theory	Appendix C
2	Probabilistic analysis of Algorithms	Chapter 5
3	Randomized Algorithms	Chapter 5
4	Introduction to NP-completemess	Chapter 34
5	Approximate Algorithms	Chapter 35
6	Examples of problems and software projects

Learning Assessment

Learning Assessment Procedures

Final exam will be oral and we will also discuss the software project the students will have prepared.

Examples of frequently asked questions and / or exercises

1.What is the expected value of this probability distribution?

2. What is the approximation ratio of this algorithm and what is its complexity?

Degree Course in

Computer Science