I NP Completeness
1 NP Completeness I
1.1 Introduction
Can we solve all problems in polynomial time?
1.2 Complexity classes
1.2.1 Reductions
1.3 More NP-Complete problems
1.3.1 3SAT
1.4 Bibliographical Notes
3.1 Hamiltonian Cycle
3.2 Traveling Salesman Problem
3.3 Subset Sum
3.4 3 dimensional Matching (3DM)
3.6 Some other problems
4 Exercises - NP Completeness
4.1 Equivalence of optimization and decision
problems
4.2 Showing problems are NP-Complete
4.3 Solving special subcases of NP-Complete problems in
polynomial time
II Dynamic programming
5.1 Basic Idea - Partition Number
5.1.1 A Short sermon on memoization
5.2 Example -- Fibonacci numbers
5.2.1 Why, where, and when?
5.2.2 Computing Fibonacci numbers
5.3 Edit Distance
5.3.1 Shortest path in a
DAG and dynamic
programming
7.1 Greedy algorithms and approximation
algorithms
7.1.1 Alternative algorithm -- two for the price of
one
7.2 Fixed parameter tractability, approximation, and fast
exponential time algorithms (to say nothing of the dog)
7.2.1 A silly brute force algorithm for vertex
cover
7.2.2 A fixed parameter tractable algorithm
7.2.2.1 Remarks
7.3 Traveling Salesman Person
7.3.1 TSP with
the triangle inequality
7.3.1.1 A 2-approximation
7.3.1.2 A 3/2-approximation to TSP
7.4 Biographical Notes
8.1 Max Exact 3SAT
8.2 Approximation Algorithms for Set Cover
8.2.1 Guarding an Art Gallery
8.2.2 Set Cover
8.2.3 Lower bound
8.2.4 Just for fun -- weighted set
cover
8.2.4.1 Analysis
8.3 Biographical Notes
9.1 Clustering
9.1.1 The
approximation algorithm for $k$-center
clustering
9.2 Subset Sum
9.2.1 On the complexity of
eps-approximation algorithms
9.2.2 Approximating subset-sum
9.2.2.1 Bounding the running time of ApproxSubsetSum
9.2.2.2 The result
9.3 Approximate Bin Packing
9.4 Bibliographical notes
10 Exercises - Approximation Algorithms
10.1 Greedy algorithms as approximation algorithms
10.2 Approxiamtion for hard problems
IV Randomized algorithms
11.2 Sorting Nuts and Bolts
11.2.1 Running time analysis
11.2.1.1 Alternative incorrect solution
11.2.2 What are randomized algorithms?
11.3 Analyzing QuickSort
11.4 QuickSelect -- median selection in linear time
12.1 QuickSort and Treaps with High Probability
12.1.1 Proving that an element participates in small
number of rounds
12.1.2 An alternative proof of the high probability of
QuickSort
12.2 Chernoff inequality
12.2.1 Preliminaries
12.2.2 Chernoff inequality
12.2.2.1 The Chernoff Bound --- General Case
12.3 Treaps
12.3.1 Construction
12.3.2 Operations
12.3.2.1 Insertion
12.3.2.2 Deletion
12.3.2.3 Split
12.3.2.4 Meld
12.3.3 Summery
12.4 Bibliographical Notes
13.1 Min Cut
13.1.1 Problem Definition
13.1.2 Some
Definitions
13.2 The Algorithm
13.2.1 The resulting algorithm
13.2.1.1 On the art of randomly picking an edge
13.2.2 Analysis
13.2.2.1 The probability of success
13.2.2.2 Running time analysis.
13.3 A faster algorithm
13.3.1 On coloring trees and min-cut
13.4 Bibliographical Notes
16.1 Accountability
16.2 The Ford-Fulkerson Method
16.3 The Edmonds-Karp algorithm
16.4 Applications and extensions for Network
Flow
16.4.1 Maximum Bipartite Matching
16.4.2 Extension: Multiple Sources and Sinks
17.1 Edge disjoint paths
17.1.1 Edge-disjoint paths in a directed graphs
17.1.2 Edge-disjoint paths in undirected graphs
17.2 Circulations with demands
17.2.1 Circulations with demands
17.2.1.1 The algorithm for computing a circulation
17.3 Circulations with demands and lower bounds
17.4 Applications
17.4.1 Survey design
19.1 Minimum Average Cost Cycle
19.2 Potentials
19.3 Minimum cost flow
19.4 A Strongly Polynomial Time Algorithm for Min-Cost Flow
19.5 Analysis of the Algorithm
19.5.1 Reduced cost induced by a circulation
19.5.2 Bounding the number of iterations
19.6 ZZZ Bibliographical Notes
22.1 Introduction and Motivation
22.1.1 History
22.1.2 Network flow via linear programming
22.2 The Simplex
Algorithm
22.2.1 Linear program where all the variables are
positive
22.2.2 Standard form
22.2.3 Slack Form
22.2.4 The Simplex
algorithm by example
22.2.4.1 Starting somewhere
23.1 The Simplex
Algorithm in Detail
23.2 The SimplexInner
Algorithm
23.2.1 Degeneracies
23.2.2 Correctness of linear programming
23.2.3 On the ellipsoid method and interior point
methods
23.3 Duality and Linear Programming
23.3.1 Duality by Example
23.3.2 The Dual Problem
23.3.3 The Weak Duality Theorem
23.4 The strong duality theorem
23.5 Some duality examples
23.5.1 Shortest path
23.5.2 Set Cover and Packing
23.5.3 Network flow
23.6 Solving LPs without ever getting into a loop -
symbolic perturbations
23.6.1 The problem and the basic idea
23.6.2 Pivoting as a Gauss elimination step
23.6.2.1 Back to the perturbation scheme
23.6.2.2 The overall algorithm
27.1 Model of Computation
27.2 Sorting with a circuit -- a naive solution
27.2.1 Definitions
27.2.2 Sorting network based on insertion
sort
27.3 The Zero-One Principle
27.4 A bitonic sorting network
27.4.1 Merging sequence
27.5 Sorting Network
27.6 Faster sorting networks
28.1 Union-Find
28.1.1 Requirements from the data-structure
28.1.2 Amortized analysis
28.1.3 The data-structure
28.2 Analyzing the Union-Find Data-Structure
31.1 Huffman coding
31.1.1 The algorithm to build Hoffman's code
31.1.2 Analysis
31.1.3 What do we get
31.1.4 A formula for the average size of a code word
34.1 Coding: Shannon's Theorem
34.2 Proof of Shannon's theorem
34.2.1 How to encode and decode efficiently
34.2.1.1 The scheme
34.2.1.2 The proof
34.2.2 Lower bound on the message size
34.3 Bibliographical Notes
36.1 Definitions
36.2 Unweighted matching in a bipartite graph
36.3 Matchings and Alternating Paths
36.4 Maximum Weight Matchings in A Bipartite
Graph
36.4.1 Faster Algorithm
36.5 The Bellman-Ford Algorithm - A Quick Reminder
37.1 Maximum Size Matching in a Non-Bipartite Graph
37.1.1 Finding an augmenting path
37.1.2 The algorithm
37.1.2.1 Running time analysis
37.2 Maximum Weight Matching in A Non-Bipartite Graph
38.1 Sorting
38.1.1 Decision trees
38.1.2 An easier direct argument
38.2 Uniqueness
38.3 Other lower bounds
38.3.1 Algebraic tree model
38.3.2 3Sum-Hard
39.1 How many times can the minimum change?
39.2 Yet another analysis of QuickSort
39.3 Closest pair: Backward analysis in
action
39.3.1 Definitions
39.3.2 Back to the problem
39.3.3 Slow algorithm
39.3.4 Linear time algorithm
39.4 Computing a good ordering of the
vertices of a graph
39.4.1 The algorithm
39.4.2 Analysis
39.5 Computing nets
39.5.1 Basic definitions
39.5.1.1 Metric spaces{subsubsection.39.5.1.1
39.5.1.2 Nets{subsubsection.39.5.1.2
39.5.2 Computing nets quickly for a point set in
R^{d}
39.5.3 Computing an $r$-net in a sparse graph
39.5.3.1 The algorithm
39.5.3.2 Analysis
39.6 Bibliographical notes
X Exercises
40 Exercises - Prerequisites
40.1 Graph Problems
40.2 Recurrences
40.3 Counting
40.5 Probability
40.6 Basic data-structures and algorithms
40.7 General proof thingies
40.8 Miscellaneous
41 Exercises - Miscellaneous
41.1 Data structures
41.2 Divide and Conqueror
41.3 Fast Fourier Transform
41.4 Union-Find
41.5 Lower bounds
41.6 Number theory
41.7 Sorting networks
41.8 Max Cut