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>
Course
Last Updated March 7, 2022
No experience required
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