Data Structures and Algorithms of Physics of Data
A.Y. 2020/2021
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
Instructions for lecturing amid pandemics will be immediately posted on the websites dedicated to the course (see url's below).
in case of online lecturing, lectures will be provided via Zoom either syncronously and recorded for an asyncronous attendance. The contents of the course as well as the resources for preparing the final exam will not modify. The final exam will take place via Zoom according to modality and criterions adopted for the traditional exam, described below.
in case of online lecturing, lectures will be provided via Zoom either syncronously and recorded for an asyncronous attendance. The contents of the course as well as the resources for preparing the final exam will not modify. The final exam will take place via Zoom according to modality and criterions adopted for the traditional exam, described below.
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
· Some aspects on algorithm design and analysis for non-Von Neumann systems
Parallel and distributed 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
· Some aspects on algorithm design and analysis for non-Von Neumann systems
Parallel and distributed algorithms
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. Third Edition, MIT Press, 2009. (Italian version available.)
· 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 in preparation.)
· 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. Third Edition, MIT Press, 2009. (Italian version available.)
· 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 in preparation.)
· 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 an oral colloquium which covers the whole span of topics proposed during the course. Questions will be proposed, aiming to check students' knowledge of basic concepts as well as the ability of applying main algorithm design techniques in the solution of typical scientific problems. In addition, some problems will be issued requiring "original" ideas from the students, in order to appreciate a certain level of algorithmic maturity. About forty minutes are devoted to the oral exam. The possibility will be evaluated, of complementing the oral examination with some software developments in C++ or Python. The exam will be rated from 1 to 30.
FIS/01 - EXPERIMENTAL PHYSICS
FIS/07 - APPLIED PHYSICS
FIS/07 - APPLIED PHYSICS
Lessons: 42 hours
Professors:
Mereghetti Carlo, Tamascelli Dario
Professor(s)
Reception:
On appointment, via email
Uff. S 6008, VI floor, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy
Reception:
Tuesday, 9am-10am or by appointment (ask via e-mail)
Room C12, 5th floor LITA Building, Physics Department, via Celoria 16.