Vai al contenuto principale Vai al footer
Università degli Studi di Parma Università degli Studi di Parma
University of Parma
Course catalogue
Università degli Studi di Parma
course catalogue

ALGORITHMS AND DATA STRUCTURES II
cod. 16827

Academic year 2009/10
3° year of course - Second semester
Professor
Grazia LOTTI
Academic discipline
Informatica (INF/01)
Field
Formazione interdisciplinare e applicativa
Type of training activity
Related/supplementary
60 hours
of face-to-face activities
6 credits
hub:
course unit
in - - -
lectures timetable unavailable
exam calls
Print

Learning objectives

Overview of  some of the most important algorithms

Prerequisites

Algoritmi e strutture dati e Laboratorio di  Algoritmi e strutture dati

Course unit content

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

Full programme

- - -

Bibliography

<br />
<br />
[1] C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1995. <br />
[2] A. Bernasconi, B. Codenotti, Introduzione alla Complessita Com- <br />
putazionale, McGraw-Hill, 1998. <br />
[3] D. Gusfield, Algorithms on String, Trees, and Sequences: Computer science <br />
and Computational Biology Cambridge University Press, 1997. <br />

Teaching methods

- - -

Assessment methods and criteria

- - -

Other information

- - -

2030 agenda goals for sustainable development

- - -