Sciences
Subject: ALGORITMI DISTRIBUITI (A.A. 2023/2024)
master degree course in COMPUTER SCIENCE
| Course year | 2 |
|---|---|
| CFU | 9 |
| Teaching units |
Unit Algoritmi distribuiti
Information Technology (lesson)
|
| Exam type | oral |
| Evaluation | final vote |
| Teaching language | Italiano |
Teachers
Giacomo CABRI
Manuela MONTANGERO
Overview
The aim of this course is to provide theoretical and practical bases in the study and implementation of distributed algorithms, as well as fundamentals about complexity theory.
By the end of the course, students will be able to:
- study and design distributed algorithms;
- exploiting technologies for the development of distributed systems
Moreover, students will acknowledge the existence of NP-hard problems and of some techniques that might be used to approach them.
Admission requirements
Students are required to know:
- basics in algoritmica and data structures, as in a basic algorithm course,
- at least one programming language,
- mathematical skills at undergraduate calculus course level,
- operating systems, computer networks.
Course contents
The course takes place during the first semestre of the master program second year. The duration of the course is 63 hours (9 CFU), divided between theoretical and practical lectures.
There are two modules (6 CFU + 3CFU) held by different professors.
6 CFU Module. Contents:
- Course introduction, introduction to distributed computing and models (6 hours)
- Distributed computing fundamentals algorithms: leader election, broadcast, minimum spanning tree construction, routing (12 hours)
- Consensus problem with faults: link and node failures, bizantine failures (8 hours).
- Distributed data structure: hash tables, block-chains (8 hours)
- Complexity theory fundamentals: NP-completness, NP-hardness, example of approximation algorithms for selected NP-hard problems: Travelling Salesman Problem and Vertex Cover problem (8 hours).
3CFU Module. Contents:
- Socket programming (4 hours)
- Distributed file systems (4 hours)
- Object technologies for the development of distributed applications; issues; example: Java RMI (13 hours)
Distribution of hours among topics should be considered indicative, as it might vary according to the students responsiveness during lectures.
Teaching methods
Lectures (6 CFU) and laboratory exercises (3 CFU) will be held on-site. Attendance is not mandatory. The course is held in Italian but provided material is in English. All information about the course will be posted on the moodle page dedicated to the course. There students will find practical information concerning the course, as well as didactical material provided by professors (such as lecture slides, other useful studying material and adopted books).
Assessment methods
The exam is divided into two parts, one for each module of the course. - 6CFU Module: a 20-minute oral exam which aims to verify the knowledge of the concepts and algorithms studied in class, and the skills in analyzing and designing distributed algorithms; the mark of this part is 2/3 of the global mark; - 3CFU Module: presentation of a project where the students are required to develop a distributed software application in order to verify the skill to apply the concepts; the mark of this part is 1/3 of the global mark. The two parts might be taken in different periods, in whatever order the student preferes. The final mark will be computed when the student passes both parts, as the wighetd mean of the two scores. Exams will take place on-site. In all exams, the mark ranges from 18/30 (basic knowledge of the topics and partial skill to apply the knowledge) to 30/30 cum laude (full knowledge of the topic and excellent skill to apply the knowledge), ranging the middle scores on the base of the achievement of the expected learning results, included the transversal ones shown during the exam.
Learning outcomes
* Knowledge and understanding
At the end of the course, students will know technologies to develop distributed applications. Students will have knowledge of fundamental problems, standard techniques and data structures in a distributed environment. Moreover,
students will and understanding of some fundamental algorithmic standard techniques for exact or approximate solution of computationally hard problems.
* Applying knowledge and understanding
Students will be able to develop distributed software applications, being able to choose the most appropriate technologies and platforms. Moreover, students will be able to recognize difficult computational problems when they arise in real applications.
* Making judgments
Students will be able to choose independently or contribute, within a team, to the choice of the best solutions to problems dealt with in this course.
* Communication skills
Students will have acquired knowledge and skills that empower them to discuss, propose and effectively share problems, ideas and solutions in application fields where dealt with in this course arise.
* Lifelong learning skills
Students will be able to deal with new (known or unknown) problems of the same nature as those covered in the course which they eventually will have to face in their careers.
Readings
Per entrambi i moduli:
- i docenti forniranno del materiale, tra cui: appunti di lezioni di altre università italiane e straniere disponibili on-line e note e appunti scritti dal docente.
Per il modulo da 6 CFU, selezione di capitoli dai seguenti testi:
- T.H. Cormen, C.E. Leoserson, R.L. Rivest, C. Stein,
Introduction to Algorithms ,
Mc-Graw Hill, II o III Edizione
- Nicola Santoro
Design and Analysis of Distributed Algorithms
WILEY 2007