587SM-2 - ALGORITHMIC DESIGN 2023
Schema della sezione
-
Dear students, please find below a SAMPLE FOR THE WRITTEN PART of the exam.
-
Sample exam File PDF
-
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.
-
-
Intro File PDF
-
Basics File PDF
-
Exercises01 File PDF
-
-
Dear students,
Please find below a set of papers among which you can pick the one to present for the exam. When you choose a paper, please write the title and your name in this file Paper_choice.xlsx to reserve it for the date on which you intend to take the exam.
-
16.FM Index File PDF
-
CDAWGS File PDF
-
affix array File PDF
-
38.WhatsHap File PDF
-
19.Omnitigs File PDF
-
Hat-trie File PDF
-
AA-Trees File PDF