Algorithms, or the Unofficial Guide to the Georgia Institute of Technology's CS6515: Graduate Algorithms

Description

Contents I Notes Dynamic Programming Fibbing Our Way Along… Recursive Relations Longest Increasing Subsequence Breaking Down Subproblems Algorithm & Runtime Analysis Longest Common Subsequence Step 1: Identify Subproblems Step 2: Find the Recurrence Algorithm & Runtime Analysis Knapsack Greedy Algorithm Optimal Algorithm Knapsack With Repetition Simple Extension Optimal Solution Matrix Multiplication Subproblem Formulation Recurrence Relation Divide & Conquer An Exercise in D&C: Multiplication Another Exercise in D&C: Median-Finding Solving Recurrence Relations Example 1: Integer Multiplication Example 2: Better Integer Multiplication General Form Fast Fourier Transform Graphs Common Algorithms Depth-First Search Breadth-First Search Shortest Paths From One Vertex: Bellman-Ford From All Vertices: Floyd-Warshall Connected Components Undirected Graphs Directed Graphs Acyclic Digraphs Strongly-Connected Components Finding SCCs Satisfiability Solving 2-SAT Problems Minimum Spanning Trees Greedy Approach: Kruskal's Algorithm Graph Cuts Prim's Algorithm Flow Ford-Fulkerson Algorithm Edmonds-Karp Algorithm Variant: Flow with Demands Minimum Cut Max-Flow = Min-Cut Theorem Application: Image Segmentation Cryptography Modular Arithmetic Modular Exponentiation Inverses Fermat's Little Theorem Euler's Totient Function RSA Algorithm Protocol Limitations Generating Primes Primality Linear Programming 2D Walkthrough Key Issues Generalization Standard Form Example: Max-Flow as Linear Programming Algorithm Overview Simplex Algorithm Invalid LPs Duality Max SAT Simple Scheme Integer Linear Programming ILP is np-Hard Computational Complexity Search Problems Example: SAT Example: k-Coloring Problem Example: MSTs Example: Knapsack Differentiating Complexities Reductions 3SAT from SAT Independent Sets Cliques Vertex Cover Subset Sum Summary Undecidability II Additional Assignments Homework #0 Problem 1: From Algorithms, Ch. 0 Problem 2: Big-Ordering Homework #1 Compare Growth Rates Geometric Growth Recurrence Relations Divide & Conquer (DPV Ch. 2) Reductions (DPV Ch. 8) III Exam Quick Reference Exam 1 Exam 2 Exam 3 Index of Terms