468SM - FUNDAMENTALS OF ALGORITHMS 2021
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 binary search. Moreover, they unravel the importance of sorting data to quickly retrieve them. Some of the most relevant sorting algorithms 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.
-
Please ignore Exercise 2 of the last set of exercises. Topological sort is not defined on undirected graphs.