Algorithms and data structures

A.Y. 2020/2021
12
Max ECTS
120
Overall hours
SSD
INF/01
Language
Italian
Learning objectives
The aim of the course is to introduce the fundamental concepts concerning the project and analysis of algorithms and data structures used by them, by illustrating the main project techniques and some fundamental data structures, together with computational complexity analysis.
Expected learning outcomes
The student should be able to apply the concepts and techniques illustrated in the course to the project of algorithms for the solution of simple problems, to the choice of suitable data structures, to the estimation of the computational complexity. Furthermore, the student should be able to present problems and corresponding solving algorithms in an appropriate way, critically comparing different algorithmical solutions of a same problem.
Course syllabus and organization

Single session

Responsible
Lesson period
First semester
Teaching methods.
Lecture will be given online, using the platform Zoom, according to timetable. Students are recommended to follow online lectures. Anyway, the lecture will be also recorded and will be available to students on the course website.

Course syllabus and Teaching Resources.
No changes.

Assessment methods and Criteria.
Assessments methods and criteria are unchanged: exams will be either in class or online, depending on the rules in force at that time.
Course syllabus
The course is divided into a part of theory and a part of laboratory.

The theory part is focused on the following topics:
- The concept of algorithm. Algorithms and programs. Asymptotic notations. Algorithm complexity.
- The RAM Machine.
- Fundamental data structures: array, list, stack, queue, tree.
- Search: sequential and binary search. Tree structures for search.
- Hashing.
- Elementary sorting techniques.
- Advanced sorting techniques (mergesort, heapsort, quicksort).
- Sorting techniques not using comparisons.
- Fundamental algorithmic techniques: divide-and-conquere, dynamic programming, greedy.
- Graphs.
- Fundamental problems and algorithms on graphs: minimum spanning tree, shortest paths in graphs.
- Hard problems: nondeterministic algorithms and NP-completeness (an introduction).


In the laboratory part the student will have to familiarize with algorithmic techniques through the concrete implementation of algorithms in a real programming language, the C language. In particular, the following topics will be covered:
Fundamentals of C:
- gcc compilers
- Types, operators, selection and iteration
- Input / output
- Aggregated data: arrays, matrices, strings and structures
- Functions and recursion

Advanced elements of C:
- Pointers
- Dynamic memoery allocoation
- Program structure, division and management of multiple files, preprocessor

Implementation of data structures and algorithms
- Sorting algorithms
- Lists, stacks and tails
- Graphs: breadth and depth first visits, connected components
- Search and balanced trees
- Dynamic programming
- Heap and priority queues
- Greedy algorithms
- Client-interface-implementation paradigm for the creation of data structures

A detailed list of topics presented in each lecture is published and updated on the course webpage.
Prerequisites for admission
To be able to write and develop programs that use fundamental structures of imperative programming; to know at least one imperative programming language, and how to use it in a profitable way.
Relevant mathematical functions as polynomials, logarithms and exponentials; fundamental asymptotic notations and their properties.
It is mandatory to have passed the exam of Computer Programming. Furthermore, it is strongly recommended to have passed the exams of Continuum Mathematics and Discrete Mathematics.
Teaching methods
The theory part is carried out through frontal lectures. The laboratory part alternates lectures with exercises and practical activities carried out individually or in small groups.
Teaching Resources
The main reference is the following:
C. Demetrescu, I. Finocchi, G. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2008.

For some topics we use:
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, Rapporto interno n. 230-98, Dip. Scienze dell'Informazione, Università degli Studi di Milano, Ottobre 2011.

For the part on C language the main reference is:
B. Kernighan, D. M. Ritchie, Il linguaggio C, Pearson Education Italia, 2019

Another recommended text is:
R. Sedgewick, Algoritmi in C, Pearson Education Italia, 2002

Further material, prepared by the teachers, is available on the course website.
Assessment methods and Criteria
The exam consists of 3 parts: written, laboratory and oral.
In the written part (2 hours), the students must solve some exercises, with open-ended questions, and a problem, where it is required to apply one of the algorithmic techniques presented in the course.
In the laboratory part (2 hours and half), the students have to solve exercises that require 1) to realize (or understand and modify) C programs that process and use data structures and 2) to design and implement algorithmic solutions for specified problems.
The exam ends with the oral part, which is accessed after passing the written and laboratory parts, and which is focuses on the discussion of some topics covered in the course. At the end of the oral part, the overall evaluation (expressed in thirtieths) is given by taking into account the following parameters: degree of knowledge of the topics, ability to apply the course contents to the solution of concrete problems, ability of critical reasoning, clarity of presentation and appropriate use of the language.
INF/01 - INFORMATICS - University credits: 12
Laboratories: 16032 hours
Lessons: 72 hours
Shifts:
Introduzione - Lab. Turno A
Professor: Lonati Violetta
Introduzione - Lab. Turno B
Professor: Lonati Violetta
Lab. parte 2 turno unico
Professor: Lonati Violetta