CS6215 Introduction to Graduate Algorithms
This course is a graduate-level course in the design and analysis of algorithms. We study techniques for the design of algorithms (such as dynamic programming) and algorithms for fundamental problems (such as fast Fourier transform FFT). In addition, we study computational intractability, specifically, the theory of NP-completeness. The main topics covered in the course include: dynamic programming; divide and conquer, including FFT; randomized algorithms, including RSA cryptosystem; graph algorithms; max-flow algorithms; linear programming; and NP-completeness.
This was a nice course in algorithms, however given my Maths background it had a lot of repeated knowledge. However, it was good to do it from a more algorithmic point of view.
Lectures
- Week 1 - Dynamic Programming
- Week 1 - Knapsack Problem
- Week 2 - Chain Matrix Multiply
- Week 2 - Shortest Paths
- Week 3 - Fast Integer multiplication
- Week 3 - Linear-Time Median
- Week 3 - Solving Recurrences
- Week 4 - Fast Fourier Transforms
- Week 6 - Graph algorithms - strongly connected components
- Week 6 - 2-Satisfiability
- Week 6 - Minimum Spanning Tree
- Week 7 - Ford-Fulkerson Algorithm
- Week 7 - Max-Flow Min-Cut
- Week 7 - Image Segmentation
- Week 7 - Edmonds-Karp algorithm
- Week 7 - Max-flow Generalizations
- Week 8 - Modular Arithmetic
- Week 8 - RSA
- Week 8 - Bloom Filters
- Week 10 - NP overview
- Week 10 - NP-completeness
- Week 10 - Graph problem complexity
- Week 11 - Linear Programming
- Week 12 - Max-SAT approximation algorithm
- Week 12 - Knapsack complexity
- Week 12 - Halting problem
- Week 15 - Markov Chains