Schema della sezione

  • Link to Teams: Home

    Basic notions: definition of algorithm, how to read and write pseudocode, asymptotic analysis, definition of the RAM model. Chapters 2.1, 2.2 and 3.2 of Cormen's book.

    Sorting and co: Insertion sort, Merge sort, Heaps and priority queues, Heap sort, Quick sort, Lower bound on sorting, Counting sort, Radix sort. Chapters 2.2, 2.3.1, 6, 7, 8.1, 8.2 and 8.3 of Cormen's book.

    Binary search trees: definition, search, insertions, deletions. BST sort (inorder tree walk) and comparison with Quick sort. Chapters 12.1, 12.2, 12.3 and Problem 12-3 of Cormen's book.

    Unweighted graphs: definition, representations of graphs, breadth-first search, shortest paths in unweighted graphs, depth-first search, edge classification, cycle detection, topological sort. Chapters 22.1, 22.2, 22.3 and 22.4 of Cormen's book.

    Weighted graphs: definition. Single-source shortest paths (SSSP) problem: general scheme, edge relaxation, optimal substructure of shortest paths, topological-sort-based algorithm for SSSP on DAGS, Bellman-Ford algorithm for SSSP, Dijkstra's algorithm for SSSP. All-pairs shortes paths: Floyd-Warshall algorithm. Chapters 24.0, 24.1, 24.2, 24.3, 24.5 and 25.2 of Cormen's Book.

    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.