Roberto DE PRISCO | Advanced Algorithms
Roberto DE PRISCO Advanced Algorithms
cod. 0522500064
ADVANCED ALGORITHMS
| 0522500064 | |
| DIPARTIMENTO DI INFORMATICA | |
| EQF7 | |
| COMPUTER SCIENCE | |
| 2017/2018 |
| YEAR OF COURSE 1 | |
| YEAR OF DIDACTIC SYSTEM 2016 | |
| PRIMO SEMESTRE |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| INF/01 | 7 | 56 | LESSONS | |
| INF/01 | 2 | 16 | LAB |
| Objectives | |
|---|---|
| Knowledge and Understanding This class aims at providing advanced knowledge in the field of algorithms. Applying Knowledge and Understanding Enhancing the student’s skills in solving algorithmic problems. |
| Prerequisites | |
|---|---|
| IT IS NECESSARY TO HAVE KNOWLEDGE OF DATA STRUCTURE, BASIC ALGORITHMS, BASIC MATHEMATICS AND BASIC PROBABILITY THEORY. |
| Contents | |
|---|---|
| THE SYLLABUS OF THE COURSE CONTAINS THE FOLLOWING TOPICS. •HARD PROBLEMS AND THE CLASSES P AND NP: REDUCTIONS, INDEPENDENT SET, VERTEX COVER, SET COVER, SET PACKING, SAT, 3SAT, PSPACE, NP-HARD PROBLEMS •BRUTE FORCE SEARCH AND BACKTRACKING •APPROXIMATION ALGORITHMS: LOAD BALANCING, VERTEX COVER, KNAPASACK •RANDOMIZED ALGORITHMS: MIN GLOBAL CUT, MAX-3SAT, ORDER STATISTIC, QUICKSORT. •ONLINE ALGORITHMS. •DISTRIBUTED ALGORITHMS: CONSENSUS, IMPOSSIBILITY RESULTS AND ALGORITHMS FOR VARIOUS MODEL, FROM SYNCHRONOUS TO ASYNCHRONOUS, WITH STOP AND BYZANTINE FAILURES. |
| Teaching Methods | |
|---|---|
| LECTURES. |
| Verification of learning | |
|---|---|
| WRITTEN AND ORAL EXAM. |
| Texts | |
|---|---|
| "ALGORITHM DESIGN", KLEINBERG, TARDOS. EDITOR: PEARSON, 2014 “DISTRIBUTED ALGORITHMS”, NANCY LYNCH. EDITOR: MORGAN KAUFFMAN |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2019-05-14]
