Introduction to Graduate Algorithms

  • Introduction to Graduate Algorithms
    • Overview
  • DP1: FIB, LIS, LCS
    • Dynamic Programming Overview
    • Fibonacci Numbers
    • FIB1: Recursive Algorithm
    • FIB1: Exp. Running Time
    • FIB2: DP Algorithm
    • FIB2: DP Recap
    • Longest Increasing Subseq.
    • LIS: Subproblem Attempt 1
    • LIS: Recurrence Attempt 1
    • LIS: Subproblem Attempt 2
    • LIS: Recurrence Attempt 2
    • LIS: DP Algorithm
    • LIS: DP Running Time
    • LIS Recap
    • Longest Common Subsequence
    • LCS Example
    • LCS: Subproblem Attempt 1
    • LCS: Recurrence Attempt 1
    • LCS: Recurrence Problem
    • LCS: Subproblem Attempt 2
    • LCS: Recurrence Unequal Case
    • LCS: Recurrence Equal Case
    • LCS: Recurrence Equal Recap
    • LCS: Recurrence Summary
    • LCS: DP Algorithm
    • LCS: DP Table
    • LCS: Extract Sequence
    • DP1: Practice Problems
    • DP1: Practice Problem 6.1
    • DP1: Practice Solution
  • DP2: Knapsack, Chain Multiply
    • Knapsack Problem
    • Knapsack Problem Variants
    • Greedy Algorithm
    • Knapsack: No repetition
    • Knapsack: Recurrence 1
    • Knapsack: Subproblem 2
    • Knapsack: Recurrence 2
    • Knapsack: DP Pseudocode
    • Knapsack in Poly-time?
    • Knapsack Repetition
    • Knapsack2: Recurrence
    • Knapsack2: Recap
    • Knapsack2: Simpler Subproblem
    • Knapsack2: Pseudocode
    • Knapsack2: Running Time
    • Knapsack2: Traceback
    • Chain Matrix Multiply
    • Order of Operation
    • Cost for Matrix Multiply
    • General Problem
    • Graphical View
    • Chain Multiply: Prefixes
    • Chain Multiply: Substrings
    • Chain Multiply: Recurrence
    • Chain Multiply: Summary
    • Filling the Table
    • Chain Multiply: DP Pseudocode
    • DP2: Practice Problems
  • DP3: Shortest Paths
    • Shortest Paths via DP
    • Negative Weight Cycles
    • Single Source: Subproblem
    • Single Source: Recurrence
    • Single Source: Summary
    • Single Source: Pseudocode
    • Finding Negative Wt. Cycle
    • All Pairs Shortest Path
    • Naive Approach
    • All Pairs: Subproblem
    • All Pairs: Base Case
    • All Pairs: Recurrence
    • Case: i not on path
    • Case: i is on path
    • Recurrence: i is on path
    • Recurrence: Summary
    • All Pairs: Pseudocode
    • All Pairs: Running Time
    • Finding Neg. Wt. Cycle #2
    • Comparing Algorithms
    • DP3: Practice Problems
  • RA1: Modular Arithmetic
    • Randomized Algorithms
    • RSA: Lecture Overview
    • Huge Integers
    • Modular Arithmetic
    • Example Mod 3
    • Basic Fact
    • Modular Exp.: Naive
    • Modular Exp.: Fast
    • Mod Exp Algorithm
    • Multiplicative Inverse
    • Inverse: Example
    • Inverse: Existence
    • Inverse: Terminology
    • Inverse: Unique
    • Inverse: Non-existence
    • GCD: Euclid's Rule
    • GCD: Euclid's Algorithm
    • GCD: Base Case
    • GCD: Running Time
    • Computing Inverses
    • Inverses: Ext. Euclid Alg.
    • Mod. Exp. + Inverses Recap
  • RA2: RSA
    • Fermat's Little Theorem
    • Fermat's Thm.: Proof
    • Proof: Key Lemma
    • Proof: Finishing Up
    • Euler's Theorem
    • Euler's Totient Quiz
    • Euler's Thm. for N=pq
    • RSA Alg. Idea
    • Crypto Setting
    • RSA Protocol: Keys
    • RSA Protocol: Encrypting
    • RSA: Potential Pitfalls
    • Recap of RSA
    • Recap of RSA #2
    • RSA Exercise
    • Random Primes
    • Primality: Fermat's Test
    • Trivial Witness
    • Non-Trivial Witness
    • No Non-Trivial Witnesses?
    • Primality: Many Witnesses
    • Simple Primality Alg.
    • Primality Alg. Analysis
    • Boosting Success
    • Addendum: Pseudoprimes
  • RA3: Bloom Filters
    • Hashing Outline
    • Balls Into Bins
    • Probability Quiz
    • Analysis Setup
    • Max Load Quiz
    • Max Load Analysis
    • Best of Two Scheme
    • Power of Two Choices
    • Hashing Setup
    • Chain Hashing
    • Power of Two Hashing
    • Lecture Outline
    • Bloom Filters Motivation
    • Operations
    • Bloom Filters
    • Robust Scheme
    • Correctness
    • Analysis Setup
    • False Positive Probability
    • Optimal k
    • Looking at False Positive Rate
    • Summary
  • DC1: Fast Integer Multiplication
    • Divide and Conquer
    • D&C: Overview
    • Multiplying Complex #'s
    • Improved Approach
    • D&C: Naive Approach
    • Naive: Recursive idea
    • Naive: Pseudocode
    • Naive: Running Time
    • D&C: Improved Approach
    • Improved: Pseudocode
    • Improved: Running Time
    • Improved: Summary
  • DC2: Linear-Time Median
    • Median Problem
    • QuickSort
    • Search Example
    • QuickSelect
    • Simple Recurrence
    • D&C: High-level idea
    • Goal: Good Pivot
    • Random Pivot
    • D&C: Recursive Pivot
    • Representative Sample
    • Recursive Rep. Sample
    • Median: Pseudocode
    • Median: Running Time
    • Correctness
    • HW: Groups of 3? 7?
  • DC3: Solving Recurrences
    • Solving Recurrences
    • Example 1
    • Expanding out
    • Geometric Series
    • Manipulating Polynomials
    • Example 2
    • General Recurrence
  • DC4: FFT - Part 1
    • Polynomial Multiplication
    • Quiz: PM: Example
    • PM: General Problem
    • Convolution Applications
    • Polynomials Basics
    • MP: Values
    • FFT: Opposites
    • FFT: Splitting A(x)
    • FFT: Even & Odd
    • FFT: Recursion
    • FFT: Summary
    • FFT: Recursive Problem
    • Review: Complex Numbers
    • Multiplying in Polar
    • Complex Roots
    • Roots: Graphical View
    • Roots: Notation
    • Roots: Examples
    • Complex roots practice
    • Key Property: Opposites
    • Key Property: Squares
  • DC5: FFT - Part 2
    • FFT: High-Level
    • FFT: Pseudocode
    • FFT: Core
    • FFT: Concise
    • FFT: Running Time
    • Poly Mult. using FFT
    • Linear Algebra View
    • LA View of FFT
    • LA for Inverse FFT
    • Inverse FFT
    • Inverse FFT via FFT
    • Quiz: Inverses
    • Quiz: Sum of Roots
    • Proof of Claim
    • Proof of Lemma
    • Diagonal Entries
    • Off-Diagonal Entries
    • Back to Poly Mult.
  • GR1: Strongly Connected Components
    • Graph Algorithms
    • Outline
    • Undirected Graphs
    • Exploring Undirected Graphs
    • DFS: Paths
    • DFS on Directed Graphs
    • Directed DFS: Example
    • Types of Edges
    • Cycles
    • Toplogical Sorting
    • Topological Ordering Quiz
    • DAG Structure
    • Outline Review
    • Connectivity in Directed Graphs
    • SCC Quiz
    • Graph of SCC
    • SCC Algorithm Idea
    • Vertex in sink SCC
    • Finding sink SCC
    • SCC Example
    • SCC Algorithm
    • Simpler Claim
    • Proof of Key SCC Fact
    • BFS/Dijkstra's
  • GR2: 2-Satisfiability
    • SAT Notation
    • SAT Problem
    • SAT Problem Quiz
    • k-SAT
    • Simplifying Input
    • Graph of Implications
    • Graph Properties
    • SCC's
    • Algorithm Idea
    • Algorithm Idea 2
    • 2SAT Algorithm
    • Proof of Key Fact
    • Rest of Proof
    • Proof of Claim
  • GR3: Minimum Spanning Tree
    • Greedy Approach
    • MST Problem
    • Tree Properties
    • Greedy Approach for MST
    • Kruskal's Algorithm
    • Kruskal's Analysis
    • Kruskal's Correctness
    • Cuts
    • Cut Property
    • Cut Property: Kruskal's
    • Proof Outline
    • Constructing T
    • T is a Tree
    • T is a MST
    • Prim's Algorithm
  • GR4: Markov Chains and PageRank
    • PageRank Lecture Outline
    • Example Markov Chain
    • General Markov Chain
    • 2-Step Transitions
    • k-Step Transitions
    • Big k for 6210 Example
    • Infinite Time
    • Linear Algebra View
    • Stationary Distribution
    • Bipartite Markov Chain
    • Multiple SCC's
    • Ergodic MC
    • What is Pi?
    • PageRank
    • Webgraph
    • First Idea
    • Problem 1
    • Second Idea
    • Problem 2
    • Rank Definition
    • Random Walk
    • Stationary Distribution
    • Problems
    • Random Surfer
    • Transition Matrix
    • Sink Nodes
    • Ergodic
    • Finding Pi
  • MF1: Ford-Fulkerson Algorithm
    • Max-Flow
    • Lecture Outline
    • Problem Setup
    • Problem Formulation
    • Max-Flow Problem
    • Max-Flow Goal
    • Quiz: Max-Flow Example
    • Cycles are OK
    • Anti-parallel Edges
    • Toy Example
    • Simple Algorithm
    • Backward Edges
    • Residual Network
    • Ford-Fulkerson Algorithm
    • Running Time
    • Time per Round
    • Discussion
  • MF2: Max-Flow Min-Cut
    • Lecture Outline
    • Recap: Ford-Fulkerson
    • Quiz: Verifying Max-Flow
    • Min-Cut Problem
    • Problem Formulation
    • Max-Flow = Min st-Cut
    • Max-Flow Min st-Cut
    • Proof of Claim
    • Finishing Off
    • Reverse Inequality
    • Proof of Claim
    • Properties of Cut
    • Completing the Proof
  • MF3: Image Segmentation
    • Image Segmentation
    • Formulation
    • Parameters
    • Example
    • Partition
    • Min-Cut
    • Reformulation
    • New Weights
    • New Problem
    • Flow Network
    • Foreground
    • Background
    • Cuts
    • Solution
  • MF4: Edmonds-Karp Algorithm
    • Max-Flow Min-Cut Algorithms
    • Ford Fulkerson Algorithm
    • Edmonds-Karp Algorithm
    • Proof Outline
    • BFS Properties
    • BFS Example
    • BFS Properties - Part 2
    • Add/Delete Edges
    • Conclusion
    • Proof of Claim
    • Delete/Add Effect
    • Finishing Off
  • MF5: Max-Flow Generalization
    • Max-Flow with Demands
    • Feasible Flow Example
    • Reduction Overview
    • Reduction: Vertices
    • Original Edges
    • New Edges
    • One More Edge
    • Saturating Flows
    • Saturating Feasible
    • f is Valid
    • Feasible Saturating
    • f is Valid
    • f Constraints
    • Max Feasible Flow
    • Reduction Example
  • LP1: Linear Programming
    • Linear Programming
    • Lecture Outline
    • Max-Flow as LP
    • Simple 2D Example
    • 2D LP Formulation
    • 2D LP Recap
    • 2D Geometric View
    • Optimum
    • Key Issues
    • 3D Example
    • 3D LP Formulation
    • 3D Geometric View
    • Standard Form
    • Linear Algebra View
    • Converting to Standard Form
    • General Geometric View
    • Vertices
    • LP Algorithms
    • Simplex Algorithm
    • Simplex Example
  • LP2: Geometry
    • LP Geometry
    • LP Optimum
    • Infeasible Example
    • Unbounded Example
    • Unbounded to Bounded
    • LP Optimum - Part 2
    • Infeasible?
  • LP3: Duality
    • LP Duality
    • Example
    • Upper Bound
    • Dual LP
    • Dual LP Example
    • General Form
    • Dual of Dual
    • Quiz: Dual LP
    • Quiz: Dual LP Constraints
    • Weak Duality
    • Matching Values
    • Unbounded LP
    • Check Unbounded
    • Weak Duality - Part 2
    • Strong Duality
  • LP4: Max-SAT Approximation
    • Max-SAT
    • Approximate Max-SAT
    • Outline
    • Simple Scheme
    • Expectation
    • Analysis
    • Finishing Off
    • Ek-SAT
    • Integer Programming
    • NP-Hard
    • Clauses
    • Another Clause
    • Reduction
    • LP Relaxation
    • Rounding
    • Expectation
    • Lemma
    • AM-GM
    • Analysis
    • Calculus
    • Finishing Up
    • Summary
    • Comparison
    • Best of 2
  • NP1: Definitions
    • NP: Overview
    • NP1: Lecture Outline
    • Complexity Classes
    • Comparing P and NP
    • Search Problems
    • SAT Problem
    • SAT Example
    • SAT in NP
    • Colorings in NP
    • MST
    • MST in NP
    • MST in P
    • Knapsack Problem
    • Knapsack Complexity
    • Solution: Knapsack Complexity
    • Knapsack Search
    • Knapsack Search in NP
    • NP acronym for?
    • P vs NP
    • NP-Completeness
    • SAT is NP-Complete
    • Reductions
    • How to do a Reduction
    • More on Reductions
    • NP-Completeness Proof
    • Simpler Proof Approach
    • Practice Problems
  • NP2: 3SAT
    • NP-Completeness
    • 3SAT
    • Proof Outline
    • 3SAT in NP
    • SAT 3SAT
    • Example
    • Claim: Forward
    • Claim: Reverse
    • Quiz: 5-SAT 3-SAT
    • Big Clauses
    • General Claim: Forward
    • General Claim: Reverse
    • SAT 3SAT
    • Correctness
    • Satisfying Assignment
    • Practice Problems
  • NP3: Graph Problems
    • Lecture Outline
    • Independent Set
    • Quiz: Max Independent Set
    • Search Version
    • Proof Outline
    • 3SAT IS
    • Clause Edges
    • Variable Edges
    • Example
    • Correctness
    • Reverse Implication
    • NP-hard
    • Lecture Outline II
    • Clique
    • Clique: Search Version
    • Clique: Proof Outline
    • IS Clique Idea
    • IS Clique
    • Lecture Outline III
    • Vertex Cover
    • VC: Search Version
    • VC: Proof Outline
    • VC: Reduction Idea
    • Forward Implication
    • Reverse Implication
    • IS VC
    • IS VC Correctness
    • Practice Problems
  • NP4: Knapsack
    • Lecture Outline
    • Subset Sum
    • Subset-Sum in P?
    • Subset-Sum NP-Complete
    • 3SAT Subset-Sum: Input
    • 3SAT Subset-Sum: Variables
    • 3SAT Subset-Sum: Example
    • 3SAT Subset-Sum: Clauses
    • 3SAT Subset-Sum: Buffers
    • 3SAT Subset-Sum: Correctness
    • Proof: Satisfying Assignment
    • Reverse Implication
    • Knapsack is NP-complete
  • NP5: Halting Problem
    • Undecidability
    • Halting Problem
    • HP: Example
    • HP: Undecidable
    • HP: Paradox
    • HP: What's Harmful?
    • HP: Paradox derived