587SM-2 - ALGORITHMIC DESIGN 2020
Section outline
-
This lesson introduces the course, presents the main topics and details time schedule and exam rules.
-
This lesson presents the notion of algorithm, introduces the selected computational model and details O, Omega, and Theta notations. Finally, it describes some useful notions and abstract data types.
-
This unit defines the matrix multiplication problem, presents the standard naive algorithm to solve it and introduces the alternative divide-and-conquer solution strategy. Finally, it details the Strassen's algorithm and shows how to evaluate its asymptotic complexity by mean of recursion trees.
-
This unit presents a motivating example, defines the problem and proposes a naive solution for it. The drawbacks of the naive solution are unravelled and some observations trace the route to a recursive algorithm based on dynamic programming. This algorithm is then reduced to a fully iterative solution. The asymptotic complexity of this last version is revealed.
-
Motivations and definition of heap. Binary heaps: definition and possible array-based implementation. Min-heaps and Max-heaps. Finding the minimum, removing the minimum, building a binary heap, decreasing a key, and inserting a new node: intuition, pseudo-code, and complexity intuition.
-
These lessons introduce the notion of index and detail the dichotomic searching unravelling, at the same time, the importance of sorting data to quickly retrieve them. Some of the most relevant sorting algorithms, as well as the select algorithm, are also presented.
-
Binary Search Trees: motivation, definition and properties. Insertions, searches, and deletions: intuition, examples, pseudo-code, and complexity. Red Black Trees: motivation, definition, and properties. Insertions and searches: intuition, examples, pseudo-code, and complexity. Deletions: intuition, complexity, and pseudo-code.
-
Motivations. Definition of (un)directed graph. How to represent a graph. Graph traversal: Breadth-First Search and Depth-First Search. Intuition, examples, pseudo-code, complexity, and properties. Topological Sort: motivations, intuition, pseudo-code, complexity, and sketch of correctness. Transitivity Closure: naive algorithm and complexity, intuition, and complexity.
-
Single-Source Shortest Paths Problem. All Pairs Shortest Paths Problem. Routing. Contraction Hierarchy.
-
Basic notions and properties on strings. The string-matching problem: Knuth-Morris-Pratt algorithm.