Laurea in InformaticaJump second level menu
Algoritmi e strutture dati - 8 CFU - A.A. 2010/2011
Prof. Livio Colussi
II anno - 1 trimestre | 18/10/2010 - 11/12/2010
Hours: 48 Lessons, 0 Practice, 16 Exercises
The course covers roughly the content of the first 5 chapters of the textbook: Introduction to Algorithms and Data Structure by Cormen, Leiserson, Rivest and Stein.
Informal analysis of InsertSort: counting the execution steps. Growth of functions: asymptotic notations. Analysis of MergeSort algorithm. Solution of recurrences: the master theorem. Analysis of QuickSort: expected running time. Randomized QuickSort.
II Sorting and order statistics
Analysis of HeapSort. Lower bounds for sorting. Priority queues. Sorting in linear time: CountingSort, RadixSort e BucketSort. Selection in expected linear time.
III Data Structures
Hash tables. Binary search trees. Red-black trees. Augmenting data structures. Interval trees.
IV Advanced Design and Analysis Techniques.
Dynamic programming. Greedy algorithms. Amortized analysis.
V Advanced Data Structures
B-trees. Binomial heaps. Data structure for disjoint sets.
Required Courses: - -
Teaching Support Tools: Slides of lectures and a set of solved exercise (in Italian).
Introduzione agli Algoritmi e Strutture Dati. (seconda edizione)
T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.
Editore McGraw-Hill Italia.