Algorithms and LAB A - LModule Algorithms
Academic Year 2022/2023 - Teacher: Domenico CANTONEExpected 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
Elementary data structures and algorithms for their manipulation (lists, queues, stacks, trees).
Elements of discrete mathematics, of programming I and II, and of mathematical analysis
Attendance of Lessons
For a full understanding of the course topics and of the techniques illustrated, lesson attendance is strongly recommended.
Detailed Course Content
General description
The course presents the main design methodoligies (incremental, recursion, dynamic programming, greedy algorithms) and the techniques for their complexity analysis, both in the worst and average cases.
DETAILED SYLLABUS
Introduction
Computational problems and algorithms: the sorting problem
Algorithms as technology
Incremental methodology: Insertion-Sort (correctness and complexity)
Divide-and-Conquer methodology: Merge-Sort (complexity)
Asymptotic notations and relationships among them
Standard notations and common functions.
Recurrences
The substitution method
The iterative method and the recursion tree
The master theorem
Sorting and order statistics
Heaps and their construction
Priority queues
Quicksort and its randomized version
Analysis of Quicksort in the worst- and average case
Lower bounds for sorting
Sorting in linear time: Counting-Sort, Radix-Sort, Bucket-Sort
Medians and order statistics
Hashing
Hash table
Hash functions (division method, multiplication method, universal hashing)
Open addressing
Red-black trees
Rotations, insertions, deletions
Complexity analysis
Elements of dynamic programming
Optimal substructure, overlapping subproblems, reconstructing an optimal solution
Some case studies: assembly line scheduling, matrix-chain multiplication, longest common subsequence, editing distance
Elements of the greedy strategy
Greedy-choice property, optimal substructure
Some case studies: the activity-selection problem, Huffman codes
Elementary graph algorithms
Single-source shortest paths: the Bellman-Ford algorithm, single-source shortest paths in oriented acyclic graphs, Dijkstra's algorithm
All-pairs shortest paths: the Floyd-Warshall algorithm, transitive closure of oriented graphs
Textbook Information
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 | Ricorrenze | Cap. 4.3-4.5 di 1) e materiale didattico integrativo |
| 5 | Heapsort | Cap. 6 di 1) e materiale didattico integrativo |
| 6 | Quicksort | Cap. 7 di 1) |
| 7 | Ordinamento in tempo lineare | Cap. 8 di 1) e materiale didattico integrativo |
| 8 | Hashing | Cap. 11.1-11.4 di 1) e materiale didattico integrativo |
| 9 | Alberi rosso-neri | Cap. 13 di 1) e materiale didattico integrativo |
| 10 | Elementi della programmazione dinamica | Cap. 15 di 1) e materiale didattico integrativo |
| 11 | Elementi della strategia golosa | Cap. 16.1-16.3 di 1) e materiale didattico integrativo |
| 12 | 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
Please note that, in any case, before the exam verbalization the student must have passed the exam of the relative Laboratory module.
The examination of the Algorithms module is divided into two parts: a first written test (mandatory) and a subsequent oral exam (which may be optional for students admitted without reserve). These tests may take place electronically, should the 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 examination
- ADMITTED WITH RESERVE to the oral examination
- ADMITTED to the oral examination
In the latter case, the student will be notified of the grade obtained in the written test, which will be between 18 and 25.
The oral examination can take place on the same day as the written exam or after a few days from it. The oral examination has the purpose of evaluating in more detail the preparation of the student, her/his ability to reason in relation to the topics covered in class, as well as her/his language skills.
The oral examination supplements the written exam and its evaluation is therefore not to be understood as a mere increase in the grade obtained in the written test.
Students ADMITTED to the oral examination may ask to be exempted from it and accept 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 will have to take the oral exam to complete the examination of the Algorithms module.
Students NOT ADMITTED to the oral examination will have to repeat the written examination in a subsequent session.
Please note that, in any case, before the exam verbalization the student must have passed the exam of the relative Laboratory module.