Algorithms

Preface
Contents
I NP Completeness
NP Completeness I
Introduction
Complexity classes
Reductions
More NP-Complete problems
3SAT
Bibliographical Notes
NP Completeness II
Max-Clique
Independent Set
Vertex Cover
Graph Coloring
NP Completeness III
Hamiltonian Cycle
Traveling Salesman Problem
Subset Sum
3 dimensional Matching (3DM)
Partition
Some other problems
II Dynamic programming
Dynamic programming
Basic Idea - Partition Number
A Short sermon on memoization
Example – Fibonacci numbers
Why, where, and when?
Computing Fibonacci numbers
Edit Distance
Shortest path in a DAG and dynamic programming
Dynamic programming II - The Recursion Strikes Back
Optimal search trees
Optimal Triangulations
Matrix Multiplication
Longest Ascending Subsequence
Pattern Matching
Slightly faster TSP algorithm via dynamic programming
III Approximation algorithms
Approximation algorithms
Greedy algorithms and approximation algorithms
Alternative algorithm – two for the price of one
Fixed parameter tractability, approximation, and fast exponential time algorithms (to say nothing of the dog)
A silly brute force algorithm for vertex cover
A fixed parameter tractable algorithm
Remarks
Approximating maximum matching
Graph diameter
Traveling Salesman Person
TSP with the triangle inequality
A 2-approximation
A 3/2-approximation to TSP-Min
Biographical Notes
Approximation algorithms II
Max Exact 3SAT
Approximation Algorithms for Set Cover
Guarding an Art Gallery
Set Cover
Lower bound
Just for fun – weighted set cover
Analysis
Biographical Notes
Approximation algorithms III
Clustering
The approximation algorithm for k-center clustering
Subset Sum
On the complexity of -approximation algorithms
Approximating subset-sum
Bounding the running time of RedVioletApproxSubsetSum
The result
Approximate Bin Packing
Bibliographical notes
IV Randomized algorithms
Randomized Algorithms
Some Probability
Sorting Nuts and Bolts
Running time analysis
Alternative incorrect solution
What are randomized algorithms?
Analyzing QuickSort
RedVioletQuickSelect – median selection in linear time
Randomized Algorithms II
QuickSort and Treaps with High Probability
Proving that an element participates in small number of rounds
An alternative proof of the high probability of RedVioletQuickSort
Chernoff inequality
Preliminaries
Chernoff inequality
The Chernoff Bound — General Case
Treaps
Construction
Operations
Insertion
Deletion
Split
Meld
Summery
Bibliographical Notes
Hashing
Introduction
Universal Hashing
How to build a 2-universal family
On working modulo prime
Constructing a family of 2-universal hash functions
Analysis
Explanation via pictures
Perfect hashing
Some easy calculations
Construction of perfect hashing
Analysis
Bloom filters
Bibliographical notes
Min Cut
Branching processes – Galton-Watson Process
The problem
On coloring trees
Min Cut
Problem Definition
Some Definitions
The Algorithm
Analysis
The probability of success
Running time analysis.
A faster algorithm
Bibliographical Notes
V Network flow
Network Flow
Network Flow
Some properties of flows and residual networks
The Ford-Fulkerson method
On maximum flows
Network Flow II - The Vengeance
Accountability
The Ford-Fulkerson Method
The Edmonds-Karp algorithm
Applications and extensions for Network Flow
Maximum Bipartite Matching
Extension: Multiple Sources and Sinks
Network Flow III - Applications
Edge disjoint paths
Edge-disjoint paths in a directed graphs
Edge-disjoint paths in undirected graphs
Circulations with demands
Circulations with demands
The algorithm for computing a circulation
Circulations with demands and lower bounds
Applications
Survey design
Network Flow IV - Applications II
Airline Scheduling
Modeling the problem
Solution
Image Segmentation
Project Selection
The reduction
Baseball elimination
Problem definition
Solution
A compact proof of a team being eliminated
Network Flow V - Min-cost flow
Minimum Average Cost Cycle
Potentials
Minimum cost flow
Strongly Polynomial Time Algorithm for Min-Cost Flow
Analysis of the Algorithm
Reduced cost induced by a circulation
Bounding the number of iterations
Bibliographical Notes
Network Flow VI - Min-Cost Flow Applications
Efficient Flow
Efficient Flow with Lower Bounds
Shortest Edge-Disjoint Paths
Covering by Cycles
Minimum weight bipartite matching
The transportation problem
VI Linear Programming
Linear Programming in Low Dimensions
Some geometry first
Linear programming
A solution and how to verify it
Low-dimensional linear programming
An algorithm for a restricted case
Running time analysis
The algorithm for the general case
Linear Programming
Introduction and Motivation
History
Network flow via linear programming
The Simplex Algorithm
Linear program where all the variables are positive
Standard form
Slack Form
The Simplex algorithm by example
Starting somewhere
Linear Programming II
The Simplex Algorithm in Detail
The SimplexInner Algorithm
Degeneracies
Correctness of linear programming
On the ellipsoid method and interior point methods
Duality and Linear Programming
Duality by Example
The Dual Problem
The Weak Duality Theorem
The strong duality theorem
Some duality examples
Shortest path
Set Cover and Packing
Network flow
Solving LPs without ever getting into a loop - symbolic perturbations
The problem and the basic idea
Pivoting as a Gauss elimination step
Back to the perturbation scheme
The overall algorithm
Approximation Algorithms using Linear Programming
Weighted vertex cover
Revisiting Set Cover
Minimizing congestion
VII Miscellaneous topics
Fast Fourier Transform
Introduction
Computing a polynomial quickly on n values
Generating Collapsible Sets
Recovering the polynomial
The Convolution Theorem
Complex numbers – a quick reminder
Sorting Networks
Model of Computation
Sorting with a circuit – a naive solution
Definitions
Sorting network based on insertion sort
The Zero-One Principle
A bitonic sorting network
Merging sequence
Sorting Network
Faster sorting networks
Union Find
Union-Find
Requirements from the data-structure
Amortized analysis
The data-structure
Analyzing the Union-Find Data-Structure
Approximate Max Cut
Problem Statement
Analysis
Semi-definite programming
Bibliographical Notes
The Perceptron Algorithm
The RedVioletperceptron algorithm
Learning A Circle
A Little Bit On VC Dimension
Examples
VIII Compression, entropy, and randomness
Huffman Coding
Huffman coding
The algorithm to build Hoffman's code
Analysis
What do we get
A formula for the average size of a code word
Bibliographical notes
Entropy, Randomness, and Information
Entropy
Extracting randomness
Even more on Entropy, Randomness, and Information
Extracting randomness
Enumerating binary strings with j ones
Extracting randomness
Bibliographical Notes
Shannon's theorem
Coding: Shannon's Theorem
Intuition behind Shanon's theorem
What is wrong with the above?
Proof of Shannon's theorem
How to encode and decode efficiently
The scheme
The proof
Lower bound on the message size
Bibliographical Notes
IX Miscellaneous topics II
Matchings
Definitions and basic properties
Definitions
Matchings and alternating paths
Unweighted matching in bipartite graph
The slow algorithm; RedVioletalgSlowMatch
The Hopcroft-Karp algorithm
Some more structural observations
Improved algorithm
Extracting many augmenting paths: RedVioletalgExtManyPaths
The result
Bibliographical notes
Matchings II
Maximum weight matchings in a bipartite graph
On the structure of the problem
Maximum Weight Matchings in a bipartite Graph
Building the residual graph
The algorithm
Faster Algorithm
The Bellman-Ford algorithm - a quick reminder
Maximum size matching in a non-bipartite graph
Finding an augmenting path
The algorithm
Running time analysis
Maximum weight matching in a non-bipartite graph
Lower Bounds
Sorting
Decision trees
An easier direct argument
Uniqueness
Other lower bounds
Algebraic tree model
3Sum-Hard
Backwards analysis
How many times can the minimum change?
Yet another analysis of RedVioletQuickSort
Closest pair: Backward analysis in action
Definitions
Back to the problem
Slow algorithm
Linear time algorithm
Computing a good ordering of the vertices of a graph
The algorithm
Analysis
Computing nets
Basic definitions
Metric spaces
Nets
Computing nets quickly for a point set in Rd
Computing an r-net in a sparse graph
The algorithm
Analysis
Bibliographical notes
Linear time algorithms
The lowest point above a set of lines
Bibliographical notes
Streaming
How to sample a stream
Sampling and median selection
A median selection with few comparisons
Big data and the streaming model
Heavy hitters
Chernoff inequality
X Exercises
Exercises - Prerequisites
Graph Problems
Recurrences
Counting
O notation and friends
Probability
Basic data-structures and algorithms
General proof thingies
Miscellaneous
Exercises - NP Completeness
Equivalence of optimization and decision problems
Showing problems are NP-Complete
Solving special subcases of NP-Complete problems in polynomial time
Exercises - Network Flow
Network Flow
The good, the bad, and the middle.
Ad hoc networks
Minimum Flow
Prove infeasibility.
Cellphones and services.
Follow the stars
Flooding
Capacitation, yeh, yeh, yeh
Fast Friends
Even More Capacitation
Matrices
Unique Cut
Transitivity
Census Rounding
Edge Connectivity
Maximum Flow By Scaling
Perfect Matching
Number of augmenting paths
Minimum Cut Festival
Independence Matrix
Scalar Flow Product
Go to school!
The Hopcroft-Karp Bipartite Matching Algorithm
Min Cost Flow
Streaming TV.
Transportation Problem.
Edge Connectivity
Perfect Matching
Max flow by augmenting
And now for something completely different.
Minimum Cut
Exercises - Miscellaneous
Data structures
Divide and Conqueror
Fast Fourier Transform
Union-Find
Lower bounds
Number theory
Sorting networks
Max Cut
Exercises - Approximation Algorithms
Greedy algorithms as approximation algorithms
Greedy algorithm does not work for TSP with the triangle inequality.
Greedy algorithm does not work for VertexCover.
Greedy algorithm does not work for independent set.
Greedy algorithm does not work for coloring. Really.
Greedy coloring does not work even if you do it in the right order.
Approximation for hard problems
Even More on Vertex Cover
Maximum Clique
Pack these squares.
Smallest Interval
Rectangles are Forever.
Graph coloring revisited
Randomized Algorithms
Randomized algorithms
Find kth smallest number.
Minimum Cut Festival
Adapt min-cut
Majority tree
Hashing to Victory
Sorting Random Numbers
Exercises - Linear Programming
Miscellaneous
Slack form
Tedious
Tedious Computations
Linear Programming for a Graph
Linear programming
Distinguishing between probablities
Strong duality.
Exercises - Computational Geometry
Misc
Robot Navigation
Point-Location
Convexity revisited.
Nearest Neighbor
Exercises - Entropy
Compress a sequence.
Arithmetic coding
Computing entropy.
When is entropy maximized?
Condition entropy.
Improved randomness extraction.
Kraft inequality.
XI Homeworks/midterm/final
Fall 2001
Homeworks
Homework 0
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Midterm
Final
Spring 2002
Fall 2002
Spring 2003
Homeworks
Homework 0
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Midterm 1
Midterm 2
Final
Fall 2003
Spring 2005
Spring 2006
Fall 2007
Fall 2009
Spring 2011
Fall 2011
Fall 2012
Fall 2013
Spring 2013: CS 473: Fundamental algorithms
Homeworks
Homework 0
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Midterm 1
Midterm 2
Final
Fall 2014: CS 573 – Graduate algorithms
Homeworks
Homework 0
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Midterm
Final
Fall 2015: CS 473 – Theory II
Homeworks
Homework 0
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Homework 11
Midterm
Final
Fall 2018: CS 473 Algorithms
Homeworks
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Homework 10
Homework 11
Midterm I
Midterm II
Final
Bibliography
Index