Udacity Logo
Log InJoin for Free
Free

Introduction to Graduate Algorithms

Course

Last Updated March 7, 2022

Prerequisites:

No experience required

Course Lessons

Lesson 1

Introduction to Graduate Algorithms

Overview of main topics covered, course webpage available at: <a href="https://gt-algorithms.com">https://gt-algorithms.com</a>

Lesson 2

DP1: FIB, LIS, LCS

Dynamic programming: Toy problem (Fibonacci numbers), Longest Increasing Subsequence (LIS), and Longest Common Subsequence (LCS).

Lesson 3

DP2: Knapsack, Chain Multiply

Dynamic programming: Knapsack, and Chain Matrix Multiplication.

Lesson 4

DP3: Shortest Paths

Dynamic programming algorithms for solving various shortest path problems on graphs.

Lesson 5

RA1: Modular Arithmetic

Modular Arithmetic: Fast Modular Exponentiation and Multiplicative Inverses.

Lesson 6

RA2: RSA

RSA Cryptosystem: Fermat's Little Theorem, RSA Protocol, and Primality Testing.

Lesson 7

RA3: Bloom Filters

Lecture about Hashing: Toy problem of Balls into Bins, Traditional Chain Hashing, and Bloom Filters.

Lesson 8

DC1: Fast Integer Multiplication

Faster Divide-and-Conquer Algorithm for Multiplying Large Integers.

Lesson 9

DC2: Linear-Time Median

Linear-time Divide-and-Conquer Algorithm for Finding the Median from an unsorted list.

Lesson 10

DC3: Solving Recurrences

Refresher Lecture about Solving Recurrences.

Lesson 11

DC4: FFT - Part 1

High-level approach for polynomial multiplication and FFT (Fast Fourier Transform). Primer on complex numbers, including complex roots of unity.

Lesson 12

DC5: FFT - Part 2

FFT and polynomial multiplication algorithms, and inverse FFT.

Lesson 13

GR1: Strongly Connected Components

Connectivity: Connected components of undirected graphs, Topological sorting of a DAG, and strongly connected components of general directed graphs.

Lesson 14

GR2: 2-Satisfiability

Polynomial-time algorithm for 2-SAT, using the SCC algorithm.

Lesson 15

GR3: Minimum Spanning Tree

Minimum Spanning Tree (MST): Cut Property for MST's, and Kruskal's MST algorithm.

Lesson 16

GR4: Markov Chains and PageRank

Introduction to Markov Chains, and an exposition of the PageRank algorithm.

Lesson 17

MF1: Ford-Fulkerson Algorithm

Max-flow: Problem statement, residual network, and Ford-Fulkerson algorithm.

Lesson 18

MF2: Max-Flow Min-Cut

Max-Flow Min-Cut Theorem: Statement and Proof, and proof of correctness of Ford-Fulkerson and Edmonds-Karp augmenting path algorithms.

Lesson 19

MF3: Image Segmentation

Max-flow: Application to Image Segmentation problem.

Lesson 20

MF4: Edmonds-Karp Algorithm

Max-flow: Edmonds-Karp augmenting path algorithm.

Lesson 21

MF5: Max-Flow Generalization

Max-flow: Generalization allowing demand constraints.

Lesson 22

LP1: Linear Programming

Linear Programming: Basics, Standard Form, and Simplex Algorithm Overview

Lesson 23

LP2: Geometry

Geometry of Linear Programs: Feasible Region, Infeasible LP's, and Unbounded LP's.

Lesson 24

LP3: Duality

Dual of a Linear Program; Converting an LP problem to its Dual; Weak and Strong Duality.

Lesson 25

LP4: Max-SAT Approximation

Maximum Satisfiability Problem; Approximate Solutions; Integer Programming; Calculus.

Lesson 26

NP1: Definitions

NP: Definition of a Search Problem and Computational Complexity Classes P and NP; Proving a Problem is in NP; Reductions; and the notion of NP-Completeness

Lesson 27

NP2: 3SAT

3-SAT Problem is NP-Complete

Lesson 28

NP3: Graph Problems

NP-Completeness of Graph Problems: Independent Sets, Clique, and Vertex Cover

Lesson 29

NP4: Knapsack

Knapsack and Subset Sum Problems are NP-Complete

Lesson 30

NP5: Halting Problem

Halting Problem is Undecidable

Taught By The Best

Photo of Eric Vigoda

Eric Vigoda

Instructor

Photo of Arpan Chakraborty

Arpan Chakraborty

Instructor

Arpan is a computer scientist with a PhD from North Carolina State University. He teaches at Georgia Tech (within the Masters in Computer Science program), and is a coauthor of the book Practical Graph Mining with R.

The Udacity Difference

Combine technology training for employees with industry experts, mentors, and projects, for critical thinking that pushes innovation. Our proven upskilling system goes after success—relentlessly.

Demonstrate proficiency with practical projects

Projects are based on real-world scenarios and challenges, allowing you to apply the skills you learn to practical situations, while giving you real hands-on experience.

  • Gain proven experience

  • Retain knowledge longer

  • Apply new skills immediately

Top-tier services to ensure learner success

Reviewers provide timely and constructive feedback on your project submissions, highlighting areas of improvement and offering practical tips to enhance your work.

  • Get help from subject matter experts

  • Learn industry best practices

  • Gain valuable insights and improve your skills

Get Started Today

Introduction to Graduate Algorithms

Month-To-Month


  • Unlimited access to our learning catalog
  • Always-on learning assistant
  • Personalized project reviews
  • Program certificates
  • Learner community

4 Months

Average time to complete a Nanodegree program

  • All the same great benefits in our month-to-month plan
  • Most cost-effective way to acquire a new set of skills
Discount applies to the first 4 months of membership, after which plans are converted to month-to-month.