Learning objectives
Knowledge and understanding
The objective of the course is to show the main algorithmic methods and data structures used in software development, by means of pseudo-code. The student will be then able to evaluate the best algorithm (in terms of computational cost and other factors) and the best data structures to be used given a problem to be solved.
Applying knowledge and understanding
The student will acquire the ability to understand algorithmic techniques to be used to solve in a correct and effective way a given problem. He/she will be also capable of understanding and evaluating the data structures to be used for an effective solution (in terms of computation and memory) of the problem.
Prerequisites
- - -
Course unit content
The course introduces the students to the algorithms and data structures used in the solution of fundamental problems, by presenting principles and techniques which allow us a systematic analysis. The objective is to provide the student with the tools for designing correct and effective algorithmic solutions, and for identifying, in case of alternatives, the most suitable solution for a given problem. The main topics are: computational complexity analysis, basic abstract data types, sorting algorithms, binary search trees, hash tables, oriented and non-oriented graphs.
Full programme
The course includes lessons on the following topics (duration is indicative):
- Algorithms and data structures: introduction and examples. Introduction to the concept of cost (time and memory space). (2 hours)
- Asymptotic notations for cost functions and analysis methods (worst, average and best case). (2 hours)
- Analysis methods for recursive algorithms: recursion tree, iteration, substitution, Master Theorem. (5 hours)
- Abstract data types (dictionary, stack, queue) and their implementation (6 hours)
- Trees: traversal algorithms (DFT and BFT) (6 hours)
- Incremental sorting algorithms (description, implementation and analysis): SelectionSort, InsertionSort, BubbleSort, HeapSort, MergeSort, QuickSort. Lower bound on the sorting cost for model based on comparisons (6 hours)
- Sorting algorithms for integer (description, implementation and analysis): IntegerSort, BucketSort, RadixSort (3 hours)
- Binary search trees, AVL trees, splay trees, 2-3 trees, B-trees, B*-trees, 2-3-4 trees, red-black trees (6 hours)
- Hash tables: direct access tables, collision problem (3 hours)
- Oriented and non-oriented graphs, and their representation. Traversal algorithms (description, implementation and cost) (3 hours)
- Greedy algorithmic technique. minimum spanning tree and its computation with greedy algorithm. Algorithms of Kruskal, of Prim and of Boruvka. (3 hours)
- Shortest paths on graphs and corresponding algorithms (description, implementation and analysis): distance computation, algorithm of Bellman and Ford, computation of shortest paths with single source on acyclic graphs, Dijkstra algorithm (7 hours)
Bibliography
- C. Demetrescu, I. Finocchi, G.F. Italiano, "Algoritmi e strutture dati", 2a ed., McGraw-Hill
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, "Introduzione agli algoritmi e strutture dati", 3a ed., McGraw-Hill
- A. Bertossi, A. Montresor, "Algoritmi e strutture di
dati", 2a ed., Città Studi
Teaching methods
The course includes frontal lectures for about 48 hours, assisted by exercises in preparation of the exam.
Assessment methods and criteria
The exam consists of a written script with several exercises which require the writing of algorithms in pseudo-code, the step-by-step explanation of algorithms, the motivation of choices in terms of algorithm and/or data structures for the solution of a given problem.
Other information
- - -
