Computer science | ALGORITHM DESIGN
Computer science 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 COURSE HAS THE FOLLOWING OBJECTIVES: - PROVIDE THE STUDENT WITH METHODS AND KNOWLEDGE SUITABLE FOR THE DESIGN OF EFFICIENT ALGORITHMS - PROVIDE TOOLS FOR THE ANALYSIS OF RESOURCES (SPACE AND TIME) USED BY ALGORITHMS - PROVIDE A CATALOGUE OF THE MOST WELL-KNOWN AND EFFICIENT ALGORITHMS FOR BASIC COMPUTATIONAL PROBLEMS (SORTING, SEARCHING, RESOURCE OPTIMIZATION, ETC.) EXPECTED LEARNING OUTCOMES: KNOWLEDGE AND COMPRENSION ABILITY - KNOWLEDGE OF ASYMPTOTIC NOTATIONS USED IN ALGORITHM ANALYSIS - KNOWLEDGE OF METHODS FOR THE EVALUATION OF RESOURCES USED BY ALGORITHMS - KNOWLEDGE OF THE DIVIDE ET IMPERA METHODOLOGY FOR THE DESIGN OF ALGORITHMS - KNOWLEDGE OF THE DYNAMIC PROGRAMMING METHODOLOGY FOR THE DESIGN OF ALGORITHMS - KNOWLEDGE OF GREEDY METHODOLOGY FOR THE DESIGN OF ALGORITHMS - KNOWLEDGE OF THE TECHNIQUES OF GRAPHS EXPLORATIONS - KNOWLEDGE OF METHODS FOR CALCULATING MINIMUM PATHS IN GRAPHS - KNOWLEDGE OF METHODS FOR THE CALCULATION OF MST WITH A MINIMUM WEIGHT IN GRAPHS - KNOWLEDGE OF BACKTRACK METHODOLOGY - KNOWLEDGE OF BRANCH AND BOUND METHODOLOGY ABILITY TO APPLY KNOWLEDGE AND UNDERSTANDING - ABILITY TO EVALUATE THE ASYMPTOTIC COMPLEXITY OF ALGORITHMS - ABILITY TO DESIGN ALGORITHMS BASED ON DIVIDE AND IMPERA METHODOLOGY - ABILITY TO DESIGN ALGORITHMS BASED ON DYNAMIC PROGRAMMING METHODOLOGY - ABILITY TO DESIGN ALGORITHMS BASED ON GREEDY METHODOLOGY - ABILITY TO DESIGN ALGORITHMS ON GRAPHS - ABILITY TO DESIGN ALGORITHMS BASED ON THE BACKTRACK 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 CORRECTION (OR NOT) OF AN ALGORITHM - THE APPLICABILITY DOMAIN OF THE DIVIDE AND IMPERA METHODOLOGY AND ITS OPPORTUNITY OF USE - THE DOMAIN OF APPLICABILITY OF THE DYNAMIC PROGRAMMING METHODOLOGY AND ITS OPPORTUNITY OF USE - THE APPLICABILITY DOMAIN OF THE GREEDY METHODOLOGY AND ITS OPPORTUNITY OF USE - THE DOMAIN OF APPLICABILITY OF THE BACK TRACK METHODOLOGY AND ITS OPPORTUNITY OF USE - THE APPLICABILITY DOMAIN OF THE BRANCH AND BOUND METHODOLOGY AND ITS OPPORTUNITY OF USE COMMUNICATIVE SKILLS THE STUDENT WILL BE ABLE TO SUPPORT TECHNICAL CONVERSATIONS ABOUT THE PROJECT AND ANALYSIS OF ALGORITHMS. THE STUDENT WILL ALSO BE ABLE TO ILLUSTRATE THE DIFFERENT TECHNIQUES FOR THE ALGORITHM PROJECT (DIVIDE AND IMPERA, DYNAMIC PROGRAMMING, GREEDY, BACKTRACK AND BRANCH AND BOUND). |
| Prerequisites | |
|---|---|
| STUDENTS SHOULD HAVE ACQUIRED THE NOTIONS OF MATHEMATICS AS TAUGHT IN PREVIOUS ACADEMIC YEARS AND THE ABILITY TO DEVELOP LOGICAL REASONING. THEY SHOULD ALSO HAVE LEARNED AND MASTERED THE BASIC CONCEPTS OF AN INTRODUCTORY CLASS IN DATA STRUCTURES. |
| Contents | |
|---|---|
| 72 LESSON HOURS: (48 THEORY, 24 EXERCITATIONS) 1. INTRODUCTION TO THE ASYMPTOTIC NOTATIONS BIGOH, OMEGA, THETA AND THEIR APPLICATIONS TO THE ANALYSIS OF ALGORITHMS. 2. RECURRENCE RELATIONS FOR THE ANALYSIS OF RECURSIVE ALGORITHMS, AND METHODS FOR THEIR SOLUTIONS. 3. THE DIVIDE ET CONQUER TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF APPLICATIONS. 4. THE DINAMIC PROGRAMMING TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF APPLICATIONS. 5. THE GREEDY TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF APPLICATIONS. 6. GRAPHS AND GRAPHS ALGORITHMS. BREADTH FIRST AND DEPTH FIRST SEARCH ON GRAPHS AND THEIR APPLICATIONS. DIRECTED ACYCLIC GRAPHS AND TOPOLOGICAL SORTING. MINIMUM COST PATHS IN EDGE-WEIGHTED GRAPHS AND ALGORITHMS FOR THEIR COMPUTATION. MINIMUM COST SPANNING TREES IN EDGE-WEIGHTED GRAPHS AND ALGORITHMS FOR THEIR COMPUTATION. 7. INTELLIGENT EXHAUSTIVE SEARCH: BACKTRACKING, BRANCH-AND- BOUND AND EXAMPLES OF APPLICATIONS. |
| 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: 1. KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY. 2. S. DASGUPTA, C.H. PAPADIMITRIOU, AND U.V. VAZIRANI. ALGORITHMS. MCGRAW-HILL 3. CLASS NOTES PROVIDED BY THE TEACHER ADDITIONAL TEACHING MATERIAL (EXERCISES, TESTS FOR SELF-ASSESSMENT) WILL BE MADE AVAILABLE THROUGH THE TEACHERS PERSONAL WEB SITES). |
| More Information | |
|---|---|
| ATTENDING LESSONS AND EXERCITATIONS IS ADVISED. 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]
