Free Course
Introduction to Graduate Algorithms
by
Offered at Georgia Tech as CS 8803 GA
Start Free Course
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.
Course Cost
Free
Timeline
Approx. 3 months
Skill Level
Advanced
Included in Course
Rich Learning Content
Interactive Quizzes
Taught by Industry Pros
Self-Paced Learning
Student Support Community
Join the Path to Greatness
This free course is your first step towards a new career with the Become an iOS Developer Nanodegree Program.
Free Course
Introduction to Graduate Algorithms
Enhance your skill set and boost your hirability through innovative, independent learning.
Course Leads
-
Eric Vigoda
Instructor
-
Arpan Chakraborty
Instructor
What You Will Learn
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
Prerequisites and Requirements
Students are expected to have an undergraduate course on the design and analysis of algorithms. In particular, they should be familiar with basic graph algorithms, including DFS, BFS, and Dijkstra's shortest path algorithm, and basic dynamic programming and divide and conquer algorithms (including solving recurrences). An undergraduate course in discrete mathematics is assumed, and students should be comfortable analyzing the asymptotic running time of algorithms.
The course uses the textbook Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani.
See the Technology Requirements for using Udacity.
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.
What do I get?
- Instructor videos
- Learn by doing exercises
- Taught by industry professionals
Related Courses
Introduction to Graduate Algorithms
Cyber-Physical Systems Design & Analysis
Educational Technology
Human-Computer Interaction
Computability, Complexity & Algorithms
Cyber-Physical Systems Security
Popular Courses
Udacity 现已提供中文版本！ A Udacity tem uma página em português para você! There's a local version of Udacity for you! Sprechen Sie Deutsch?
Besuchen Sie de.udacity.com und entdecken Sie lokale Angebote, unsere Partnerunternehmen und Udacitys deutschsprachigen Blog.
Zu de.udacity.com
continue in English