Diodato FERRAIOLI | DESIGN AND ANALYSIS OF ALGORITHMS
Diodato FERRAIOLI DESIGN AND ANALYSIS OF ALGORITHMS
cod. 0623200001
DESIGN AND ANALYSIS OF ALGORITHMS
| 0623200001 | |
| DEPARTMENT OF INFORMATION AND ELECTRICAL ENGINEERING AND APPLIED MATHEMATICS | |
| EQF7 | |
| INFORMATION ENGINEERING FOR DIGITAL MEDICINE | |
| 2024/2025 |
| OBBLIGATORIO | |
| YEAR OF COURSE 1 | |
| YEAR OF DIDACTIC SYSTEM 2022 | |
| AUTUMN SEMESTER |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| INF/01 | 5 | 40 | LESSONS | |
| INF/01 | 4 | 32 | EXERCISES |
| Objectives | |
|---|---|
| THE COURSE PROVIDES METHODOLOGIES AND TOOLS FOR ANALYZING A PROBLEM, DESIGNING AN EFFICIENT SOLUTION. EVENTUALLY USING ADVANCED PROGRAMMING TECHNIQUES AND DATA STRUCTURES, AND IMPLEMENTING IT IN AN OBJECT-ORIENTED PROGRAMMING LANGUAGE. KNOWLEDGE AND UNDERSTANDING STUDENTS WILL LEARN ADVANCED PROGRAMMING TECHNIQUES AND DATA STRUCTURES. THEY WILL LEARN THE IMPLEMENTATION OF THE MOST RELEVANT DATA STRUCTURES INCLUDED IN STANDARD LIBRARIES. THEY WILL LEARN TO UNDERSTAND TERMINOLOGY USED IN THE CONTEXT OF ALGORITHM DESIGN. APPLYING KNOWLEDGE AND UNDERSTANDING STUDENTS WILL LEARN TO USE PROPOSED PROGRAMMING TECHNIQUES AND ADVANCED DATA STRUCTURES TO SOLVE COMPLEX PROBLEMS. THEY WILL BE ABLE TO IMPLEMENT ALGORITHMS AND DATA STRUCTURES IN AN OBJECT-ORIENTED PROGRAMMING LANGUAGE USING THE FRAMEWORK OF PATTERN DESIGN. |
| Prerequisites | |
|---|---|
| IT IS SUPPOSED: FLUENCY IN OBJECT-ORIENTED PROGRAMMING, KNOWLEDGE OF BASIC DATA STRUCTURES AND FUNDAMENTALS OF PROGRAMMING, KNOWLEDGE OF ALGORITHM ANALYSIS TECHNIQUES. |
| Contents | |
|---|---|
| DIDACTIC UNIT 1: PYTHON (LECTURE/PRACTICE HOURS 4/0) - 1 (2 HOURS LECTURE): INTRODUCTION TO PYTHON - 2 (2 HOURS LECTURE): PYTHON: CLASSES AND FUNCTIONS KNOWLEDGE AND UNDERSTANDING: KNOWLEDGE OF THE KEY CONCEPTS AND TERMS OF PYTHON LANGUAGE APPLYING KNOWLEDGE AND UNDERSTANDING: ABILITY OF WRITING SIMPLE PYTHON PROGRAMS DIDACTIC UNIT 2: BALANCED BINARY SEARCH TREES (LECTURE/PRACTICE HOURS 11/6) - 3 (3 HOURS LECTURE): ABSTRACT DATA TYPES AND DATA STRUCTURES - 4 (2 HOURS LECTURE): BINARY SEARCH TREES - 5 (2 HOURS LECTURE): AVL TREES - 6 (3 HOURS PRACTICE): BINARY SEARCH TREES AND AVL TREES - 7 (2 HOURS LECTURE): MULTIWAY SEARCH TREES AND B-TREES - 8 (2 HOURS LECTURE): RED-BLACK TREES - 9 (3 HOURS PRACTICE): BALANCED BINARY SEARCH TREES KNOWLEDGE AND UNDERSTANDING: KOWLEDGE OF THE FUNCTIONS OF THE DICTIONARY ADT; KNOWLEDGE OF THE INSERTION, DELETION, UPDATE, AND BALANCING OPERATION ALGORITHMS IN A BINARY SEARCH TREE APPLYING KNOWLEDGE AND UNDERSTANDING: ABILITY OF CHOOSING THE BEST DATA STRUCTURE FOR THE REQUIRED OPERATIONS; ABILITY TO DESIGN VARIANTS TO THE IMPLEMENTATION SEEN DURING THE LESSONS DIDACTIC UNIT 3: HASH TABLES AND PRIORITY QUEUES (LECTURE/PRACTICE HOURS 4/5) - 10 (2 HOURS LECTURE): HASH TABLE - 11 (3 HOURS PRACTICE): HASH TABLE - 12 (2 HOURS LECTURE): PRIORITY QUEUES - 13 (2 HOURS PRACTICE): PRIORITY QUEUES KNOWLEDGE AND UNDERSTANDING: KNOWLEDGE OF THE INSERTION, DELETION, RESEARCH ALGORITHMS IN HASH TABLES AND PRIORITY QUEUES APPLYING KNOWLEDGE AND UNDERSTANDING: ABILITY OF CHOOSING THE BEST DATA STRUCTURE FOR THE REQUIRED OPERATIONS; ABILITY TO DESIGN VARIANTS TO THE IMPLEMENTATIONS SEEN DURING THE LESSONS DIDACTIC UNIT 4: PATTERN MATCHING ALGORITHMS (LECTURE/PRACTICE HOURS 5/2) - 14 (2 HOURS LECTURE): PATTERN MATCHING AND SUFFIX TRIES - 15 (3 HOURS LECTURE): SUFFIX TRIES APPLICATIONS - 16 (2 HOURS PRACTICE): SUFFIX TRIES KNOWLEDGE AND UNDERSTANDING: KNOWLEDGE OF PATTERN MATCHING ALGORITHMS, AND OF THE ALGORITHMS FOR BUILDING AND USING A SUFFIX TRIE APPLYING KNOWLEDGE AND UNDERSTANDING: ABILITY OF DESIGNING SUFFIX TRIES FOR SOLVING SPECIFIC PROBLEMS DIDACTIC UNIT 5: PROGRAMMING TECHNIQUES (LECTURE/PRACTICE HOURS 6/9) - 17 (2 HOURS LECTURE): GREEDY PROGRAMMING - 18 (3 HOURS PRACTICE): GREEDY PROGRAMMING - 19 (2 HOURS LECTURE): DYNAMIC PROGRAMMING - 20 (3 HOURS PRACTICE): DYNAMIC PROGRAMMING - 21 (2 HOURS LECTURE): LOCAL SEARCH - 22 (3 HOURS PRACTICE): PROGRAMMING TECHNIQUES KNOWLEDGE AND UNDERSTANDING: KNOWLEDGE OF PROGRAMMING TECHNIQUES PRINCIPLES AND LIMITATIONS APPLYING KNOWLEDGE AND UNDERSTANDING: ABILITY OF ANALYZING A REAL PROBLEM AND TO FIND THE BEST PROGRAMMING TECHNIQUE FOR SOLVING IT; ABILITY TO DESIGN EFFICIENT ALGORITHM WITH THE STUDIED PROGRAMMING TECHNIQUES DIDACTIC UNIT 6: GRAPHS (LECTURE/PRACTICE HOURS 12/8) - 23 (2 HOURS LECTURE): GRAPHS - 24 (2 HOURS LECTURE): GRAPH VISIT - 25 (3 HOURS PRACTICE): UNWEIGHTED GRAPHS - 26 (2 HOURS LECTURE): SHORTEST PATHS - 27 (2 HOURS LECTURE): MINIMUM SPANNING TREES - 28 (3 HOURS PRACTICE): WEIGHTED GRAPHS - 29 (2 HOURS LECTURE): MAX FLOW - 30 (2 HOURS PRACTICE): MAX FLOW APPLICATIONS - 31 (2 HOURS LECTURE): APPROXIMATION ALGORITHMS KNOWLEDGE AND UNDERSTANDING: KNOWLEDGE OF GRAPHS KEY CONCEPTS, OF THEIR IMPLEMENTATIONS ADVANTAGES AND DRAWBACKS, AND OF THE KNOWN ALGORITHMS FOR SOLVING SPECIFIC GRAPH PROBLEMS APPLYING KNOWLEDGE AND UNDERSTANDING: ABILITY TO DESIGN ALGORITHMS FOR PROBLEMS THAT CAN BE SOLVED BY USING GRAPH AND THE KNOWN GRAPH ALGORITHMS TOTALE LECTURE/PRACTICE HOURS/LABORATORIO 42/30/0 |
| Teaching Methods | |
|---|---|
| THE COURSE CONSISTS IN LECTURES (42 HOURS) AND GUIDED EXERCISES (30 HOURS). DURING THE LECTURES ALGORITHMS AND DATA STRUCTURES ARE PRESENTED AND THEIR APPLICATIONS TO REAL-LIFE PROBLEMS ARE DISCUSSED. IN THE GUIDED EXERCISES, TASKS ARE PROVIDED AIMING TO APPLY, ANALYZE, DESIGN, AND IMPLEMENT THE STUDIED ALGORITHMS AND THEIR VARIANTS. |
| Verification of learning | |
|---|---|
| THE FINAL EXAM IS DESIGNED TO EVALUATE AS A WHOLE THE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS PRESENTED IN THE COURSE, AND THE ABILITY TO APPLY SUCH KNOWLEDGE IN DESIGNING ALGORITHMS AND IMPLEMENTING THEM IN AN OBJECT-ORIENTED PROGRAMMING LANGUAGE TO SOLVE NON TRIVIAL COMBINATORIAL PROBLEMS. THE EXAM CONSISTS OF A WRITTEN EXAM AND A DISCUSSION OF THE WRITTEN EXAM. THE WRITTEN EXAM CONSISTS OF FOUR EXERCISES AND AIMS TO EVALUATE THE ACQUIRED KNOWLEDGE ABOUT DATA STRUCTURES AND ADVANCED PROGRAMMING TECHNIQUES, AND THE ABILITY OF APPLYING AND IMPLEMENT THESE TOOLS. THE DISCUSSION WILL AIM TO ASSES IN MORE DETAILS THE ABILITY TO DESIGN, IMPLEMENT, AND ANALYZE ALGORITHMIC SOLUTION TO PROBLEMS RAISED DURING THE WRITTEN EXAM OR TO ITS VARIANTS. IN THE FINAL EVALUATION, EXPRESSED IN THIRTIES, THE EVALUATION OF THE WRITTEN EXAM WILL ACCOUNTS FOR 60% WHILE THE DISCUSSION ACCOUNTS FOR THE REMAINING 40%. THE CUM LAUDE MAY BE GIVEN TO STUDENTS WHO DEMONSTRATE THAT THEY CAN APPLY THE KNOWLEDGE AUTONOMOUSLY EVEN IN CONTEXTS OTHER THAN THOSE PROPOSED IN THE COURSE. |
| Texts | |
|---|---|
| M.T. GOODRICH, M. TAMASSIA, M.H. GOLDWASSER, “DATA STRUCTURES & ALGORITHMS IN PYTHON”, WILEY 2013 KLEINBERG, TARDOS, "ALGORITHM DESIGN", PRENTICE HALL, 2005. THE TEACHING MATERIAL IS AVAILABLE ON THE UNIVERSITY E-LEARNING PLATFORM (HTTP://ELEARNING.UNISA.IT) ACCESSIBLE TO STUDENTS USING THEIR OWN UNIVERSITY CREDENTIALS. SUGGESTED READINGS: T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, C. STEIN, “INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI”, SECONDA EDIZIONE, MCGRAW-HILL, 2005. M. VENTO, P. FOGGIA, “ALGORITMI E STRUTTURE DATI”, MCGRAW-HILL. P. MORIN, ”OPEN DATA STRUCTURES", (HTTP://WWW.OPENDATASTRCTURES.ORG). C. DEMETRESCU, I. FINOCCHI, G. ITALIANO, “ALGORITMI E STRUTTURE DATI”, MCGRAW HILL, 2008. |
| More Information | |
|---|---|
| THE COURSE IS HELD IN ENGLISH |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2024-11-18]
