Algorithms and Data Structures
A.Y. 2020/2021
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 cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
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.
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.
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.
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.
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.
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: 48 hours
Lessons: 72 hours
Lessons: 72 hours
Professors:
Lonati Violetta, Pighizzini Giovanni
Shifts:
Professor:
Pighizzini Giovanni
Introduzione - Lab. Turno A
Professor:
Lonati ViolettaIntroduzione - Lab. Turno B
Professor:
Lonati ViolettaLab. parte 2 turno unico
Professor:
Lonati ViolettaProfessor(s)