Algorithms and Data Structures
A.Y. 2024/2025
Learning objectives
The objective of the course is the introduction of the basic concepts for the design and analysis of algorithms and data structures. The course will illustrate the main data structures and will focus on some specific algorithms, also analyzing their computational complexity.
Expected learning outcomes
The student will know and will be able to use the main data structures and algorithms studied during the course. The student will also be able to propose adequate algorithmic solutions to simple problems, using the most appropriate data structures, and will be able to estimate the computational complexity of the proposed solution.
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
1- Basic concepts
Problem and algorithm; computational complexity of algorithms, asymptotic notations; recurrence equations
2- Elementary data structures
Stack, queue, list: definitions and operations, implementation using arrays and pointers; dictionaries and hash tables
3- Trees
Definition of tree, main operations over trees, implementation of trees; binary search trees: definition, representation, operations; balanced trees: AVL trees, B-trees
4- Graphs
Definition of graph, representation of graph; breadth first search and depth first search, concept of connected component; minimum cost spanning tree; the shortest path problem
5- Sort algorithms
The sorting problem; sort algorithms: bubble sort, insertion sort, selection sort, merge sort, heap sort, quick sort (and its analysis); sorting in linear time
6- Algorithm design techniques [hints]
Problem and algorithm; computational complexity of algorithms, asymptotic notations; recurrence equations
2- Elementary data structures
Stack, queue, list: definitions and operations, implementation using arrays and pointers; dictionaries and hash tables
3- Trees
Definition of tree, main operations over trees, implementation of trees; binary search trees: definition, representation, operations; balanced trees: AVL trees, B-trees
4- Graphs
Definition of graph, representation of graph; breadth first search and depth first search, concept of connected component; minimum cost spanning tree; the shortest path problem
5- Sort algorithms
The sorting problem; sort algorithms: bubble sort, insertion sort, selection sort, merge sort, heap sort, quick sort (and its analysis); sorting in linear time
6- Algorithm design techniques [hints]
Prerequisites for admission
Knowledge of the basic concepts and constructs of imperative programming.
Knowledge of the main mathematical functions and of the main asymptotic notations.
Passing the exam of Computer programming course is compulsory for Algorithms and data structure course. It is advised to pass the exam of Calculus course.
Knowledge of the main mathematical functions and of the main asymptotic notations.
Passing the exam of Computer programming course is compulsory for Algorithms and data structure course. It is advised to pass the exam of Calculus course.
Teaching methods
Frontal lessons
Teaching Resources
Web site:
https://myariel.unimi.it/course/view.php?id=826
where students will find lecture notes
Reference book:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduction to Algorithms", 4/ed, 2022
The MIT Press
[ISBN: 9780262033848]
Suggested readings:
V. Aho, J.E. Hopcroft, J.D. Ullman, "Data Structures and Algorithms," Addison-Wesley, Reading, MA, 1983.
https://myariel.unimi.it/course/view.php?id=826
where students will find lecture notes
Reference book:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,
"Introduction to Algorithms", 4/ed, 2022
The MIT Press
[ISBN: 9780262033848]
Suggested readings:
V. Aho, J.E. Hopcroft, J.D. Ullman, "Data Structures and Algorithms," Addison-Wesley, Reading, MA, 1983.
Assessment methods and Criteria
The exam is a written test of nearly 2.30 hours, including open questions and exercises.
The exam aims at evaluating the comprehension of the studied algorithms and data structures. The exam also aims at evaluating the ability of using the studied data structures and algorithms for solving simple problems.
The exam is closed book.
The evaluation is expressed on a 1-30 scale.
The results of the exams are available on the Ariel web page of the course.
The exam aims at evaluating the comprehension of the studied algorithms and data structures. The exam also aims at evaluating the ability of using the studied data structures and algorithms for solving simple problems.
The exam is closed book.
The evaluation is expressed on a 1-30 scale.
The results of the exams are available on the Ariel web page of the course.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Foresti Sara
Shifts:
Turno
Professor:
Foresti SaraEducational website(s)
Professor(s)