S. Baase, Computer Algorithms Introduction to Design and Analysis, 2nd Edition, Addison Wesley, 1988.
A. Bertossi, Algoritmi e strutture di dati, Utet Libreria, 2000.
A. Bertossi, A. Montresor, Algoritmi e strutture di dati, Citt a’ Studi Edizioni, 2010.
T. H. Cormen, C.E. Leiserson, R. L. Rivest, Introduzione agli algoritmi, Jackson Libri, 2003.
P. Crescenzi, G. Gambosi, R. Grossi, Strutture di dati e algoritmi - Progettazione, analisi e visualizzazione, Pearson Addison Wesley, 2006.
C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, Seconda edizione, McGraw-Hill, 2008.
J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilit a’, Addison-Wesly, 2003
Learning Objectives
Knowledge acquired:
Knowledge of the most important algorithm techniques and the basic principles of computational complexity.
Competence acquired:
Know how to develop new algorithms and evaluate their complexity.
Skills acquired (at the end of the course):
Ability to use their own knowledge with awareness in order to find resolutive strategies of real problems.
Prerequisites
Courses recommended: Computer science
Teaching Methods
Total hours of the course (including the time spent in attending lectures, seminars, private study, examinations, etc...): 150
Hours reserved to private study and other indivual formative activities: 102
Hours for lectures: 72
Hours for laboratory: 0
Hours for laboratory-field/practice: 0
Seminars (hours): 0
Stages (hours): 0
Intermediate examinations (hours): 0
Further information
Attendance of lectures, practice and lab:
Not mandatory
Recursive algorithms and recurrence relations.
The “Divide et Conquer” approach: product of integers; matrix multiplication and the Strassen algorithm; the fast Fourier Transform and the polynomial product; the problem of the nearest points.
“Greedy” algorithms: activity planning; Huffman codes; points covered withs intervals.
Dynamic Programming: multiplication of n matrices; optimal triangulations; a shortest-path algorithm; the change problem; partition of integers; the Knapsack problem.
String matching: the distance of two strings; the problem of the longest common subsequence; finite autotomaton; the Knuth-Morris-Pratt algorithm; the Rabin-Karp algorithm.
NP-Complete problems. Approximation Algorithms. Unsolvable problems. Elements of computational geometry.