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 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
Course syllabus
1. Introduction
Basic concepts. Analysis of algorithms, space and time complexity of recursive and non-recursive algorithms. Asymptotic notations.
2. Abstract data types
Lists, Stack, Code: definition and operations. Implementation (arrays, pointers) and advantages / disadvantages.
3. Sorting
Problem. Insertion sort, heapsort, quicksort, mergesort: description and analysis of complexity.
4. Hashing
Direct hashing. Hash functions. Collisions.
5. Trees
Basic concepts and definitions. Visiting techniques (inorder, preorder, postorder). Search, insert, and delete operations. Implementation techniques. Binary search trees: definition, representation, operations. Red-black binary trees: definition, representation, operations.
6. Management of data on external memory
Problems. B-trees: definition, properties and advantages. Execution of search, insertion and deletion operations. Merge and split operations.
7. Graphs.
Oriented and non-oriented graphs: definitions and basic concepts. Implementation techniques. Minimum path in weighted graphs: problem and solutions. Visiting algorithms (BFS and DFS). Examples of DFS and BFS applications. Graph matching.
8. Recursion
Definition of direct and indirect recursion. Tail recursion technique.
9. Advanced design techniques.
Dynamic programming. Greedy algorithms.
Basic concepts. Analysis of algorithms, space and time complexity of recursive and non-recursive algorithms. Asymptotic notations.
2. Abstract data types
Lists, Stack, Code: definition and operations. Implementation (arrays, pointers) and advantages / disadvantages.
3. Sorting
Problem. Insertion sort, heapsort, quicksort, mergesort: description and analysis of complexity.
4. Hashing
Direct hashing. Hash functions. Collisions.
5. Trees
Basic concepts and definitions. Visiting techniques (inorder, preorder, postorder). Search, insert, and delete operations. Implementation techniques. Binary search trees: definition, representation, operations. Red-black binary trees: definition, representation, operations.
6. Management of data on external memory
Problems. B-trees: definition, properties and advantages. Execution of search, insertion and deletion operations. Merge and split operations.
7. Graphs.
Oriented and non-oriented graphs: definitions and basic concepts. Implementation techniques. Minimum path in weighted graphs: problem and solutions. Visiting algorithms (BFS and DFS). Examples of DFS and BFS applications. Graph matching.
8. Recursion
Definition of direct and indirect recursion. Tail recursion technique.
9. Advanced design techniques.
Dynamic programming. Greedy algorithms.
Prerequisites for admission
It is compulsory to pass the exam of Computer Programming and it is recommended pass the exam of Continuum mathematics and Discrete mathematics.
Teaching methods
Lectures and laboratory.
Teaching Resources
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, "Introduzione agli Algoritmi e Strutture Dati," McGraw-Hill, 2a edizione (2005).
Slides available on the Ariel web site of the course: http://sdecapitaniasd.ariel.ctu.unimi.it/
Slides available on the Ariel web site of the course: http://sdecapitaniasd.ariel.ctu.unimi.it/
Assessment methods and Criteria
The exam consists of a written test that includes both theoretical questions and exercises. The written test, lasting two and a half hours, aims to verify the preparation and understanding of the subject. The evaluation, expressed in thirtieths, will take into account the correctness, completeness and clarity of the answers to the theoretical questions and the ability to reason and use the knowledge acquired for solving the exercises. The exam is closed book. The results of the written tests will be communicated through the publication of a pdf file on the Ariel website of the course.
INF/01 - INFORMATICS - University credits: 12
Laboratories: 48 hours
Lessons: 72 hours
Lessons: 72 hours
Professors:
De Capitani Di Vimercati Sabrina, Frasca Marco
Shifts:
Professor(s)