Algorithms and Data Structures
A.Y. 2023/2024
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.
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
First semester
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 GO programming language. In particular, the following topics will be covered:
- Sorting algorithms
- Lists, stacks and tails
- Client-interface-implementation paradigm for the creation of data structures
- Graphs
- Search and balanced trees
- Dynamic programming
- Heap and priority queues
- Greedy algorithms
A detailed list of topics presented in each lecture is published and updated on the course webpage.
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 GO programming language. In particular, the following topics will be covered:
- Sorting algorithms
- Lists, stacks and tails
- Client-interface-implementation paradigm for the creation of data structures
- Graphs
- Search and balanced trees
- Dynamic programming
- Heap and priority queues
- Greedy algorithms
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.
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. It is strongly recommended to attend all the lectures and all the laboratory activities.
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.
Further material, prepared by the teachers, is available on the course website.
Course website:
https://myariel.unimi.it/course/view.php?id=1221
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.
Further material, prepared by the teachers, is available on the course website.
Course website:
https://myariel.unimi.it/course/view.php?id=1221
Assessment methods and Criteria
The exam consists of 3 parts: written, project, 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.
The project aims to deepen the practical aspects of one or more topics covered in the course. It is required to design and implement a program, according to the assigned specifications, and to describe and justify the design choices, in a written report, that can be followed by an oral discussion, which will be mandatory when the report presents incomplete or unclear aspects. The specifications of the project, which must be carried out individually, are given at the end of the laboratory lessons. The project must be delivered within the dates that will be communicated through the course website and, at the latest, by September 15, 2024.
The exam ends with the oral part, which is accessed after passing the written and project parts, and which is focuses on the discussion of some topics covered in the course.
In evaluating each part of the exam, the following parameters will be taken into account: degree of knowledge of the topics, ability to apply the knowledge, critical reasoning ability, clarity of presentation and appropriate use of the language. In addition to the previous parameters, the evaluation of the project will also take into account the ability to apply knowledge to the resolution of concrete problems through the development of programs.
At the end of the oral part, the overall evaluation (expressed in thirtieths) is given by equally taking into account the evaluations of the three parts.
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.
The project aims to deepen the practical aspects of one or more topics covered in the course. It is required to design and implement a program, according to the assigned specifications, and to describe and justify the design choices, in a written report, that can be followed by an oral discussion, which will be mandatory when the report presents incomplete or unclear aspects. The specifications of the project, which must be carried out individually, are given at the end of the laboratory lessons. The project must be delivered within the dates that will be communicated through the course website and, at the latest, by September 15, 2024.
The exam ends with the oral part, which is accessed after passing the written and project parts, and which is focuses on the discussion of some topics covered in the course.
In evaluating each part of the exam, the following parameters will be taken into account: degree of knowledge of the topics, ability to apply the knowledge, critical reasoning ability, clarity of presentation and appropriate use of the language. In addition to the previous parameters, the evaluation of the project will also take into account the ability to apply knowledge to the resolution of concrete problems through the development of programs.
At the end of the oral part, the overall evaluation (expressed in thirtieths) is given by equally taking into account the evaluations of the three parts.
INF/01 - INFORMATICS - University credits: 12
Laboratories: 48 hours
Lessons: 72 hours
Lessons: 72 hours
Professors:
Lonati Violetta, Pighizzini Giovanni
Shifts:
Professors:
Lonati Violetta, Pighizzini Giovanni
Introduzione lab. - turno A
Professor:
Lonati ViolettaIntroduzione lab. - turno B
Professor:
Lonati ViolettaEducational website(s)
Professor(s)