Introduction to Graduate Algorithms (Udacity)

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.

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