Fall 2023
Dominik Kempa
- Introduction
- Big-O notation
- Integer exponentiation by squaring
- Euclid's GCD
- Least Common Ancestor
- String Search
- KMP Algorithm
- Karp-Rabin Algorithm
- Suffix Tree
- Suffix Tree
- Longest Common Substring (LCS)
- Suffix Array
- Suffix Array
- Random Minimum Query (RMQ)
- LCP Array
- Sorting
- Merge Sort
- Heap Sort
- Quicksort
Midterm 1 - Counting Sort
- Radix Sort
- Fast Multiplication
- Divide-and-conquer multiplication
- Karatsuba's Algorithm
- Edit Distance
- Dynamic Programming
- Global comparison
- Edit Distance
- Longest Common Subsequence
- Local comparison
- Approximate Pattern Matching
- Knapsack
- Subset Sum
- Knapsack problem
- Optimal BST
- Optimal BST
- Chain Matrix Multiplication
- Chain Matrix Multiplication
- Scheduling
- Scheduling
Midterm 2
- Scheduling
- Huffman Coding
- Huffman Coding
- BFS
- Directed Graphs
- Breadth First Search
- Two Coloring
- DFS
- Depth First Search
- Topological Sort
- Strongly Connected Components
- Shortest Paths
- Dijkstra's Algorithm
- Bellman-Ford Algorithm
- All Pairs Shortest Paths
- Floyd-Warshall Algorithm
- NP-Hardness
- NP-Hardness
- NP-Completeness