Author(s): George Kudrayvtsev
Year: 2020
Language: English
City: Atlanta
Tags: CS 6515; CS6515; algo; GA; gatech; georgia tech; CCA; computability; complexity; 6505; CS6505; CS; CSE; dynamic programming; randomized; randomised; divide and conquer; divide; conquer; D&C; DP; linear programming; NP-completeness; NP; completeness; hard; reductions; graph; tree; graphs; graph theory; greedy; approximation; approx; random; arithmetic; binary; algorithm design; algorithm analysis; design; analysis; algorithm
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
