Introduction to Graduate Algorithms

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

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

Dynamic programming: Knapsack, and Chain Matrix Multiplication.

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

Modular Arithmetic: Fast Modular Exponentiation and Multiplicative Inverses.

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

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

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

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

Refresher Lecture about Solving Recurrences.

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

FFT and polynomial multiplication algorithms, and inverse FFT.

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

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

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

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

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

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

Max-flow: Application to Image Segmentation problem.

Max-flow: Edmonds-Karp augmenting path algorithm.

Max-flow: Generalization allowing demand constraints.

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

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

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

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

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

3-SAT Problem is NP-Complete

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

Knapsack and Subset Sum Problems are NP-Complete

Halting Problem is Undecidable