T. H. Cormen, C.E. Leiserson, R. L. Rivest, Introduzione agli algoritmi, Jackson Libri, 2003.
J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education.
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.
A. Bertossi, A. Montresor, Algoritmi e strutture di dati, Citt a’ Studi Edizioni, 2010.
Learning Objectives
Knowledge acquired:
Knowledg the main algorithm design techniques, methods to demonstrate their correctness and to compute their computational complexity computation.
Competence acquired:
Know how to develop new algorithms and evaluate their complexity and correctness.
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 (Rabin-Karp algorithm, finite automaton, the Knuth-Morris-Pratt algorithm). Problems formulation.
NP, NP-c, NP-co e NP-h problems: polynomial certificates, non determinism, polynomial reducibility, NP-completeness tests. Approximation algorithms for NP-c problems: characteristics, applicability and approximating factor. Examples: k-SAT, set and vertex covering, graph coloring, hamiltonian cycles, job scheduling, bin packing.