Home » Archivo » Archvio 2010 » Algoritmi e strutture dati - 2010/2011

Laurea in Informatica

Jump second level menu

Algoritmi e strutture dati - 8 CFU - A.A. 2010/2011

Teacher

Prof. Livio Colussi

Scheduled Period

II anno - 1 trimestre | 18/10/2010 - 11/12/2010

Hours: 48 Lessons, 0 Practice, 16 Exercises

Move Up ▲

Contents

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.

I Foundations.
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.

Suggested Courses: Programmazione.
Computer Programming.

Required Courses: - -

Teaching Support Tools: Slides of lectures and a set of solved exercise (in Italian).

Text Books: Introduzione agli Algoritmi e Strutture Dati. (seconda edizione)
T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein.
Editore McGraw-Hill Italia.

Move Up ▲

Contatore