Annalisa DE BONIS | ALGORITHM DESIGN
Annalisa DE BONIS ALGORITHM DESIGN
cod. 0512100043
ALGORITHM DESIGN
| 0512100043 | |
| DIPARTIMENTO DI INFORMATICA | |
| EQF6 | |
| COMPUTER SCIENCE | |
| 2020/2021 |
| OBBLIGATORIO | |
| YEAR OF COURSE 2 | |
| YEAR OF DIDACTIC SYSTEM 2017 | |
| SECONDO SEMESTRE |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| INF/01 | 6 | 48 | LESSONS | |
| INF/01 | 3 | 24 | EXERCISES |
| Objectives | |
|---|---|
| THE MAIN GOALS OF THE CLASS ARE THE FOLLOWING: - TO PROVIDE THE STUDENT WITH GENERAL METHODS AND KNOWLEDGE FOR THE DESIGN OF EFFICIENT ALGORITHMS - TO GIVE THE STUDENTS TOOLS FOR THE ANALYSIS OF RESOURCES (SPACE AND TIME) NEEDED BY THE ALGORITHMS - TO PROVIDE A CATALOGUE OF THE MOST KNOWN AND EFFICIENT ALGORITHMS FOR BASIC COMPUTATIONAL PROBLEMS (SORTING, SEARCHING, OPTIMIZATION, OPTIMIZATION OF RESOURCES, ETC.) EXPECTED LEARNING ACHIEVEMENTS: KNOWLEDGE AND COMPREHENSION - KNOWLEDGE OF ASYMPTOTIC NOTATIONS USED IN THE ANALYSIS OF ALGORITHMS - KNOWLEDGE OF METHODS FOR ESTIMATING THE RESOURCES USED BY ALGORITHMS - KNOWLEDGE OF THE DIVIDE AND CONQUER METHODOLOGY - KNOWLEDGE OF THE DYNAMIC PROGRAMMING METHODOLOGY - KNOWLEDGE OF THE GREEDY METHODOLOGY - KNOWLEDGE OF THE TECHNIQUES FOR TRAVERSING THE GRAPHS - KNOWLEDGE OF METHODS FOR COMPUTING SHORTEST PATHS IN GRAPHS - KNOWLEDGE OF METHODS FOR COMPUTING SPANNING TREES OF MINIMUM WEIGHT IN GRAPHS - KNOWLEDGE OF THE BACKTRACKING METHODOLOGY - KNOWLEDGE OF THE BRANCH AND BOUND METHODOLOGY ABILITY TO APPLY KNOWLEDGE AND UNDERSTANDING - ABILITY TO EVALUATE THE ASYMPTOTIC COMPLEXITY OF ALGORITHMS - ABILITY TO DESIGN ALGORITHMS BASED ON THE DIVIDE AND CONQUER METHODOLOGY - ABILITY TO DESIGN ALGORITHMS BASED ON THE DYNAMIC PROGRAMMING METHODOLOGY - ABILITY TO DESIGN ALGORITHMS BASED ON THE GREEDY METHODOLOGY - ABILITY TO DESIGN ALGORITHMS ON GRAPHS - ABILITY TO DESIGN ALGORITHMS BASED ON THE BACKTRACKING METHODOLOGY - ABILITY TO DESIGN ALGORITHMS BASED ON THE BRANCH AND BOUND METHODOLOGY AUTONOMY OF JUDGMENT THE STUDENT WILL BE ABLE TO EVALUATE INDEPENDENTLY: - THE EFFICIENCY (OR NOT) OF AN ALGORITHM - THE CORRECTNESS (OR NOT) OF AN ALGORITHM - THE APPLICABILITY DOMAIN OF THE DIVIDE AND CONQUER METHODOLOGY AND ITS USAGE APPROPRIATENESS - THE DOMAIN OF APPLICABILITY OF THE DYNAMIC PROGRAMMING METHODOLOGY AND ITS USAGE APPROPRIATENESS - THE APPLICABILITY DOMAIN OF THE GREEDY METHODOLOGY AND ITS USAGE APPROPRIATENESS - THE APPLICABILITY DOMAIN OF THE BACKTRACKING METHODOLOGY AND ITS USAGE APPROPRIATENESS - THE APPLICABILITY DOMAIN OF THE BRANCH AND BOUND METHODOLOGY AND ITS USAGE APPROPRIATENESS COMMUNICATION SKILLS THE STUDENT WILL BE ABLE TO PARTICIPATE IN TECHNICAL CONVERSATIONS ABOUT THE DESIGN AND ANALYSIS OF ALGORITHMS. THE STUDENT WILL ALSO BE ABLE TO ILLUSTRATE THE DIFFERENT TECHNIQUES FOR THE DESIGN OF ALGORITHMS (DIVIDE AND CONQUER, DYNAMIC PROGRAMMING, GREEDY, BACKTRACKING AND BRANCH AND BOUND). |
| Prerequisites | |
|---|---|
| STUDENTS SHOULD HAVE ACQUIRED THE NOTIONS OF MATHEMATICS AS TAUGHT IN THE PREVIOUS ACADEMIC YEARS AND THE ABILITY TO DEVELOP LOGICAL REASONING. THEY SHOULD ALSO HAVE LEARNED THE BASIC CONCEPTS OF AN INTRODUCTORY CLASS IN DATA STRUCTURES. |
| Contents | |
|---|---|
| THEORETICAL LESSONS: 48 HOURS EXERCISE LESSONS: 24 HOURS 11. INTRODUCTION TO THE BIG-O, OMEGA, AND THETA NOTATIONS, AND THEIR APPLICATIONS TO THE ANALYSIS OF ALGORITHMS (4 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS). 2. RECURRENCE RELATIONS FOR THE ANALYSIS OF RECURSIVE ALGORITHMS AND METHODS FOR THEIR SOLUTIONS (2 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS). 3. THE DIVIDE AND CONQUER TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS). 4. DYNAMIC PROGRAMMING AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS). 5. GREEDY ALGORITHMS AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS) 6. GRAPHS AND GRAPHS ALGORITHMS, BREADTH FIRST SEARCH AND DEPTH FIRST SEARCH ON GRAPHS AND THEIR APPLICATIONS, DIRECTED ACYCLIC GRAPHS AND TOPOLOGICAL SORTING, SHORTEST PATHS IN EDGE-WEIGHTED GRAPHS AND ALGORITHMS FOR THEIR COMPUTATION, MINIMUM COST SPANNING TREES IN EDGE-WEIGHTED GRAPHS AND ALGORITHMS FOR THEIR COMPUTATION (8 HOURS OF THEORETICAL LESSONS + 6 OF EXERCISE LESSONS). 7. INTELLIGENT EXHAUSTIVE SEARCH: BACKTRACKING AND BRANCH-AND- BOUND AND EXAMPLES OF APPLICATIONS (4 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS). |
| Teaching Methods | |
|---|---|
| THIS CLASS INCLUDES THEORETICAL LECTURES WITH THE GOAL OF LEARNING THE BASIC TECHNIQUES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS, AND EXCERCISES-BASED LECTURES IN WHICH IT WILL BE EXPLAINED, WITH PLENTY OF EXAMPLES, HOW THE ACQUIRED THEORETICAL KNOWLEDGE MAY BE USED TO SOLVE ALGORITHMIC PROBLEMS OF PRACTICAL INTEREST. |
| Verification of learning | |
|---|---|
| THE FINAL GRADE IS EXPRESSED WITH A GRADE X OUT-OF-THIRTY. THE EXAM CONSISTS OF A WRITTEN TEST AND AN ORAL EXAM. THE WRITTEN TEST MAY BE REPLACED BY TWO MID-TERMS. THE WRITTEN TEST TAKES PLACE BEFORE THE ORAL TEST AND IT IS CONSIDERED PASSED WITH THE ACHIEVEMENT OF THE PRE-ESTABLISHED MINIMUM SCORE. WRITTEN TESTS WILL BE SPECIALLY DESIGNED TO VERIFY THE ACQUISITION BY THE STUDENT OF THE ABILITY TO APPLY ALGORITHMIC DESIGN AND ANALYSIS METHODOLOGIES TO SIMPLE CONCRETE PROBLEMS. THE ORAL TEST CONSISTS OF QUESTIONS AND DISCUSSION ON THE METHODOLOGIES STUDIED DURING THE COURSE. IT IS MAINLY INTENDED TO ASSESS THE LEVEL OF KNOWLEDGE AND UNDERSTANDING REACHED BY THE STUDENT. AS A RULE, THE FINAL GRADE IS THE ARITHMETIC AVERAGE OF THE WRITTEN AND ORAL TESTS EVALUATIONS. |
| Texts | |
|---|---|
| TEXTBOOKS: KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY. S. DASGUPTA, C.H. PAPADIMITRIOU, AND U.V. VAZIRANI. ALGORITHMS. MCGRAW-HILL FURTHER COURSE MATERIAL ALONG WITH THE NECESSARY SUPPORT TO STUDY AND TO PREPARE FOR THE EXAM ARE PROVIDED THROUGH THE LECTURERS' WEB PAGES AND THE E-LEARNING PLATFORM AT THE FOLLOWING URL HTTP://ELEARNING.INFORMATICA.UNISA.IT/ . |
| More Information | |
|---|---|
| IT IS REASONABLE TO ASSUME THAT AN AVERAGE OF TWO HOURS OF INDIVIDUAL STUDY ARE REQUIRED FOR EACH HOUR OF CLASS LESSON. |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2022-05-23]
