Algorithms and LAB A - LModule LAB
Academic Year 2024/2025 - Teacher: SIMONE FAROExpected Learning Outcomes
Knowledge and understanding: Students will acquire knowledge of the fundamental principles of algorithm performance analysis and key concepts related to computational complexity and algorithmic correctness.
Applying knowledge and understanding: Students will be able to apply analysis techniques to existing algorithms and learn to design algorithmic solutions to elementary problems that adhere to rigorous correctness standards.
Autonomy of judgment: Students will be able to identify situations where one algorithm is preferable to another and evaluate the computational complexity and the correctness of algorithms through formal proofs.
Communication skills: Students will learn to communicate the results of complexity analysis and correctness proofs clearly and effectively through written reports, informal presentations, and technical discussions, employing appropriate terminology adaptable to audiences of varying expertise.
Learning Skills: Students will master the algorithmic thinking acquired in the course and adapt it to new algorithms and computational problems they encounter. They will be capable of independent learning and acquiring new skills in areas such as computational complexity and algorithmic correctness.
Course Structure
Required Prerequisites
Additionally, enrollment in the Algorithms course is mandatory.
Attendance of Lessons
Detailed Course Content
COURSE OVERVIEW
The course provides a thorough understanding of fundamental techniques for the analysis of computational complexity and methodologies for proving the correctness of computer algorithms.
COURSE TOPICS
Introduction
Tools for algorithm analysis. Analysis of elementary algorithms. Introduction to asymptotic notations.
Recursive Algorithms
Analysis of algorithms using the substitution method and the recursion-tree method. Heapify and Mergesort. Using the master method to solve recurrence equations.
Hashing
Analysis of hash tables: successful and unsuccessful search.
Red-Black Trees
Analysis of the height of a red-black tree. Insertion and deletion operations.
Dynamic Programming
Analysis of dynamic programming. Proof of the optimal substructure property. Example: Longest Common Subsequence.
Basics of Greedy Strategy
Selection of the optimal solution. Proof of the greedy choice for the activity selection problem and the Huffman algorithm case. Proof of the optimal substructure and greedy choice in knapsack and change-making problems.
Elementary Graph Algorithms
Correctness of the Bellman-Ford and Topological Sort algorithms with execution examples. Correctness of the Dijkstra's algorithm with execution examples.
Textbook Information
(*) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Fourth Edition), The MIT Press, Cambridge - Massachusetts, 2022
disponibile anche nella traduzione italiana
(1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.
Course Planning
| Subjects | Text References | |
|---|---|---|
| 1 | Tools for algorithms analysis. The asymptotic notation. | chap. 2.2 and 3 of (*) |
| 2 | Recursive algorithms analysis. | chap. 2.3, intro to chap. 4, 4.3, and 4.4 of (*) |
| 3 | The master method for solving recurrences. Example: Heapify. Analisys of Build-a-Heap. | chap. 4.5, 6.2, and 6.3 of (*) |
| 4 | Hash tables. | chap. 11.2 and 11.4 of (*) |
| 5 | Height of red-black trees. Insertion and deletion. | chap. 13.1 of (*) |
| 6 | Dynamic programming analysis. | chap. 14.3-14.3, and 14.5 of (*) |
| 7 | Elements of Greedy strategy. | chap. 15.1 - 15.3 of (*) |
| 8 | Greedy versus dynamic programming: Knapsack and fractional knapsack. PRoperties of Depth-First Search | chap. 15.2 and 20.3 of (*) |
| 9 | Bellman-Ford algorithm and Topological Sort | chap. 20.4 and 22.1 of (*) |
| 10 | Dijkstra's Algorithm. | chap. 22.3 of (*) |
| 11 | Exercise classes. |