Annalisa DE BONIS | Advanced Algorithmic Techniques For Distributed Systems
Annalisa DE BONIS Advanced Algorithmic Techniques For Distributed Systems
cod. 0522500105
ADVANCED ALGORITHMIC TECHNIQUES FOR DISTRIBUTED SYSTEMS
| 0522500105 | |
| DIPARTIMENTO DI INFORMATICA | |
| EQF7 | |
| COMPUTER SCIENCE | |
| 2017/2018 |
| YEAR OF COURSE 2 | |
| YEAR OF DIDACTIC SYSTEM 2016 | |
| SECONDO SEMESTRE |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| INF/01 | 6 | 48 | LESSONS |
| Objectives | |
|---|---|
| THE MAIN GOAL OF THE CLASS IS TO STUDY THE TECHNIQUE FOR DESIGNING AND ANALYSING DISTRIBUTED GRAPH ALGORITHMS, AND FOR PROVING THE LIMITATIONS OF THESE ALGORITHMS. THE TOPICS CAN BE GROUPED IN THE FOLLOWING THREE AREAS: LOCALITY IN GRAPH PROBLEMS: GRAPH COLORING, MAXIMAL INDEPENDENT SET, GRAPH DECOMPOSITON. THE PROBLEM OF CONGESTION: LOWER BOUNDS, RECENT DISTRIBUTED ALGORITHMS FOR MINIMUM SPANNING TREE AND SHORTEST PATHS. THE CLASS WILL ALSO ILLUSTRATE USEFUL ALGORITHMIC TOOLS LIKE GRAPH SPARSIFICATION AND SPANNERS. BROADCAST ALGORITHMS FOR WIRELESS NETWORKS: THE CLASS WILL COVER BOTH DETERMINISTIC ALGORITHMS AND RANDOMIZED ALGORITHMS. AS FAR AS IT CONCERNS DETERMINISTIC ALGORITHMS, IT WILL COVER RECENT ALGORITHMS BASED ON SELECTIVE FAMILIES. APPLYING KNOWLEDGE: • THE STUDENTS ARE EXPECTED TO BECOME FAMILIAR WITH THE MOST RELEVANT TECHNIQUES FOR DESIGNING AND ANALYSING DISTRIBUTED ALGORITHMS • THE STUDENTS ARE EXPECTED TO UNDERSTAND THE IMPACT THAT THE ABOVE TECHNIQUES HAVE ON A NUMBER OF CONCRETE PROBLEMS RELATED TO MODERN NETWORK COMMUNICATION TECHNOLOGIES. |
| Prerequisites | |
|---|---|
| THE STUDENTS SHOULD HAVE ACQUIRED THE BASIC NOTIONS OF MATHEMATICS AND SHOULD ALSO HAVE LEARNED THE BASIC CONCEPTS OF THE DESIGN AND ANALYSIS OF ALGORITHMS. |
| Contents | |
|---|---|
| THE CLASS WILL FOCUS ON THE FOLLOWING SUBJECTS: • CLASS OVERVIEW AND INTRODUCTORY NOTIONS. • GRAPH COLORING: GRAPH GOLORING IN CONSTANT-DEGREE GRAPHS, ALGORITHMS AND LOWER BOUNDS; KUHN'S ALGORITHM THROUGH DEFECTIVE-COLORING • MAXIMAL INDEPENDENT SET: RANDOMIZED ALGORITHMS, APPLICATIONS TO RELATED PROBLEMS SUCH AS MATCHING AND VERTEX COLORING. • NETWORK DECOMPOSITIONS: THE DISTRIBUTED ALGORITHM OF AWERBUCH, GOLDBERG, LUBY, PLOTKIN. • MINIMUM SPANNING TREES: THE ALGORITHM OF KUTTEN AND PELEG. • LOWER BOUNDS ON COMMUNICATION COMPLEXITY: LOWER BOUNDS FOR MINIMUM SPANNING TREE AND SINGLE SOURCE SHORTEST PATHS. • SHORTEST PATHS: APPROXIMATION ALGORITHMS FOR SINGLE SOURCE SHORTEST PATHS AND A LINEAR DETERMINISTIC ALGORITHM FOR ALL PAIRS SHORTES PATHS. • SPANNERS AND SPARSIFICATION. • BROADCAST IN WIRELESS NEWORKS: RANDOMIZED ALGORITHMS, DETERMINISTIC ALGORITHMS BASED ON SELECTIVE FAMILIES. |
| Teaching Methods | |
|---|---|
| THE COURSE COINSISTS IN THEORETICAL LESSONS AND IN SEMINARS THAT MAY INVOLVE STUDENTS IN PRESENTING SPECIFIC TOPICS. |
| Verification of learning | |
|---|---|
| THERE WILL BE A FINAL ORAL EXAMINATION CONSISTING IN • A DISCUSSION ON THE THEORETICAL SUBJECTS AND THE METHODOLOGIES LISTED IN THE SYLLABUS • A BRIEF SEMINAR ON A TOPIC TO BE SELECTED AMONG A CHOICE OF TOPICS PROPOSED BY THE INSTRUCTOR |
| Texts | |
|---|---|
| TEACHING MATERIAL WILL BE MADE AVAILABLE IN CLASS AND ON THE CLASS WEBSITE. |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2019-05-14]
