Algorithms
A.Y. 2020/2021
Learning objectives
The present course is devoted to the study of algorithms and their data structures. A general aim is the knowledge of the fundamental data structures and of the main techniques used for the design and analysis of algorithms, with a special attention to their computational complexity, i.e. the evaluation of the amount of resources required by the computation. 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 time complexity 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 carrying out of the procedures.
Lesson period: Second semester (In case of multiple editions, please check the period, as it may vary)
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
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) Models of computation.
The RAM machine model. Syntax and semantics of RAM programs. Uniform and logarithmic cost criteria. Time and space complexity of RAM programs. Polynomial and exponential time complexities. High level (Algol-like) language.
3) Elementary data structures.
Arrays, lists, stacks, queues and corresponding implementation. Oriented and non-oriented graphs, trees, plane trees, binary trees and their representations. Recursive procedures and corresponding iterative translation by a stack. Algorithms for visiting graphs and trees; depth-first search and breadth-first search.
4) Sorting algorithms.
Classification of sorting algorithms. Evaluation of the minimum number of comparisons.
Insertionsort. Heap and heapsort. Quicksort.
5) Data structures and algorithms for sets.
Abstract data structures and their implementation. Hash. Binary search trees. Balanced trees: 2-3 trees, B-trees. "Union-find" operations on partitions: algorithms based on forests with balancing and compression.
6) Design mehods.
Divide and Conquer algorithms. Analysis of their time complexity (Master theorem). Mergesort, binary search, algorithm for product of integers.
Dynamic Programming algorithms: transitive closure of graphs and (all pair) shortest paths.
Greedy algorithms. Kruskal algorithm for minimum spanning tree. Independent systems, matroids, Rado's Theorem. Prim algorithm. Dijkstra algorithm.
LABORATORY
Asymptotic properties of sequences and sums. Main recurrence equations.
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.
Implementation of data structures and algorithms: sorting algorithms, lists, stacks and queues, graphs and trees, procedures for visiting graphs, balanced search trees, 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) Models of computation.
The RAM machine model. Syntax and semantics of RAM programs. Uniform and logarithmic cost criteria. Time and space complexity of RAM programs. Polynomial and exponential time complexities. High level (Algol-like) language.
3) Elementary data structures.
Arrays, lists, stacks, queues and corresponding implementation. Oriented and non-oriented graphs, trees, plane trees, binary trees and their representations. Recursive procedures and corresponding iterative translation by a stack. Algorithms for visiting graphs and trees; depth-first search and breadth-first search.
4) Sorting algorithms.
Classification of sorting algorithms. Evaluation of the minimum number of comparisons.
Insertionsort. Heap and heapsort. Quicksort.
5) Data structures and algorithms for sets.
Abstract data structures and their implementation. Hash. Binary search trees. Balanced trees: 2-3 trees, B-trees. "Union-find" operations on partitions: algorithms based on forests with balancing and compression.
6) Design mehods.
Divide and Conquer algorithms. Analysis of their time complexity (Master theorem). Mergesort, binary search, algorithm for product of integers.
Dynamic Programming algorithms: transitive closure of graphs and (all pair) shortest paths.
Greedy algorithms. Kruskal algorithm for minimum spanning tree. Independent systems, matroids, Rado's Theorem. Prim algorithm. Dijkstra algorithm.
LABORATORY
Asymptotic properties of sequences and sums. Main recurrence equations.
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.
Implementation of data structures and algorithms: sorting algorithms, lists, stacks and queues, graphs and trees, procedures for visiting graphs, balanced search trees, 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.
It is strongly suggested to pass the examinations of at least one course of Programming and one of Mathematical Analysis, at an undergraduate level.
It is strongly suggested 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 experimental activities carried out in classroom equipped with computers.
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 experimental activities carried out in classroom equipped with computers.
Teaching Resources
THEORY
- Web page : http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)
- 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 http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)/dispense…
- 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 page : https://homes.di.unimi.it/cordone/courses/2018-algo/2018-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.
An Ariel site for both parts (Theory and Laboratory) is available at:
https://mgoldwurma.ariel.ctu.unimi.it/v5/Home/
- Web page : http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)
- 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 http://users.mat.unimi.it/users/goldwurm/Algoritmi(Matematica)/dispense…
- 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 page : https://homes.di.unimi.it/cordone/courses/2018-algo/2018-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.
An Ariel site for both parts (Theory and Laboratory) is available at:
https://mgoldwurma.ariel.ctu.unimi.it/v5/Home/
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, describing the algorithms and data structures used in the program, which also evaluates time and space complexity of the procedures. A definition of the assigned problem, time and ways of presentation of the projects are published on the web site of Laboratory of Algorithms 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.
In order to pass the examination cadidates have to pass succesfully both (lab and oral) parts. The final mark is an integer in the range 0-30, is the average value of the evaluations received in the two (lab and oral) parts and is communicated 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, describing the algorithms and data structures used in the program, which also evaluates time and space complexity of the procedures. A definition of the assigned problem, time and ways of presentation of the projects are published on the web site of Laboratory of Algorithms 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.
In order to pass the examination cadidates have to pass succesfully both (lab and oral) parts. The final mark is an integer in the range 0-30, is the average value of the evaluations received in the two (lab and oral) parts and is communicated after the oral exam.
INF/01 - INFORMATICS - University credits: 9
Practicals: 48 hours
Lessons: 45 hours
Lessons: 45 hours
Professor:
Goldwurm Massimiliano
Professor(s)