Schema della sezione

  • Introduzione

    Minimizza tutto Espandi tutto

    • Amortized analysis: aggregate analysis and accounting method. Chapters 17.1 and 17.2 of Cormen's book.

    • Red-black trees: definition and properties. Rotations and insertion procedure. Chapters 13.1, 13.2 and 13.3 of Cormen's book.

    • Hash tables: definition and properties of hash tables and hash functions. Collision resolution by chaining. Analysis of hashing with chaining. Dynamic hash tables and their analysis. Chapters 11.1, 11.2, 11.3 (for the latter, only the paragraph "What makes a good hash function?") and 17.4 of Cormen's book. 

    • Exact pattern matching on strings: definition of string matching.The naive algorithm. The Knuth-Morris-Pratt algorithm and its analysis. The Boyer-Moore-Galil algorithm. Chapter 32 of Cormen's book, excluding 32.2 and 32.3; Chapter 2.2  of Gusfield's book (please find it in Teams: Materiale del corso)

    • Multiple exact pattern matching: definition of suffix tree and suffix links. Representation of the branches of the suffix tree and implied time and space complexities. Use of the suffix tree for (multiple) exact pattern matching. Definition of suffix array and its use for exact pattern matching. Chapters 5, 6.1 (for the latter, only the definition of suffix links), 6.5, 7.1, 7.14 (until 7.14.4) of Gusfield's book; see also Ben Langmead's slides on tries, suffix trees and suffix arrays and the "survey_suffix_tree" paper.

    • Approximate pattern matching: definition of Hamming distance. Definition of k-mismatch problem. Definition of Longest common extensions. Solution to k-mismatch via longest common extensions. Definition of Edit distance. Dynamic programming algorithm for computing the edit distance. Chapters 9.1, 9.4, 11.2 and 11.3 of Gusfield's book. 


  • Red-black trees, Hashing, Amortised analysis

  • Exact pattern matching

  • Approximate pattern matching

  • Topic 4

  • Topic 5

  • Topic 6

  • Topic 7

  • Topic 8

  • Topic 9

  • Topic 10