# Class notes for graduate algorithms class

Sariel Har-Peled
Class notes in one file: here.

(Contains also the chapters missing below.
Slides for the course are here (Fall 2014).

# Class notes in separate file per chapter

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

## 2 NP Completeness II

2.1 Max-Clique How to prove that a problem X is NP-Hard
2.2 Independent Set
2.3 Vertex Cover
2.4 Graph Coloring

## 3 NP Completeness III

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 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

## 6 Dynamic programming II - The Recursion Strikes Back

6.1 Optimal search trees
6.2 Optimal Triangulations
6.3 Matrix Multiplication
6.4 Longest Ascending Subsequence
6.5 Pattern Matching

III Approximation algorithms

## 7 Approximation algorithms

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 Approximation algorithms II

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 Approximation algorithms III

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 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 Randomized Algorithms II

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 Min Cut

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

## 14 Randomized Algorithms - exercises

V Network flow

## 15 Network Flow

15.1 Network Flow
15.2 Some properties of flows and residual networks
15.3 The Ford-Fulkerson method
15.4 On maximum flows

## 16 Network Flow II - The Vengeance

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 Network Flow III - Applications

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

## 18 Network Flow IV - Applications II

18.1 Airline Scheduling
18.1.1 Modeling the problem
18.1.2 Solution
18.2 Image Segmentation
18.3 Project Selection
18.3.1 The reduction
18.4 Baseball elimination
18.4.1 Problem definition
18.4.2 Solution

## 19 Network Flow V - Min-cost flow

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

## 20 Network Flow VI - Min-Cost Flow Applications

20.1 Efficient Flow
20.2 Efficient Flow with Lower Bounds
20.3 Shortest Edge-Disjoint Paths
20.4 Covering by Cycles
20.5 Minimum weight bipartite matching
20.6 The transportation problem

## 21 Exercises - Network Flow

21.1 Network Flow
21.2 Min Cost Flow

VI Linear Programming

## 22 Linear Programming

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 Linear Programming II

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

## 24 Approximation Algorithms using Linear Programming

24.1 Weighted vertex cover
24.2 Revisiting Set Cover
24.3 Minimizing congestion

## 25 Exercises - Linear Programming

25.1 Miscellaneous
25.2 Tedious

VII Miscellaneous topics

## 26 Fast Fourier Transform

26.1 Introduction
26.2 Computing a polynomial quickly on \$n\$ values
26.2.1 Generating Collapsible Sets
26.3 Recovering the polynomial
26.4 The Convolution Theorem
26.4.1 Complex numbers -- a quick reminder

## 27 Sorting Networks

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 Union Find

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

## 29 Approximate Max Cut

29.1 Problem Statement
29.1.1 Analysis
29.2 Semi-definite programming
29.3 Bibliographical Notes

## 30 The Perceptron Algorithm

30.1 The perceptron algorithm
30.2 Learning A Circle
30.3 A Little Bit On VC Dimension
30.3.1 Examples

VIII Compression, entropy, and randomness

## 31 Huffman Coding

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

## 32 Entropy, Randomness, and Information

32.1 Entropy
32.1.1 Extracting randomness

## 33 Even more on Entropy, Randomness, and Information

33.1 Extracting randomness
33.1.1 Enumerating binary strings with \$j\$ ones
33.1.2 Extracting randomness
33.2 Bibliographical Notes

## 34 Shannon's theorem

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

## 35 Exercises - Entropy

IX Miscellaneous topics II

## 36 Matchings

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 Matchings II

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 Lower Bounds

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 Backwards analysis

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 Rd
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

## 42 Exercises - Computational Geometry

XI Homeworks/midterm/final

## 43 Fall 2014

43.1 Homeworks
43.1.1 Homework 0
43.1.2 Homework 1
43.1.3 Homework 2
43.1.4 Homework 3
43.1.5 Homework 4
43.1.6 Homework 5
43.2 Midterm
43.3 Final