ADVANCED ALGORITHMS AND PROGRAMMING METHODS - 1

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, will introduce distributed algorithms, and we will show some applications of such algorithms in the filed of robotics.The student will acquire some skills needed to develop and analyse algorithms that are more advanced than those studied during the bachelor degree.

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 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.

A basic algorithm and probability course.

For the practical project students will need some competences acquired in Advanced Algorithms mod II.

Revision of NP-completeness concepts

Approximation Algorithms:
- vertex cover problem
- load balancing problem
- center selection problem
- metric TSP problem
- weighted vertex cover problem

Local search techniques
- Gradient Discent
- Metropolis Algorithm
- Simulated Annealing
- Hopfield Neural Networks
- An algorithm for the Max cut problem
Genetic Algorithms
Nash Equilibrium

Randomized Algorithms
- Classification (numerical, Monte Carlo, Las Vegas)
- The contention resolution problem
- Randomized quicksort
- Buffon's algorithm

Distributed algorithms
- Model and complexity measures
- Interconnection networks and network properties;
- The broadcast problem
- The distributed spanning tree construction
- Shout, Shout+ algorithm
- distributed DFS
- the leader election problem
- the saturation algorithm on trees
- the computation of the minimum
- the ranking problem
- P2P systems
- Mobile agents and robots: models and algorithms

[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] Slides of the Advanced Algorithms course

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.
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 first twenty students with highest score in the first partial exam will be able to replace the second partial exam with a practical project to be done in group. For the project the students will have to design a distributed algorithm and to implement it using real robots that are programmable using the C language, etc.. The students will then have to write a report by their own and will have to give a practical demonstration (in group). These students will also need to prove (by frequency signatures) that they have partecipated to at least 3/4 of the classes on the second part of the course.

Course organized in lectures in class, exercises, some laboratory activities.

English

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

written and oral