ADVANCED ALGORITHMS AND PROGRAMMING METHODS - 1

The course provides basic techniques for the development and analysis of advanced algorithms.

Basic algorithm 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

written and oral

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. For those that attend classes we will also offer two partial exams, one in the middle of the course 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. The students will then have to write a report by their own and will have to give a practical demonstration (in group).

Lectures in class

English

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

• Course with sustainable contents
• University credits of sustainability: 5
• Lecture notes, material for reference or for self-assessment available online or as e-book
• E-learning, moodle platforms