Free

Course

Last Updated March 7, 2022

## Course Lessons

Lesson 1

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

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

Instructor

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