Introduction to Graduate Algorithms
About this Course
This 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 or 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; …
Introduction to Graduate Algorithms
About this Course
This 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 or 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 and hashing using Bloom filters; graph algorithms; max-flow algorithms; linear programming; and NP-completeness.
Learn advanced techniques for designing algorithms and apply them to hard computational problems.
[
The design and analysis of algorithms form an essential basis for computer science. This course is useful for those who want to pursue advanced studies in computer science, as well as those who want to work as a software engineer.
]
lesson 1
Dynamic Programming
Fibonacci Numbers, Longest Increasing Subsequence (LIS), Longest Common Subsequence (LCS)
Knapsack, Chain Matrix Multiplication
Shortest Path Algorithms
lesson 2
Randomized Algorithms
Modular Arithmetic: Fast Modular Exponentiation, Multiplicative Inverses
RSA Cryptosystem: Fermat’s Little Theorem, RSA Protocol, Primality Testing
Hashing: Traditional Chain Hashing, Bloom Filters
lesson 3
Divide and Conquer
Fast Integer Multiplication
Linear-Time Median
Fast Fourier Transform
lesson 4
Graph Algorithms
Strongly Connected Components, 2-Satisfiability
Minimum Spanning Tree
Markov Chains, PageRank
lesson 5
Max-Flow Problems
Ford-Fulkerson Algorithm
Max-Flow Min-Cut Theorem, Edmonds-Karp Algorithm
Max-Flow applied to Image Segmentation
lesson 6
Linear Programming
Simplex Algorithm
Weak and Strong Duality
Max-SAT Approximation
lesson 7
NP-Completeness
Complexity Classes: P, NP, NP-Complete
NP-Complete Problems: 3-SAT, Independent Set, Clique, Vertex Cover, Knapsack, Subset-Sum
Halting Problem
