Algorithms and LAB M - ZModule Algorithms
Academic Year 2023/2024 - Teacher: SIMONE FAROExpected Learning Outcomes
Knowledge and understanding: students will acquire knowldege relative to the main methodologies for the design of efficient algorithms (incremental, recursion, dynamic programming, greedy algorithms), as well as the techniques for their computational analysis, both in the worst and in the average cases.
Applying knowledge and understanding: students will acquire the ability to solve problems of low difficulty, requiring the design and analysis of elementary algorithmic solutions.
Making judgements: students will be able to evaluate the quality of an algorithmic solution in terms of efficiency and reuse.
Communication skills: students will acquire the necessary communication skills and expressive ability in communicate problems regarding the algorithmic studies, also to non-expert interlocutors.
Learning skills: students will have the ability to adapt the knowledge acquired also in new contexts and to advance his/her knowledge through the consultation of specialist sources in the algorithmic field.
Course Structure
Classroom-taught lessons.
Should teaching be offered in mixed mode or remotely, it may be necessary to introduce changes with respect to previous statements, in line with the programme planned and outlined in the syllabus.
Required Prerequisites
The student should be familiar with the main elementary data structures and the procedures for manipulating them. Specifically, good knowledge of list, queue, stack and binary search tree data structures is required. Good knowledge of the graph data structure and the elementary algorithms for its visit, i.e., DFS visit and BFS visit, is required. Good knowledge of the algorithm for computing connected components of a graph and the algorithm for computing a topological ordering of a graph is also required.
A good knowledge of the elements of discrete mathematics and mathematical analysis and the concepts presented in the Programming I and II courses is also required.
Attendance of Lessons
Detailed Course Content
GENARAL DESCRIPTION
The course presents the main algorithm design methodologies (incremental, recursive, dynamic programming, greedy algorithms) as well as offering some specific implementation techniques of the algorithms and data structures covered through the use of the C++ language. Tools useful in analyzing the computational problem in order to identify the correct problem-solving strategy will also be provided.
DETAILED COURSE PROGRAM
Introduction
- Computational problems and algorithms: the sorting problem
- Algorithms as technology
- Incremental methodology: examples and implementations
- Recursive or divide-and-conquer methodology: examples and implementations
Sorting and order statistics
- Incremental methodology applied to the sorting problem
- Recursive methodology applied to the sorting problem
- Heap and procedure for its construction
- Implementation of a Heap and its procedures
- Heapsort algorithm and its implementation
- Priority queues and their implementation
- The Quicksort algorithm and its randomized version
- Sorting in linear time: Counting-Sort, Radix-Sort, Bucket-Sort algorithms
- Implementation of Counting-Sort
- Medians and order statistics
Hashing
- Definition and characteristics of hash tables
- Hashing with concatenation
- Hash functions (division method, multiplication method, universal hashing)
- Implementation of a hash table with concatenation
- Hashing with open addressing
- Scanning methods (linear scanning, quadratic scanning, dual hashing)
- Implementation of a hash table with open addressing
Red-black trees
- Characteristics and definitions
- Rotation operations in a binary search tree
- Insertion into a red-black tree
- Deletion in a red-black tree
Elements of dynamic programming
- Characterization: optimal substructure, repetition of subproblems, reconstruction of an optimal solution.
- Some case studies: assembly line programming, multiplication of a sequence of matrices, knapsack problem, remainder problem.
Elements of the greedy strategy
- Characterization: properties of greedy choice, optimal substructure
- Some case studies: task selection problem, Huffman code construction, knapsack problem, remainder problem.
Elementary algorithms for graphs
- Minimum paths from single source: Bellman-Ford algorithm, minimum paths from single source in acyclic oriented graphs, Dijkstra algorithm.
- Minimum paths between all pairs: algorithm based on matrix multiplication, Floyd-Warshall algorithm.
- Implementation of minimum walk algorithms on graphs.
Textbook Information
The recommended textbook is:
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009
Course Planning
| Subjects | Text References | |
|---|---|---|
| 1 | Introduzione. Algoritmi come tecnologia. | Cap.1.1-1.2 di 1) |
| 2 | Algoritmo Insertion-Sort | Cap. 2.1 di 1) e materiale didattico integrativo |
| 3 | Divide-et-impera | Cap. 4.1 di 1) e materiale didattico integrativo |
| 4 | Heapsort | Cap. 6 di 1) e materiale didattico integrativo |
| 5 | Quicksort | Cap. 7 di 1) |
| 6 | Ordinamento in tempo lineare | Cap. 8 di 1) e materiale didattico integrativo |
| 7 | Hashing | Cap. 11.1-11.4 di 1) e materiale didattico integrativo |
| 8 | Alberi rosso-neri | Cap. 13 di 1) e materiale didattico integrativo |
| 9 | Elementi della programmazione dinamica | Cap. 15 di 1) e materiale didattico integrativo |
| 10 | Elementi della strategia golosa | Cap. 16.1-16.3 di 1) e materiale didattico integrativo |
| 11 | Algoritmi elementari per grafi | Capp. 24.1-24.4, 25-1 e 25-3 di 1) e materiale didattico integrativo |
Learning Assessment
Learning Assessment Procedures
The examination of the Algorithms module is divided into two parts: a first written test (compulsory) and a subsequent oral test (which may be optional for students admitted without reservation). These tests may take place electronically, should conditions require it.
At the end of the written test, the student will receive one of the following three evaluations:
- NOT ADMITTED to the oral test
- ADMITTED WITH RESERVE to the oral test
- ADMITTED to the oral test.
In the latter case the student will be notified of the grade obtained in the written test, which grade will be between 18 and 25.
The oral test may be held on the same day as the written test or a few days after it. The purpose of this test will be to assess in more detail the student's preparation, his or her ability to reason with regard to the topics covered in class, as well as his or her property of language.
The evaluation of the oral test should be understood as supplementing the grade obtained in the written test and not increasing it.
Students ADMITTED to the oral test may ask to be exempted from taking this test, thus accepting the grade communicated to them at the end of the written test.
Students ADMITTED WITH RESERVE will not be able to take advantage of the previous option and, should they wish to continue with the examination process, they will have to compulsorily take the oral test in order to complete the Algorithms module examination.
Students NOT ADMITTED to the oral test will have to repeat the written test in a subsequent appeal.
Please note that the Algorithms module exam and the Algorithms Lab module exam will be held concurrently and will therefore be assessed concurrently.