Algorithms and Data Structures
A.Y. 2024/2025
Learning objectives
The present course is devoted to the study of algorithms and data structures. A general aim is the knowledge of the fundamental data structures and the main techniques used in the design and analysis of algorithms. A special attention is paid to computational complexity issues, i.e. the evaluation of computation time and memory space required by the procedures. A further goal is to achieve an activity of implementation of algorithms verifying their behavior over a computer machine, by means of programming languages and software tools that make clear and transparent to the user how the machine carries out the computations.
Expected learning outcomes
Students will learn to design and analyze algorithms for simple problems, choosing appropriate data structures and evaluating the computation time and the memory space required by the procedures. They will also learn to compare different algorithms for the solution of the same problem, also keeping into account the main aspects of the implementation and development of the procedures.
Lesson period: Second 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
Second semester
Course syllabus
The program is split in two parts: Theory and Laboratory
THEORY
1) Introduction.
Intuitive notion of problem and algorithm. Design and analysis of algorithms. Complexity of an algorithm, worst-case and average case analysis.
2) Computation model.
The RAM machine model. Syntax and semantics of RAM programs. Uniform and logarithmic cost criteria. Time and space complexity of RAM programs. Comparison between polynomial and exponential time complexities. High level (Algol-like) language.
3) Elementary data structures.
Arrays, lists, stacks, queues and corresponding implementation. Directed and undirected graphs, trees, plane trees, rooted trees and their memory representations.
4) Recursion.
Recursive procedures and algorithms. Translation of the recursive procedures into iterative algorithms by a means of a stack for procedure calls. Algorithms for visiting graphs and trees. Depth-first search and breadth-first search.
5) Sorting.
Classification of sorting algorithms. Evaluation of the minimum number of comparisons. Insertionsort, Heapsort, Quicksort.
6) Main data structures.
Abstract data structures and their implementation. Dictionaries. Hashing. Binary search trees. Balanced trees: 2-3 trees, B-trees.
Data structures for "Union-find" operations on partitions. Algorithms based on forests with balancing and compression.
7) General methods for algorithm design
Divide and Conquer algorithms. General paradigm. Analysis of time complexity of divide and conquer algorithms (Master theorem). Key examples: Mergesort, binary search, algorithm for product of integers.
Dynamic Programming: general properties, algorithms for transitive closure of graphs and for (all pair) shortest paths in weighted graphs, computing the longest common subsequence.
Greedy algorithms. Matroids and Rado Theorem. Kruskal and Prim algorithms for the minimum spanning trees. Dijkstra algorithm for the shortest paths from a source.
LABORATORY
1) Asymptotic worst-case complexity: properties of sequences and sums. Main recurrence equations.
2) Elements of C language: program structure, primitive data types, expressions, control flow, lexical analysis, basic data structures (arrays, matrices, strings, records), recursive procedures and functions, pointers dynamic memory allocation.
3) Sorting algorithms.
4) Lists, stacks and queues.
5) Graphs and trees, visit procedures, balanced search trees.
6) Examples of dynamic programming and greedy algorithms.
THEORY
1) Introduction.
Intuitive notion of problem and algorithm. Design and analysis of algorithms. Complexity of an algorithm, worst-case and average case analysis.
2) Computation model.
The RAM machine model. Syntax and semantics of RAM programs. Uniform and logarithmic cost criteria. Time and space complexity of RAM programs. Comparison between polynomial and exponential time complexities. High level (Algol-like) language.
3) Elementary data structures.
Arrays, lists, stacks, queues and corresponding implementation. Directed and undirected graphs, trees, plane trees, rooted trees and their memory representations.
4) Recursion.
Recursive procedures and algorithms. Translation of the recursive procedures into iterative algorithms by a means of a stack for procedure calls. Algorithms for visiting graphs and trees. Depth-first search and breadth-first search.
5) Sorting.
Classification of sorting algorithms. Evaluation of the minimum number of comparisons. Insertionsort, Heapsort, Quicksort.
6) Main data structures.
Abstract data structures and their implementation. Dictionaries. Hashing. Binary search trees. Balanced trees: 2-3 trees, B-trees.
Data structures for "Union-find" operations on partitions. Algorithms based on forests with balancing and compression.
7) General methods for algorithm design
Divide and Conquer algorithms. General paradigm. Analysis of time complexity of divide and conquer algorithms (Master theorem). Key examples: Mergesort, binary search, algorithm for product of integers.
Dynamic Programming: general properties, algorithms for transitive closure of graphs and for (all pair) shortest paths in weighted graphs, computing the longest common subsequence.
Greedy algorithms. Matroids and Rado Theorem. Kruskal and Prim algorithms for the minimum spanning trees. Dijkstra algorithm for the shortest paths from a source.
LABORATORY
1) Asymptotic worst-case complexity: properties of sequences and sums. Main recurrence equations.
2) Elements of C language: program structure, primitive data types, expressions, control flow, lexical analysis, basic data structures (arrays, matrices, strings, records), recursive procedures and functions, pointers dynamic memory allocation.
3) Sorting algorithms.
4) Lists, stacks and queues.
5) Graphs and trees, visit procedures, balanced search trees.
6) Examples of dynamic programming and greedy algorithms.
Prerequisites for admission
Fondamental notions and concepts of Programming. Basic mathematical notions. Main numerical sequences and series and their asymptotic properties.
We suggest to pass the examinations of at least one course of Programming and one of Mathematical Analysis, at an undergraduate level.
We suggest to pass the examinations of at least one course of Programming and one of Mathematical Analysis, at an undergraduate level.
Teaching methods
The course consists of two parts: theory and laboratory.
The theory part is based on traditional lectures, some of which devoted to the solutions of simple exercises.
The laboratory part includes both traditional lectures and computer programming activities carried out in equipped classroom.
The theory part is based on traditional lectures, some of which devoted to the solutions of simple exercises.
The laboratory part includes both traditional lectures and computer programming activities carried out in equipped classroom.
Teaching Resources
THEORY
- Web site: http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)
which will also include a link to the web site MyAriel of the present course for the new academic year.
- Class notes:
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, Dispense del corso di Algoritmi,
Corso di Laurea Triennale in Matematica, a.a. 2018/19, Università degli Studi di Milano, Marzo 2019.
Available at the previous web site.
- References :
1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati,
3/ed, McGraw-Hill Italia, 2010 (oppure edizione in inglese, 2009).
2) A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms,
Addison-Wesley Publishing Company, 1974.
LABORATORY
- Web site (to be opened):
https://homes.di.unimi.it/cordone/courses/2024-algo/2024-algo.html
- References:
1) K. N. King: Programmazione in C (C Programming: A Modern Approach (second edition)),
W. W. Norton & Company, 2008.
2) Al Kelley, Ira Pohl : C, Didattica e Programmazione (A book on C, 4th edition). Pearson, Italia, 2004.
- Web site: http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)
which will also include a link to the web site MyAriel of the present course for the new academic year.
- Class notes:
A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, Dispense del corso di Algoritmi,
Corso di Laurea Triennale in Matematica, a.a. 2018/19, Università degli Studi di Milano, Marzo 2019.
Available at the previous web site.
- References :
1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati,
3/ed, McGraw-Hill Italia, 2010 (oppure edizione in inglese, 2009).
2) A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms,
Addison-Wesley Publishing Company, 1974.
LABORATORY
- Web site (to be opened):
https://homes.di.unimi.it/cordone/courses/2024-algo/2024-algo.html
- References:
1) K. N. King: Programmazione in C (C Programming: A Modern Approach (second edition)),
W. W. Norton & Company, 2008.
2) Al Kelley, Ira Pohl : C, Didattica e Programmazione (A book on C, 4th edition). Pearson, Italia, 2004.
Assessment methods and Criteria
The examination consists of two parts: a lab exam and an oral exam.
- The lab exam consists of an individual project, to be realized as home work, including a program in language C solving a problem assigned by teachers and a written report that describes algorithms and data structures used in the program and evaluates their time and space complexity. A definition of the assigned problem, time and ways of presentation of the projects are published on the web site of Laboratory of the present course two weeks before the deadline for the same presentation; such a deadline usually occurs one week before the oral exam. The lab exam aims to evaluate the ability to implement and develop the algorithms and data structures presented in the course. In order to pass this lab exam the program must be correct and the report must properly describe the main features of the implementation. The evaluation takes into account the efficiency of the procedures and the implementation choices.
- The oral exam can be taken only if the lab exam has been succesfully passed in the same session or in a previous session during the last six months. In the oral exam candidates discuss their project and the main topics of the program of theory. The evaluation is based on the ability to describe at high level the algorithms and data structures included in the program, the knowledge of methods for the design and analysis of the procedures described in the course and of the techniques for evaluating the corresponding time and space complexity.
Cadidates are required to pass succesfully both (lab and oral) exams. The final mark, an integer in the range 0-30, will be the average value of the evaluations received in the two exams and will be communicated just after the oral exam.
- The lab exam consists of an individual project, to be realized as home work, including a program in language C solving a problem assigned by teachers and a written report that describes algorithms and data structures used in the program and evaluates their time and space complexity. A definition of the assigned problem, time and ways of presentation of the projects are published on the web site of Laboratory of the present course two weeks before the deadline for the same presentation; such a deadline usually occurs one week before the oral exam. The lab exam aims to evaluate the ability to implement and develop the algorithms and data structures presented in the course. In order to pass this lab exam the program must be correct and the report must properly describe the main features of the implementation. The evaluation takes into account the efficiency of the procedures and the implementation choices.
- The oral exam can be taken only if the lab exam has been succesfully passed in the same session or in a previous session during the last six months. In the oral exam candidates discuss their project and the main topics of the program of theory. The evaluation is based on the ability to describe at high level the algorithms and data structures included in the program, the knowledge of methods for the design and analysis of the procedures described in the course and of the techniques for evaluating the corresponding time and space complexity.
Cadidates are required to pass succesfully both (lab and oral) exams. The final mark, an integer in the range 0-30, will be the average value of the evaluations received in the two exams and will be communicated just after the oral exam.
INF/01 - INFORMATICS - University credits: 9
Practicals: 48 hours
Lessons: 45 hours
Lessons: 45 hours
Professors:
Cordone Roberto, Goldwurm Massimiliano
Shifts:
Educational website(s)
Professor(s)