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 design techniques and the basic methods for computational complexity computation.
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
Algorithms correctness. Amortized analysis. Recursive algorithms and methods to solve recurrence relations.
The “Divide et Conquer” approach: characteristics, applicability. Examples: power number computation, computation of the first and second maximum, product computation of two both polynomials and matrices, HeapSort, computation of a maximum subsequence in a vector, computation of the two nearest points in the plane.
“Greedy” algorithms: characteristics, applicability. Examples: the problem of the representative, the change problem, activities planning and sequencing, Huffman codes, bin-packing, routing algorithms.
Dynamic Programming: characteristics, applicability. Examples: n-th Fibonacci number computation, the representative problem, the change problem, bin-packing, computation of a maximum subsequence in a vector, matrices multiplication, optimal triangulations, algorithms on graphs.
Strings: edit distance of two strings, the problem of the longest common subsequence, string-matching (finite automaton, the Knuth-Morris-Pratt algorithm, the Boyer-Moor algorithm, the Rabin-Karp algorithm).
NP-Complete problems: polynomial certificates; non determinism; polynomial reducibility; NP-completeness tests. Approximation algorithms: characteristics, applicability. Examples: job scheduling, set covering, vertex covering, graph coloring, bin packing.