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>

Free# Introduction to Graduate Algorithms

Course

Last Updated March 7, 2022

Lesson 1

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

Lesson 2

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

Lesson 3

Dynamic programming: Knapsack, and Chain Matrix Multiplication.

Lesson 4

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

Lesson 5

Modular Arithmetic: Fast Modular Exponentiation and Multiplicative Inverses.

Lesson 6

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

Lesson 7

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

Lesson 8

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

Lesson 9

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

Lesson 10

Refresher Lecture about Solving Recurrences.

Lesson 11

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

Lesson 12

FFT and polynomial multiplication algorithms, and inverse FFT.

Lesson 13

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

Lesson 14

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

Lesson 15

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

Lesson 16

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

Lesson 17

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

Lesson 18

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

Lesson 19

Max-flow: Application to Image Segmentation problem.

Lesson 20

Max-flow: Edmonds-Karp augmenting path algorithm.

Lesson 21

Max-flow: Generalization allowing demand constraints.

Lesson 22

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

Lesson 23

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

Lesson 24

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

Lesson 25

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

Lesson 26

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

3-SAT Problem is NP-Complete

Lesson 28

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

Lesson 29

Knapsack and Subset Sum Problems are NP-Complete

Lesson 30

Halting Problem is Undecidable

Instructor

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.

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

Introduction to Graduate Algorithms

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

- All the same great benefits in our month-to-month plan
- Most cost-effective way to acquire a new set of skills