Contribution of the course to the overall degree programme goals
The course provides basic techniques for the development and analysis of advanced algorithms.
Expected learning outcomes
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.
Basic algorithm course. For the practical project students will need some competences acquired in Advanced Algorithms mod II.
Revision of NP-completeness concepts
- 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
- Classification (numerical, Monte Carlo, Las Vegas)
- The contention resolution problem
- Randomized quicksort
- Buffon's algorithm
- 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. 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).
Course organized in lectures in class, exercises, some laboratory activities.
Students have to register on the course Web page of the e-learning platform available at the link moodle.unive.it
Type of exam
written and oral
2030 Agenda for Sustainable Development Goals
This subject deals with topics related to the macro-area "Cities, infrastructure and social capital" and contributes to the achievement of one or more goals of U. N. Agenda for Sustainable Development
Last update of the programme: 10/04/2018
If you close the banner, only essential cookies will be automatically activated
Ca' Foscari University of Venice, as part of its institutional aims and in fulfillment of the obligations set forth in article 13 of the EU Regulation 2016/679 ("Regulation"), gives you information regarding the processing of personal data collected by cookies and/or similar technologies when you visit the www.unive.it website (“Website”). Cookies are small pieces of information that a website sends to the user’s device where it is automatically stored and then sent back to the same website or to a third party every time that the website is visited using the same device.
In this notice, the term “cookie” will mean cookies as defined above as well as any other similar tracking technology used in the Website.
1. Data Controller
The data controller is Ca' Foscari University of Venice, with headquarters in Dorsoduro n. 3246, 30123 Venice (VE), legally represented by the Rector pro tempore.
2. Data Protection Officer
The University has appointed a "Data Protection Officer" ("DPO"), who can be contacted by writing to the email address: email@example.com or to the following address: Ca' Foscari University, Venice, Data Protection Officer, Dorsoduro n. 3246, 30123 Venice (VE).
3. Types of cookies, data collect, purposes and legal basis
The cookies used on the website are (please refer to the cookie list for specific information on each cookie):
essential cookies: cookies that are necessary to support the login system and the access to the “Personal Area” of the Website as well as to remember users’ cookie preferences.
Personal data associated with these cookie is: user’s IP address, date and time of the visit, means of data transfer, requested resource, response, response size in byte, link connected to the user requesting the resource, user’s operating system, browser and device used. The legal basis for this processing activity is represented by art. 6.1.b) (“performance of a service asked by the data subject”) and art. 6.1.e) of the Regulation (“execution of a task of public interest or connected to the exercise of public powers''). Being the University is a public body and it is required to have a website where the users can find useful information on its activities (artt. 53 e 54 D.lgs. n. 82/2005). You can disable these cookies at any time by clicking on the “click here to change your cookie preferences” button, this action will only have an effect on the navigation of the Personal Area.
analytics cookies: cookies that collect aggregated and statistical data on the navigation of the Website aimed at measuring the number of visits for each page of the Websites as well as the performance and the usability of the Website. The analytics cookies used on the Website are “Web Analytics Italia” set by the Agenzia per l’Italia Digitale (AGID). Personal data associated with these cookies is: user’s IP address, date and time of the visit, means of data transfer, requested resource, response, response size in byte, link connected to the user requesting the resource, user’s operating system, browser and device used, number of pages visited, ecc. The legal basis for this processing activity is represented by art. 6.1.e) of the Regulation (“execution of a task of public interest or connected to the exercise of public powers''), as the University aims at collecting statistical data on the visits of its Website pages especially with regards to the pages of “Amministrazione Trasparente”. You can disable these cookies at any time by clicking on the “click here to change your cookie preferences” button, this action will have no effect on your navigation.
third party cookies (social media and profiling): these cookies are set by third parties that collect the data in order to analyze the navigation and the preferences of the users. On the website, there are cookies set by Facebook called Facebook-Pixel, aimed at collecting data to target promotional content to specific users, and by Google namely Google-Youtube that allow users to watch Youtube videos on the Website and the University to measure the performance of its communication campaigns. These cookies are managed by Facebook and Google respectively and the University only processes anonymous and statistical information collected by them, who act as joint controllers on the basis of the CJEU ruling n. C-210/16 (5 June 2018). The legal basis for this processing activity is represented by art. 6.1.a) of the Regulation (“consent of the data subject''). The first time you land on the Website, a banner pops up asking whether you consent to enable these cookies. If you do not consent or withdraw consent at a later time through the “click here to change your cookie preferences” button, this will have no effect on your navigation.
You can always manage your cookie preferences through the browser setting. If you disable all cookies, please note that some activities on the website will not be possible anymore (i.e. the ones on the pages accessible in the Personal Area). To find out more on how to manage cookies through browser settings, please visit:
The processing of personal data will be carried out by authorized employees (in compliance with Article 29 of the Regulation and art. 2-quaterdecies of D. lgs. 196/2003), with the use of computerized procedures, adopting appropriate technical and organizational measures to protect them from unauthorized or illegal access, destruction, loss of integrity and confidentiality, even if accidental in nature.
5. Data retention
For information on the retention period of each cookie, please refer to the list below.
6. Recipients and categories of recipients of personal data and data transfer outside the European Economic Area
For the purposes set out above, in addition to specifically authorized employees and collaborators of the University, personal data may also be processed by those who execute outsourced activities on behalf of the University in their capacity as data processors (the updated list is available at: https://www.unive.it/pag/36643/).
Personal data collected by third party cookies may be transferred outside the European Economic Area (EEA) in compliance with the provisions of the Regulation.
7. Data subjects rights and how to exercise them
As a data subject, you have the right to obtain from the University, in the cases provided for by the Regulation, the access, the rectification and the erasure of your personal data as well as ask for the limitation of the processing of your personal data or to object to the data processing itself (articles 15 and following of the Regulation). The request can be submitted, without any particular formal procedures, by contacting the Data Protection Officer directly at firstname.lastname@example.org or by sending a communication to the following address: Ca' Foscari University of Venice - Data Protection Officer, Dorsoduro 3246, 30123 Venice. Alternatively, you can contact the Data Controller, by writing a PEC (certified email) to email@example.com.
Data subjects, who believe that the processing of their personal data is in violation of the provisions of the Regulation, have the right to file a complaint with the Data Protection Authority, as provided for by art. 77 of the Regulation, or to take legal action (art. 79 of the Regulation).
Appendix on social media:
In addition to the privacy notice published at: www.unive.it/pag/29567, the University provides you with information on the processing of your personal data collected through its social media pages (Facebook, Instagram). In particular, the University only processes anonymous and statistical information collected by the social media providers, who act as joint controllers on the basis of the CJEU ruling n. C-210/16 (5 June 2018). Moreover, the University informs you that when you leave a comment or a post on its social media pages, it will process your data only to administer your request/comment.
Last updated: 27/07/2022
List of cookies
Last update of the list of cookies: 27/7/2022
They maintain the session data of the SingleSignOn.