Gennaro PERCANNELLA | Algorithms and Data Structures
Gennaro PERCANNELLA Algorithms and Data Structures
cod. 0612700006
ALGORITHMS AND DATA STRUCTURES
| 0612700006 | |
| DEPARTMENT OF INFORMATION AND ELECTRICAL ENGINEERING AND APPLIED MATHEMATICS | |
| EQF6 | |
| COMPUTER ENGINEERING | |
| 2024/2025 |
| OBBLIGATORIO | |
| YEAR OF COURSE 2 | |
| YEAR OF DIDACTIC SYSTEM 2022 | |
| AUTUMN SEMESTER |
| SSD | CFU | HOURS | ACTIVITY | ||
|---|---|---|---|---|---|
| ALGORITMI E STRUTTURE DATI | |||||
| ING-INF/05 | 3 | 24 | LESSONS | ||
| ING-INF/05 | 3 | 24 | EXERCISES | ||
| ALGORITMI E STRUTTURE DATI | |||||
| INF/01 | 1 | 8 | LESSONS | ||
| INF/01 | 2 | 16 | LAB | ||
| Objectives | |
|---|---|
| THE COURSE ILLUSTRATES HOW TO DESIGN AND IMPLEMENT ALGORITHMS, USING BOTH ITERATIVE AND RECURSIVE TECHNIQUES, AND EVALUATING THE EFFICIENCY OF THE OBTAINED PROGRAMS; THE COURSE ALSO PRESENTS THE FUNDAMENTAL DATA STRUCTURES, SHOWING THEIR IMPLEMENTATION IN THE C LANGUAGE. KNOWLEDGE AND UNDERSTANDING ALGORITHMS AND BASIC DATA STRUCTURES: SORTING AND SELECTION ALGORITHMS DYNAMIC ARRAYS, LISTS, TREES, HASH TABLES, STACKS AND QUEUES. ITERATIVE AND RECURSIVE PROGRAMMING PARADIGMS. COMPARISON OF ALGORITHMS WITH RESPECT TO THEIR MEMORY AND EXECUTION TIME. APPLYING KNOWLEDGE AND UNDERSTANDING ANALYSIS OF TYPICAL PROBLEMS AND DESIGN AND IMPLEMENTATION OF APPLICATIONS THAT SOLVE THEM USING STANDARD ALGORITHMS AND DATA STRUCTURES IN THE C LANGUAGE, EVALUATING THEIR EFFICIENCY. IMPLEMENTATION OF SMALL-SCALE SOFTWARE PROJECTS USING BOTH INTEGRATED ENVIRONMENTS AND SEPARATE COMPILATION. |
| Prerequisites | |
|---|---|
| THE COURSE REQUIRES PREVIOUS KNOWLEDGE ABOUT THE C PROGRAMMING LANGUAGE. |
| Contents | |
|---|---|
| Didactic unit 1: Pointers, dynamic allocation, and structures (LECTURE/PRACTICE/LABORATORY HOURS 6/4/2) - 1 (2 Hours Lecture): Course introduction, operational semantics, pointers - 2 (2 Hours Lecture): Pointer arithmetics - 3 (2 Hours Lecture): Memory allocation, structures - 4 (2 Hours Exercise): Pointers, dynamic allocation - 5 (2 Hours Exercise): Structures - 6 (2 Hours Lab): Pointers, dynamic allocation, and structures. KNOWLEDGE AND UNDERSTANDING: Understand the concept of pointer APPLYING KNOWLEDGE AND UNDERSTANDING: Use pointers, implement the parameter passing to a function by reference, define and use structs, and dynamically allocate structs. Didactic unit 2: Recursion (LECTURE/PRACTICE/LABORATORY HOURS 4/4/2) - 7 (2 Hours Lecture): Introduction to recursion - 8 (2 Hours Lecture): Use of recursion in algorithms - 9 (2 Hours Exercise): Basic recursions - 10 (2 Hours Exercise): Advanced recursions - 11 (2 Hours Lab): Programming with recursion KNOWLEDGE AND UNDERSTANDING: Understand the recursion APPLYING KNOWLEDGE AND UNDERSTANDING: Design and implement a recursive function Didactic unit 3: Base algorithms and data structures (LECTURE/PRACTICE/LABORATORY HOURS 4/4/2) - 12 (2 Hours Lecture): Base algorithms: search algorithms, linear search, binary search, minimum and maximum - 13 (2 Hours Lecture): Base data structures: dynamic array, stack, queue - 14 (2 Hours Exercise): Base algorithms - 15 (2 Hours Exercise): Base data structures - 16 (2 Hours Lab): Base algorithms and data structures KNOWLEDGE AND UNDERSTANDING: know the base search algorithms and the base data structures (dynamic array, stack, queue) APPLYING KNOWLEDGE AND UNDERSTANDING: can use the abovementioned base data structures; can apply the search algorithms and those for the minimum and maximum search to the known data structures; given a specific problem, can choose the data structure to use Didactic unit 4: Lists (LECTURE/PRACTICE/LABORATORY HOURS 4/2/2) - 17 (2 Hours Lecture): Lists, iterative implementation - 18 (2 Hours Lecture): Lists, recursive implementation - 19 (2 Hours Exercise): Lists - 20 (2 Hours Lab): Lists KNOWLEDGE AND UNDERSTANDING: the list data structure and the functions to handle it APPLYING KNOWLEDGE AND UNDERSTANDING: design and implement the functions, implemented both in their iterative or recursive version, to handle a list Didactic unit 5: Computational complexity and sorting (LECTURE/PRACTICE/LABORATORY HOURS 6/4/0) - 21 (2 Hours Lecture): Computational complexity - 22 (2 Hours Lecture): Sorting algorithms: selection sort, insertion sort, bubble Sort - 23 (2 Hours Lecture): Merge sort, quick sort - 24 (2 Hours Exercise): Running time of algorithms - 25 (2 Hours Exercise): Running time of algorithms KNOWLEDGE AND UNDERSTANDING: the concept of computational complexity and the sorting algorithms APPLYING KNOWLEDGE AND UNDERSTANDING: compute the computational complexity of an algorithm, in both its iterative or recursive version; use the sorting algorithms on all the studied data structures Didactic unit 6: Trees (LECTURE/PRACTICE/LABORATORY HOURS 4/2/2) - 26 (2 Hours Lecture): Trees, iterative implementation - 27 (2 Hours Lecture): Trees, recursive implementation - 28 (2 Hours Exercise): Trees - 29 (2 Hours Lab): Trees KNOWLEDGE AND UNDERSTANDING: the tree data structure and the functions to handle it APPLYING KNOWLEDGE AND UNDERSTANDING: design and implement the functions, implemented both in their iterative or recursive version, to handle a tree Didactic unit 7: Hash tables (LECTURE/PRACTICE/LABORATORY HOURS 4/4/6) - 30 (2 Hours Lecture): Direct addressed hash tables - 31 (2 Hours Lecture): Indirect addressed hash tables - 32 (2 Hours Exercise): Constructions of hash tables - 33 (2 Hours Exercise): Use of hash tables - 34 (2 Hours Lab): Constructions of hash tables - 35 (2 Hours Lab): Use of hash tables - 36 (2 Hours Lab): Combining hash tables, trees, lists and dynamic arrays KNOWLEDGE AND UNDERSTANDING: the hash table data structure and the functions to handle it APPLYING KNOWLEDGE AND UNDERSTANDING: design and implement the functions, implemented both in their iterative or recursive version, to handle a hash table. Given a problem, choose the data structure that best fits that problem. TOTAL LECTURE/PRACTICE/LABORATORY HOURS 32/24/16 |
| Teaching Methods | |
|---|---|
| THE COURSE INCLUDES THEORY LESSONS, EXERCISES AND LABORATORY ACTIVITIES. IN THE EXERCISES, THE TEACHER WILL PROPOSE AND DESCRIBE ALGORITHMIC PROBLEMS AND THEIR SOLUTION USING THE C LANGUAGE. IN THE LABORATORY ACTIVITIES, THE STUDENTS WILL DEVELOP THE SOLUTION TO A PROBLEM SPECIFIED BY THE TEACHER. IN ORDER TO TAKE THE FINAL EXAM AND OBTAIN THE CREDITS RELATED TO THE EDUCATIONAL ACTIVITY, THE STUDENT MUST HAVE ATTENDED AT LEAST 70% OF THE ASSISTED TEACHING HOURS. |
| Verification of learning | |
|---|---|
| THE EXAM AIMS AT EVALUATING: THE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS PRESENTED IN THE COURSE; THE ABILITY TO APPLY THIS KNOWLEDGE FOR SOLVING PROBLEMS INVOLVING FUNDAMENTAL ALGORITHMS AND DATA STRUCTURES, EVALUATING THEIR EFFICIENCY; THE JUDGEMENT AUTONOMY; THE COMMUNICATION SKILLS; THE LEARNING ABILITY. THE EXAM CONSISTS OF A PRACTICAL TEST AND AN THEORETICAL TEST. THE PRACTICAL TEST IS MADE USING A COMPUTER. IN ORDER TO PASS THE TEST, THE STUDENT MUST SHOW THE ABILITY TO SOLVE AN ASSIGNED PROBLEM WITHOUT SIGNIFICANT ERRORS. ONLY STUDENTS PASSING THE PRACTICAL TEST ARE ADMITTED TO THE THEORETICAL TEST THAT WILL INVOLVE ALL THE ARGUMENTS PRESENTED IN THE COURSE, AND WILL EVALUATE THE KNOWLEDGE OF THE STUDENT AND THE COMMUNICATION SKILLS. THE FINAL SCORING WILL BE ASSIGNED BY WEIGHTING 60% THE PRACTICAL TEST AND 40% THE THEORETICAL TEST. THE "CUM LAUDE" SCORE CAN BE ASSIGNED TO STUDENTS THAT DEMONSTRATE AN EXCELLENT ABILITY TO ANALYZE AND DESIGN THE ALGORITHMS AND DATA STRUCTURES. |
| Texts | |
|---|---|
| P. FOGGIA, M. VENTO, “ALGORITMI E STRUTTURE DATI: ASTRAZIONE, PROGETTO E REALIZZAZIONE”, MCGRAW-HILL. SUPPLEMENTARY TEACHING MATERIAL WILL BE AVAILABLE ON THE UNIVERSITY E-LEARNING PLATFORM (HTTP://ELEARNING.UNISA.IT) ACCESSIBLE TO STUDENTS USING THEIR OWN UNIVERSITY CREDENTIALS. |
| More Information | |
|---|---|
| THE COURSE IS HELD IN ITALIAN |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2024-11-18]
