ADVANCED AND DISTRIBUTED ALGORITHMS

The course provides basic techniques for the development and analysis of advanced algorithms such as approximation algorithms, genetic algorithms, randomized algorithms and local search techniques. We will then introduce distributed systems and we will show some applications of such algorithms in the filed of security and robotics.The student will acquire some skills needed to develop and analyse advanced algorithms.

Attendance and active participation in the training activities proposed by the course (lectures, exercises, laboratory activities) and individual study will enable students / students to:

1 Knowledge and understanding
1.1. acquire the theoretical foundations and advanced knowledge of classical topics of computer science such as approximation, genetic, probabilistic, distributed algorithms and local research techniques;
1.1. acquire knowledge of some practical applications of algorithms distributed to the field of security and robotics.
2. Ability to apply knowledge and understanding
2.1. know how to use the knowledge acquired to solve algorithmic problems in the real world.
3. Ability to judge
3.1. know how to choose and analyze the most appropriate algorithm to be used in a specific real context.

Suggested to have followed a basic algorithm, programming and probability course.

Revision of NP-completeness concepts.

Approximation Algorithms.
Local search techniques.
Genetic Algorithms.
Randomized Algorithms.

Distributed algorithms
- Model and complexity measures
- Interconnection networks and network properties;
- Different problems and their solution with the help of distributed algorithms (e.g., the broadcast problem, the distributed spanning tree construction,
the leader election problem, computations on trees, searches in P2P systems).
- Examples of applications to security (Bitcoin) and robotics (mobile robots).

[CLRS] Introduction to Algorithms, third edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

[KT] Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley, 2005

[S] Design and Analysis of Distributed Algorithms, Nicola Santoro, Whiley- Interscience, 2007

[L] Lucidi del corso

The verification of the knowledge is done through the passing of a written exam. The oral exam is compulsory for those who are almost sufficient (between 15 and 17), optional for those which have a sufficient grade. The written exam (and the eventual oral exam) are required to verify the knowledge of the course contents. The oral exam is worth a maximum of 6 bonus points. If passed positively, the bonus is added to the mark of the written test, forming the final mark (if it is less than 18, the exam is not passed). If, on the other hand, the oral test is evaluated negatively, the bonus is subtracted from the starting mark and the student may not even pass the entire exam.

We will also offer two partial exams, one in the middle of the course (depending on the approval of the didactic board) and one after the end of the course, that can be taken only by passing the first part. Passing both parts will allow the student to be exonerated from the global written exam. The final mark will be given by the average of the marks of the two tests. The second intermediate exam might be substituted by a practical project with robots. In case of too many requests, the project will be assigned to the students the with highest grades in the first intermediate exam.

Course organized in lectures in class, standard and online exercises.

English

Students have to register on the course Web page of the e-learning platform available at the link moodle.unive.it.
The course will be in English.

written and oral