Recursive algorithms and recurrence relations.The "Divide et Conquer" approach. "Greedy" algorithms. Dynamic Programming. String matching. NP-Complete problems. Approximation Algorithms. Unsolvable problems. Elements of algorithms on graphs, in bioinformatics, in computational geometry.
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.
M. Sisper, Introduzione alla teoria della computazione, Maggioli Editore, 2016. Collana Apogeo education.
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
Knowledge and understanding: lessons
Applying knowledge and understanding: class exercises to be carried on autonomously
Making judgements: discussion of the main topics of the course
Learning skills: lessons
Further information
Frequency of lectures: recommended.
Type of Assessment
The final exam is designed to ensure the acquisition of knowledge and skills by conducting an oral test.
The oral test is a conversation with the teacher in order to verify the ability in problem-solving and theoretical knowledges.
Course program
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.