Computer science | University of Parma

Professor
Academic discipline: Informatica (INF/01)
Field: Discipline informatiche
Type of training activity: Characterising

48 hours
of face-to-face activities

6 credits

hub: PARMA

course unit
in - - -

lectures timetable unavailable

exam calls

Learning objectives

Overview of some of the most important algorithms

Prerequisites

algoritmi e strutture dati 1

Course unit content

• greedy algorithms, dynamic programming, branch-bound algorithms, local
search, Metropolis, simulated annehaling;
• computational geometry: convex hull, point location, polygonal triangu-
lation, sweeping algorithm, closest pair algorithm;
• DFT-IDFT: Cooley -Tuckey FFT algorithm, polynomial product/division,
interpolating polynomial, chinese remainder theorem, nite eld FFT,
Schonhage-Strassen algorithm for integer product;
• bilinear forms computation, matrix multiplication and related problems,
matrix multiplication algorithms;
• exact string matching: automata, Knuth-Morris-Pratt, Boyer-Moore, Aho-
Corasick algorithms; approximate string matching: Hamming distance,
edit distance, dynamic programming; trie, suffix tree, suffix array;
• the complexity classes P, NP, NPC and their relations, polynomial reduc-
tion, classes LOGSPACE and PSPACE, probabilistic complexity classes,
probabilistic algorithms, approximate algorithms.

Full programme

- - -

Bibliography

[1] F.P.Preparata, M.I.Shamos, Computational Geometry, Springer-Verlag.
[2] J.Kleinberg, E.Tardos, Algorithm design, Addison Wesley.
[3] C. H. Papadimitriou, Computational Complexity, Addison Wesley.
[4] A. Bernasconi, B. Codenotti, Introduzione alla Complessita Com-
putazionale, McGraw-Hill.
[5] D. Guseld, Algorithms on String, Trees, and Sequences: Computer science
and Computational Biology ,Cambridge University Press.

Teaching methods

class

Assessment methods and criteria

oral exam

Other information