60/9 - ALGORITHMS AND DATA STRUCTURES
Academic Year 2019/2020
Free text for the University
CECILIA DI RUBERTO (Tit.)
- Teaching style
- Lingua Insegnamento
|[60/65] MATHEMATICS||[65/20 - Ord. 2012] Applicativo||6||48|
The course allows you to acquire adequate knowledge of algorithms, data structures and their implementation in C for the solution of complex problems. In particular, it highlights the following aspects:
- Formally define the notion of algorithm.
- Organize information in data structures.
- Characterize the data to be processed by organizing and structuring them in appropriate ways in order to facilitate their use by the algorithms.
- Designing correct and efficient algorithms, through the examination of different paradigms and solving the problem as quickly as possible and using as little memory as possible.
- Study limitations inherent problems to be solved.
Expected learning outcomes
Knowledge and understanding
The student will acquire the fundamental knowledge related to:
- Knowledge of the mechanisms of memory allocation and use of pointers
- Programming skills in C, using pointers and dynamic data structures
- Skill in recursive programming techniques
- Knowledge of the basic notions of complexity analysis
- Ability to assess the complexity of algorithms and to improve their efficiency in terms of execution time and/or memory usage
- Problem solving skills by design data structures and algorithms
- Knowledge of complex data structures (lists, queues, stacks, heaps, trees, hash tables and graphs) and related algorithms
- Knowledge of sorting algorithms
Applying knowledge and understanding
The student will be able to apply the knowledge gained to achieve the following objectives:
- Know how to organize the information into appropriate data structures
- Characterize the data to be processed by organizing and structuring them in appropriate ways in order to facilitate their use by the algorithms
- Design correct algorithms and efficient, through the examination of different paradigms and solving the problem as quickly as possible and using as little memory as possible.
The student will be able to apply the typical methods of algorithmics for the understanding and resolution of new computational problems. Criticism classroom discussions and laboratory exercises will serve to stimulate and develop making judgements.
The student will acquire the ability to express the fundamental concepts of algorithms and data structures with appropriate and rigorous terminology. He will learn to describe problems concerning the analysis and design of correct and efficient algorithms and the methods adopted for their solution.
The student will acquire the ability to study and learn the fundamental data structures and algorithmic techniques. He will learn to recognize the importance of computational resources (in particular space and time) in order to independently develop solutions to new problems concerning the correct and efficient algorithm design.
Elements of Mathematical Analysis
Linear algebra (vector and matrix)
Elementary knowledge of architecture of computer systems
Ayntax knowledge, data types and basic language constructs in C
Ability to develop simple programs in C.
Analysis of algorithms: complexity in time and space, asymptotic complexity, notation · O, Omega, Teta; recursive algorithms and recurrence relations, the worst case, best and average (8 h)
Basic data structures: arrays, matrix, string, queue, stack. The pattern matching problem (6 h).
Dynamic data structures: linked lists, queue and stack dynamically linked. Doubly linked lists (2 h)
Tree structures: binary trees, properties, representations and operations (5 h)
Heaps and priority queues (3 h).
Binary search trees, AVL (6 h).
Hash tables (2 h)
Graphs: properties, representations, operations, the shortest path problem (7 h)
Sorting algorithms: insertion sort and selection sort, quick sort, merge sort, heap sort and radix sort (9 h)
In addition to theoretical lectures and guided exercises (48 h), practical exercises will be conducted in the laboratory and supported by the teacher and/or tutors where the described algorithms will be implemented in C and used to solve some practical problems (36 h).
Verification of learning
The exam consists of a written test with exercises/questions on theoretical arguments and algorithms described in class and an oral examination. The written exam lasts approximately about 1h30. It is evaluated in thirtieth and is deemed sufficient if its rating, which normally remains valid only for the session in which the test is supported, is at least 18/30. The written exam, if passed, is followed by an oral, aimed at verifying and discussing the solutions to the problems proposed during laboratory exercises and consists of further questions on the course program. The oral test is aimed to ensure: the level of knowledge of the theoretical course content (Dublin descriptor 1), the level of expertise in exposing their argumentation skills (Dublin descriptor 2), their independent judgment (Dublin descriptor 3) to propose the most appropriate approach to argue what is required. The oral examination also aims to verify the student's ability to respond to the proposed questions with properties of language, to support a dialectical relationship during the debate and to show logical-deductive ability and summary exposition (Dublin descriptor 4). If passed, it entails an adjustment for excess or defect of at most 5/30 of the written test, thereby determining the final grade.
C. Demetrescu, I. Finocchi, G. Italiano, Algoritmi e Strutture Dati, McGraw-Hill, 2004.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli algoritmi e Strutture Dati, McGraw-Hill, 2005.
Slides of the lectures and other materials are available on the Moodle elearning platform.