Data Structures and Algorithms of Physics of Data
A.Y. 2024/2025
Learning objectives
The course aims at introducing mathematical and programming basis and main tools and techniques for efficient algorithm design. Particular emphasis is taken, in the analysis of data structures which turn out to be fundamental in the construction of sophisticated algorithms applying in scientific realms. Mathematical tools are introduced, for performance and efficiency algorithm analysis. Main design techniques are introduced, illustrating the construction of some relevant and well-known algorithms. Finally, elements of parallel and distributed computing are proposed.
Expected learning outcomes
The student will be able to tackle typical problems related to data analysis, designing sophisticated efficient algorithms. To this aim, she/he will be able to apply the design techniques overviewed along the course, as well as properly use main data structures. Such skills will be possibly put in practice by developing C++ or Python software.
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
· Problems and algorithms
· Relevance of algorithms in the realm of Computer Science
· Algorithms from a technological viewpoint: hardware vs. software
· Design and analysis of algorithms, a case study: sorting
A simple algorithm: insertion sort, correctness and performance analysis
A more sophisticated algorithm: merge sort, correctness and performance analysis
Time complexity, worst/best/average case
· Tools for evaluating algorithm time complexity
Growth rate
Asymptotic time complexity
Landau's notation
Efficiency
· An algorithm design technique: divide et impera, recursion
Examples
Mathematical tools for analyzing recursive algorithms
Recurrence equations and their solution. Master Theorem
· Main data structures
Stack
Queue
List
Main functionalities and operations on data structures, possible implementation
· Hashing
Hash tables and functions
Open addressing
Perfect hashing
· Binary search trees
Definition
Insertion and deletion operations, balancing
Querying
Performance evaluation
· Advanced algorithm design techniques
Dynamic programming, examples
Greedy algorithms, examples, Matroids
· Main problems and algorithms on graphs
Basics on graph theory
Graph representations
Breadth-first and depth-first search
Minimum spanning trees, Kruskal and Prim's algorithms
Shortest paths, Bellman-Ford and Dijkstra's algorithms
All-pairs shortest paths, matrix and Floyd-Warshall's algorithms
· Applications of the theory of algorithms in the realm of Physics: some case studies
· Introduction to Tensor Networks
· Relevance of algorithms in the realm of Computer Science
· Algorithms from a technological viewpoint: hardware vs. software
· Design and analysis of algorithms, a case study: sorting
A simple algorithm: insertion sort, correctness and performance analysis
A more sophisticated algorithm: merge sort, correctness and performance analysis
Time complexity, worst/best/average case
· Tools for evaluating algorithm time complexity
Growth rate
Asymptotic time complexity
Landau's notation
Efficiency
· An algorithm design technique: divide et impera, recursion
Examples
Mathematical tools for analyzing recursive algorithms
Recurrence equations and their solution. Master Theorem
· Main data structures
Stack
Queue
List
Main functionalities and operations on data structures, possible implementation
· Hashing
Hash tables and functions
Open addressing
Perfect hashing
· Binary search trees
Definition
Insertion and deletion operations, balancing
Querying
Performance evaluation
· Advanced algorithm design techniques
Dynamic programming, examples
Greedy algorithms, examples, Matroids
· Main problems and algorithms on graphs
Basics on graph theory
Graph representations
Breadth-first and depth-first search
Minimum spanning trees, Kruskal and Prim's algorithms
Shortest paths, Bellman-Ford and Dijkstra's algorithms
All-pairs shortest paths, matrix and Floyd-Warshall's algorithms
· Applications of the theory of algorithms in the realm of Physics: some case studies
· Introduction to Tensor Networks
Prerequisites for admission
Undergraduate programming and mathematics.
Teaching methods
The course consists of traditional lectures in which, first of all, programming and mathematical basics are presented. Such basics turn out to be fundamental in designing sophisticated algorithms to be applied in several realms. Moreover, exercises, problems, and projects will be illustrated aiming at consolidating theory and stimulating the interest in more advanced topics which require and develop a certain maturity in computer science.
Teaching Resources
Textbooks:
Algorithms and Data Structures:
· T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. Fourth Edition, MIT Press, 2022.
· A.V. Aho, J.E. Hopcroft, J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Programming:
· P. Deitel, H. Deitel. Intro to Python. Pearson, 2020.
(Italian version: P. Deitel, H. Deitel. Introduzione a Python. Pearson, 2021.)
· D.S. Malik: Introduction to C++ Programming. Cengage South-Western, 2009
(Italian version available.)
Websites:
- ARIEL https://cmereghettisdafd.ariel.ctu.unimi.it/
Algorithms and Data Structures:
· T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. Fourth Edition, MIT Press, 2022.
· A.V. Aho, J.E. Hopcroft, J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Programming:
· P. Deitel, H. Deitel. Intro to Python. Pearson, 2020.
(Italian version: P. Deitel, H. Deitel. Introduzione a Python. Pearson, 2021.)
· D.S. Malik: Introduction to C++ Programming. Cengage South-Western, 2009
(Italian version available.)
Websites:
- ARIEL https://cmereghettisdafd.ariel.ctu.unimi.it/
Assessment methods and Criteria
The final examination consists in preparing an oral presentation on a topic related to the theory of algorithms. Such a topic, to be approved IN ADVANCE by course responsibles, might be a detailed expansion of a topic presented along the course or a discussion on applications and/or arguments not explicitly covered in the course but tightly related to algorithms and data structures.
Beside theoretical presentation, corresponding software implementation is requested: software development may be carried on with C++, Python, or another programming language.
Globally, the presentation plus software discussion should take about 30 minutes; further time should be considered for Q&A.
After presentation, an oral colloquium will take place on topics covered along the course, aiming to verify the knowledge of the general theory of algorithms and data structures.
The exam will be rated from 1 to 30.
Students not satisfied with the final evaluation assigned to their presentation + oral colloquium will be allowed to repeat the exam which will then be a classical oral colloquium on topics presented at the course.
Beside theoretical presentation, corresponding software implementation is requested: software development may be carried on with C++, Python, or another programming language.
Globally, the presentation plus software discussion should take about 30 minutes; further time should be considered for Q&A.
After presentation, an oral colloquium will take place on topics covered along the course, aiming to verify the knowledge of the general theory of algorithms and data structures.
The exam will be rated from 1 to 30.
Students not satisfied with the final evaluation assigned to their presentation + oral colloquium will be allowed to repeat the exam which will then be a classical oral colloquium on topics presented at the course.
FIS/01 - EXPERIMENTAL PHYSICS - University credits: 3
FIS/07 - APPLIED PHYSICS - University credits: 3
FIS/07 - APPLIED PHYSICS - University credits: 3
Lessons: 42 hours
Professor:
Tamascelli Dario
Professor(s)
Reception:
By appointment, send e-mail
Room C12, 5th floor LITA Building, Physics Department, via Celoria 16.