Learning objectives
Students will study, design and analyze algorithms and data structures for the efficient solution of many different problems, highlighting the applicative contests in which the considered algorithms and data structures can be successfully employed. This course deepens and extends the algorithmic notions given in Algoritmi e Strutture dati 1.
Knowledge and understanding:
The main objective of this course is to give a deeper insight to the most important and useful algorithms and data structures.
Applying knowledge and understanding:
Students will be able to design and analyze algorithms fo medium-difficult problems.
Making judgements:
Ability to judge the quality of a software solution by means of efficency and possibly reuse. Students will be able to appreciate the consequence of their algorithmic results.
Communication skills:
Ability to motivate and explain efficient programming concepts, relevant alternatives and decision recommendations, even to nonprofessional audience. Students will be able to highlight the technological consequences of their theoretical studies.
Learning skills: Students can keep up-to-date with the latest developments in algorithmics by consulting scientific journals and advanced books. The knowledge acquired in the course will allow the students to attend both master and specialistic classes.
Prerequisites
Algoritmi e strutture dati 1, Fondamenti di Programmazione A
Course unit content
This course deepens and extends the algorithmic notions given in Algoritmi e Strutture dati 1.
• tecnica greedy algorithms, dynamic programming: further applications;
• randomized algorithms, Miller-Rabin algorithm;
• parallel algorithms, PRAM, basic algorithms, Brent theorem;
• external memory model, k-way mergesort, distribution sorting;
• cache oblivious model, basic algorithms;
• online algorithms, competitive analysis; paging: LRU, Random, Marking; web caching: greedy dual, greedy dual size;
• computational geometry: convex hull, sweeping algorithm;
• DFT-IDFT: FFT algorithm, Cooley –Tuckey algorithm, polynomial multiplication, finite field FFT, Schonhage-Strassen algorithm for integer multiplication (sketch);
• exact string matching: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, suffix tree, suffix array;
• the complexity classes P, NP, NPC and their relations, polynomial reduction, approximate algorithms.
Full programme
• greedy algorithms, dynamic programming: further applications;
• randomized algorithms, Miller-Rabin algorithm;
• parallel algorithms, PRAM, basic algorithms, Brent theorem;
• external memory model, k-way mergesort, distribution sorting;
• cache oblivious model, basic algorithms;
• online algorithms, competitive analysis; paging: LRU, Random, Marking; web caching: greedy dual, greedy dual size;
• computational geometry: convex hull, sweeping algorithm;
• DFT-IDFT: FFT algorithm, Cooley –Tuckey algorithm, polynomial multiplication, finite field FFT, Schonhage-Strassen algorithm for integer multiplication (sketch);
• exact string matching: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, suffix tree, suffix array;
• the complexity classes P, NP, NPC and their relations, polynomial reduction, approximate algorithms.
Bibliography
• F.P.Preparata, M.I.Shamos, Computational Geometry, Springer-Verlag, 1985.
• J.Kleinberg, E.Tardos, Algorithm design, Addison Wesley,2006.
• C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1994
• D.Gusfield, Algorithms on String, Trees, and Sequences: Computer science and Computational Biology, Cambridge University Press, 1997.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, third edition, 2011.
• C. Demestrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, McGraw Hill, seconda edizione, 2008.
• P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Pearson, prima edizione, 2006.
Teaching methods
Class
Assessment methods and criteria
Final oral examination based on the topics discussed in class. Project development and/or seminar discussion in algorithms, data structures and complexity take place. The purpose is to test the algorithmic design skills of the students. Students can get the minimum grade by showing a sufficient knowledge of the tools for the analysis and synthesis of the algorithms discussed in class.
Other information
- - -
