Introduction to Graduate Algorithms

Online Course

Udacity

Go to Udacity

Start Learning

What is the course about?
Prerequisites & Facts
Cost, Certificate & Degree
Reviews & Experiences

What is the course about?

Introduction to Graduate Algorithms

The course Introduction to Graduate Algorithms is an online class provided by Udacity. The skill level of the course is Advanced. It may be possible to receive a verified certification or use the course to prepare for a degree.

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).

Course description

Introduction to Graduate Algorithms
3 months

Offered at Georgia Tech as CS 8803 GA
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.

Dynamic Programming
Randomized Algorithms
Divide and Conquer
Graph Algorithms
Max-Flow Problems
Linear Programming
NP-Completeness

Fibonacci Numbers, Longest Increasing Subsequence (LIS), Longest Common Subsequence (LCS)
Knapsack, Chain Matrix Multiplication
Shortest Path Algorithms
Modular Arithmetic: Fast Modular Exponentiation, Multiplicative Inverses
RSA Cryptosystem: Fermat’s Little Theorem, RSA Protocol, Primality Testing
Hashing: Traditional Chain Hashing, Bloom Filters
Fast Integer Multiplication
Linear-Time Median
Fast Fourier Transform
Strongly Connected Components, 2-Satisfiability
Minimum Spanning Tree
Markov Chains, PageRank
Ford-Fulkerson Algorithm
Max-Flow Min-Cut Theorem, Edmonds-Karp Algorithm
Max-Flow applied to Image Segmentation
Simplex Algorithm
Weak and Strong Duality
Max-SAT Approximation
Complexity Classes: P, NP, NP-Complete
NP-Complete Problems: 3-SAT, Independent Set, Clique, Vertex Cover, Knapsack, Subset-Sum
Halting Problem

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.

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.

Start Learning

Prerequisites & Facts

Introduction to Graduate Algorithms

Course Topic

iOS Developer

University, College, Institution

Udacity

Course Skill Level

Advanced

see course summary

Course Language

English

Place of class

Online, self-paced (see curriculum for more information)

Degree

Certificate

Start Learning

Degree & Cost

Introduction to Graduate Algorithms

To obtain a verified certificate from Udacity you have to finish this course or the latest version of it, if there is a new edition. The class may be free of charge, but there could be some cost to receive a verified certificate or to access the learning materials. The specifics of the course may have been changed, please consult the provider to get the latest quotes and news.

Udacity

Introduction to Graduate Algorithms

provided by Udacity

Start Learning