Introduction to Graduate Algorithms
Georgia Institute of Technology via Udacity
Overview
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.
Why Take This Course?
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.
Syllabus
Dynamic Programming
- Fibonacci Numbers, Longest Increasing Subsequence (LIS), Longest Common Subsequence (LCS)
- Knapsack, Chain Matrix Multiplication
- Shortest Path Algorithms
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
Divide and Conquer
- Fast Integer Multiplication
- Linear-Time Median
- Fast Fourier Transform
Graph Algorithms
- Strongly Connected Components, 2-Satisfiability
- Minimum Spanning Tree
- Markov Chains, PageRank
Max-Flow Problems
- Ford-Fulkerson Algorithm
- Max-Flow Min-Cut Theorem, Edmonds-Karp Algorithm
- Max-Flow applied to Image Segmentation
Linear Programming
- Simplex Algorithm
- Weak and Strong Duality
- Max-SAT Approximation
NP-Completeness
- Complexity Classes: P, NP, NP-Complete
- NP-Complete Problems: 3-SAT, Independent Set, Clique, Vertex Cover, Knapsack, Subset-Sum
- Halting Problem
Taught by
Arpan Chakraborty and Eric Vigoda
Related Courses
-
Algorithms, Part II
Princeton University
4.8 -
Number Theory and Cryptography
University of California, San Diego , Higher School of Economics
-
Advanced Graph Theory
Indian Institute of Technology Kanpur, NPTEL, Indian Institute of Technology Patna
-
Data Structures & Algorithms IV: Pattern Matching, Dijkstra’s, MST, and Dynamic Programming Algorithms
Georgia Institute of Technology
-
Computability, Complexity & Algorithms
Georgia Institute of Technology
5.0 -
Advanced Algorithms and Complexity
University of California, San Diego , Higher School of Economics
3.0
Reviews
0.0 rating, based on 0 reviews
Never Stop Learning!
