Design and Analysis of Algorithms
Contents
- Minimum Spanning Tree
- Greedy Idea 1: Kruskal’s algorithm
- Greedy Idea 2: Prim’s Algorithm
- Other algorithms
- Union-Find data structure
- More Greedy Problems
- Needle in Haystack
- Matroids
- Task Scheduling
- Huffman Codes
- Shannon’s source coding theorem
- Split-array largest sum
- Minimum fractional ST
- Master Theorem
- Closest Point
- Fast Multiplication
- Convolution
- Convolution Theorem
- Longest path on a DAG
- Knapsack Problem
- General observation
- Knapsack with unlimited items
- Knapsack with limited items
- 2D Knapsack
- Summary
Greedy Algorithms
Minimum Spanning Tree
Consider a graph describe by and (positive weights). A spanning tree of a graph is defined as an edge set such that is a tree. A minimum spanning tree is such that is minimized.
For a graph with vertices, there are spanning trees for a complete graph (Cayley’s formula).
How do we calculate the number of spanning trees for a general graph? Kirchoff’s theorem states the following -
- Let be the adjacency matrix of , and let be the diagonal matrix with .
- Define the graph Laplacian as .
- Then, the number of spanning trees is the determinant of any by principal submatrix of (obtained by removing the same row and column).
Notice how any sub-matrix yields the same value!
Greedy Idea 1: Kruskal’s algorithm
- Sort all the edges with their weights
- Pick edges as long as they don’t form a cycle
Does this work? If it does, how do we prove it?
Firstly, why is it a greedy idea? At each point of the algorithm, we select the current greedy edge (a local minimum) to obtain the minimum spanning tree (a global optimum).
-
The cut property - Let such that and are non-empty. If is an edge across and with the minimum cost, then there always exists a minimum spanning tree with .
Proof. Exchange argument. If an MST omits , its tree path between the endpoints of contains an edge across and . Replace with ; since has minimum cost across the cut, the result is also an MST.
Shouldn’t this argument be more delicate? Why is there a single edge from S to V - S?
Essentially, the exchange argument argues replacing a part of the solution improves the solution but does not worsen it.
-
The time complexity of the algorithm comes out to be . The second term in the expression comes from union-find data structures.
-
Correctness of the algorithm - We shall prove this via induction.
- Induction hypothesis - The edges selected in the th round of Kruskal’s algorithm can form an MST along with a subset of edges from the remaining edges.
- Base statement - True for
- Induction step - Cut property
-
Union-find data structure - A data structure that supports
- Merging elements of two sets into a single set -
union(x, y) - Checking whether two elements are in the same set -
find(x)
efficiently. The amortized time complexity for these operations is where for of the order . As a result, can be regarded as a constant for practical purposes.
In our case, the elements are edges and sets represent connected components.
- Merging elements of two sets into a single set -
Greedy Idea 2: Prim’s Algorithm
Start with any node and expand with the smallest edge connecting to the remaining set of edges. Note that this is different from Kruskal’s algorithm where we sort all the edges and create individual connected components that eventually merge together.
The proof for Prim’s algorithm is very similar to that of Kruskal’s. The time complexity is similar to Djikstra’s algorithm without a data structure. We can maintain a priority queue to maintain all edges that come from to reduce the time-complexity to (without decrease-key). With decrease key and a binary heap, the complexity becomes . Furthermore, with decrease key and a Fibonacci heap, the complexity reduces to .
Other algorithms
- Reverse deletion - For every cycle in the original graph and the edge with the maximum cost, there always exists an MST without . Until there are no cycles in the graph, find a cycle and delete the edge with a maximum cost. Note that this algorithm has a higher time complexity since we try and find a cycle for each iteration of the algorithm. How do we implement this?
Union-Find data structure
The idea is to maintain trees with pointers to merge and find elements. The main complication comes while merging the individual sets.
-
Merging by size (consuming smaller ones by larger sets) - The complexity of merging sets of size , times takes
-
To optimize this further, we merge by rank (generalizing the previous approach where rank was simply the size of the set). We add another trick to reduce the amortized time complexity.
- Path compression - When
find(x)is called, attach the found elements along the path directly to the root to reduce the path size.
The time complexity then becomes where is the minimum such that .
- Path compression - When
More Greedy Problems related to MST
-clustering
A maximum spacing for -clustering of is defined as
- An edge set such that has exactly connected components
- The spacing is then for in different connected components
- The goal is to maximize the spacing
This problem can be solved again with Kruskal’s algotihm to find -connected components - perform the union operation for times. Why is this correct? WE can show this using a contradiction.
- Consider two nodes that lie in the same connected component in the result obtained by Kruskal’s (with spacing ). Let them be in different connected components in the optimal solution (with spacing ). Then,
Second MST
A second MST is essentially the spanning tree with the second lowest edge summation cost. How do we find this tree?
- Find an MST with weight
- For every edge not in the MST, if adding yields a cycle in the graph; then remove the largest edge other than in the cycle to obtain the second MST
- The cost of the tree would be
The time complexity of this algorithm is and can be improved to with better data-structures and divide-and-conquer.
Lemma. The second MST only differs by one edge from the MST. Multiple MSTs? Proof. Can be shown using contradiction. The idea is that one can move from one spanning tree to another with local changes in the trees. The argument is that you can replace the edges in the second MST with the edges in the MST to obtain a tree with a lower cost. This process can be repeated until there is only one edge that is different from an MST and replacing that would cause the tree to become the MST.
More Greedy Problems
Needle in Haystack
Given two strings , decide whether there is a subsequence (need not be contiguous) in that matches with . A naive greedy algorithm is depicted as follows -
i, j = 0, 0
while True:
if j == len(t):
break
if s[i] == t[j]:
j += 1 # s[i] is matched with t[j]
else:
i += 1
On first glance, it looks as if this is a very intuitive algorithm. However, there are more intricate details and the proof makes these clearer. The proof relies on the Exchange argument. If there exists a subsequence in matching (). If is the first index that , then also matches . This way we can find a set of indices through the greedy algorithm that gives the correct answer.
In general, greedy algorithms can be proven in two general ways
- Consider any iteration of the algorithm and show that the decision made by the greedy algorithm is the best and conclude using induction
- Exchange argument: Pick an optimal solution and gradually change it to the solution produced by the greedy algorithm showing that the optimality is not affected.
Matroids
A finite matroid consists of where
- is a finite set (called the ground set). For example, is the set of all edges in the graph
- is a collection of subsets of (called the independent set). For example, consists all subsets of of such that all the edges in form a forest.
should satisfy the following properties -
- Null set should be in -
- if and then
- If , then , such that
Isn’t 2 inclusive of 1 and 3?
How does this data structure help us? Suppose we have a graph with weights . Then, design an algorithm to find an independent set that maximizes . Consider the following algorithm -
- Sort in decreasing order of weights
- Let . Add to if does not add cycles in
This algorithm is very similar to the reverse deletion algorithm and has a time complexity .
Lemma. Let have the maximum cost m then there always exists an IS with maximum weight containing .
The proof is very similar to what we have shown with MSTs. This example can be applied to MSTs, and it demonstrates how Matroids can be useful for greedy algorithms.
Task Scheduling
Given jobs each with time to finish and deadlines . Consider that there is a single resource solving tasks sequentially from time , and a job has to completely finished before moving onto the next one.
Suppose in a scheduling algorithm, job finishes at time , then the lateness is defined as . The goal is find an algorithm that minimizes the maximum lateness .
Let us consider a simple case. Suppose there are two jobs with . Note that any scheduling algorithm should not have any idle time between jobs. Why so? If there is idle time, you can always do a job earlier to reduce the lateness. Furthermore, a scheduling algorithm should not have an inversion. That is, if job 1 has deadline earlier than job 2, then it is always optimal to perform job 1 before job 2. This claim can be easily proved using the exchange argument.
Algorithm
Sort all jobs according to the increasing order of these deadlines , then complete each job without any idle time.
Proof. Generalize the previous two observations to jobs.
Huffman Codes
How do we encode an alphabet in binaries to have no ambiguities.
Prefix codes
A prefix code for an alphabet is a function , such that for distinct , is not a prefix of .
It can be shown that a prefix code gives unique decoding.
How do we design an encoding that is most efficient? Let us define efficiency. For every letter in , let its frequency be . Let be a prefix code and for every letter , let is the number of bits. The goal is to find a prefix code that minimizes the expected number of bits when encoding under the frequency .
It is beneficial to represent prefix codes as a binary tree. Each node has two children: 0 and 1. The paths from the root to other nodes in the tree represent the binary encodings.
- For prefix codes, no node of a symbol is an ancestor of node of another symbol (from the alphabet).
- Another observation is that any optimal prefix code is a full tree (every inner node has two children) - if anode has a single chide, the parent node can itself be used for the symbol deleting the leaf node making the encoding more efficient.
- There is an optimal tree (prefix code) such that two lower frequent letters are siblings, and are as deep as possible in the tree. This claim can be proved easily with the exchange argument.
With these observations, consider the following algorithm
-
Initialize each letter as a node and label it with
-
Put all nodes into a min-heap (according to the frequency)
-
While min-heap has atleast two elements
-
Pop out the two smallest elements (corresponds to two trees)
-
Combine them to a single tree
-
Push it into the heap, label with
-
This is the Huffman’s coding algorithm which has a time complexity of .
Shannon’s source coding theorem
Let be an alphabet with frequency . The entropy of the alphabet is defined as
The Shannon’s source coding theorem then states that you cannot send a letter from with frequenct , with expected bits less than . Huffmman’s encoding gives a solution with expected bits at most .
Important point. One can suggest to increase the alphabet size with dummy symbols to virtually reduce the value of significantly. However, this introduces complexity for encoding algorithms. Therefore, there is a tradeoff with space occupied by encoding and the time for encoding.
Even with augmented alphabet, the size of the encoding does not change for the original symbols in the alphabet?
Binary Search X Greedy Algorithms
The basic binary search takes advantage of the monotone structure in arrays to identify elements with certain properties. Any binary search problem can be converted to the following simpler version: For an array that has binary elements with all zeros occurring before all ones, find the index of the first occuring .
The binary search algorithm can be simply proved using induction.
Let us consider an example - Ternary search. Given an array that is first strictly increasing and then strictly decreasing, dind the largest element. The array is constructed as
Split-array largest sum
Minimum fractional ST
Given an undirected graph and each edge has two costs both of which are positive, find a spanning tree that minimizes
How is this related to binary search? Firstly, we will convert this problem to a decisional version - Given an undirected graph and a real number , decide whether there exists a spanning tree such that .
This is equivalent to find a spanning tree such that . Construct a new graph with the weights . The reduction is easy to follow.
How do we find the monotone structure for binary search? If the decision problem is satisfiable, then is also satisfiable for any . Conceptually, assume a function (with continuous index) such that where is an upper bound. iuf and only if is satisifiable, and is monotone.
Divide and Conquer
Master Theorem
Consider an algorithm that has the following relationship for running time complexity -
then .
Closest Point
Fast Multiplication
Suppose we have two integers in binary . The goal is to compute , where for and . The naïve brute force approach takes to compute the answer.
This question is related to matrix multiplication as well. The naïve algorithm takes .
Algorithm 1
We segment as follows -
-
where and
-
similarly.
Then, . The strategy then is to do a divide and conquer on these halves to get the final answer.
The time complexity is then . This is essentially that does not give any improvement.
This can be optimized further -
The number of multiplications is reduced to 3, giving and hence .
This algorithm can be extended to matrix multiplications as well.
The naïve algorithm shown above is still . Strassen’s algorithm reduces the number of multiplications to providing an improvement over the algorithm giving .
The current state of the art algorithm for matrix multiplication achieves . We do not know if there is an algorithm that achieves .
Algorithm 2
Multiplication can be seen as a special case of convolution and we can use Fast Fourier Transform (FFT) to perform this in . The details will be elaborated in the next section.
Convolution
Consider two vectors of the following form -
The convolution operation is defined as
Convolution is a generalization of integer multiplication (padding + convolution = multiplication). Also, convolution is a central operation in signal processing - used for blurring images and also to learn features from spatial data.
The naïve algorithm can be done in time. We can perform convolution using using Fourier Transform.
Fourier Transform
Consider the dimensional vector and . Let form a unit basis of such that .
Consider another basis of with components , where is the -th root of unity. Therefore, .
It is easy to check that this is a valid basis. So, again, can be uniquely represented as
-
,
-
A Fourier transform is then defined as - Given , compute .
The inverse problem is to find . It essentially is a change of basis between .
Convolution Theorem
Let be two vectors in ; then,
With this claim, convolution can be f=done in .
Dynamic Programming
Longest path on a DAG
Given a DAF with vertices, edges, every edge has a weight , compute the longest path on the DAG. The length of a path is defined as the weight sum over all edges in the path.
Consider the following algorithm
DFS(u):
if marked[u] = true:
return DP[u]
cost <- 0
for all v that (v, u) in E:
cost <- max(cost, DFS(v) + l_{v, u})
marked[u] <- true
DP[u] <- cost
return cost
The time complexity of the algorithm is . The key point to notice is that instead of recomputing the cost of each path, we have essentially stored the costs in the array DP to reduce the redundant calculations. This step is known as memoization.
Knapsack Problem
Consider an integer representing total capacity and a list of integers that represents the volume and cost of each item respectively. The goal is to pick items such that their total volume is at most and their value is maximized.
Idea 1. Sort everything by and pick the items until value if . It is easy to see that this greedy algorithm will not work.
A Backtracking algorithm
Consider an iterative algorithm that at step has volume left and is considering whether to pick or skip the -th item. Considering these two possibilities, we can implement a brute force algorithm with memoization for dynamic programming.
We set a 2D matrix of size where each row represents the set of items that need to be picked to maximize the cost within volume . Without memoization, this recursive search takes time; with memoization over the states , it takes time.
The algorithm is as follows -
dfs(C, i):
if i = 0: return 0
Cost <- dfs(C, i - 1)
if C >= c_i:
Cost <- max(Cost, dfs(C - c_i, i - 1) + v_i)
return Cost
Alternative view
We can treat every possible as a vertex in a graph. Every vertex has at most two outcoming edges - with cost and with cost . This constructed graph is a DAG and we essentially reduced Knapsack problem to longest path on a DAG.
Based on the algorithm we have seen earlier, we modify the algorithm to include memoization
dfs(C, i):
if marked[C][i] = true: return DP[C][i] // Modification
if i = 0: return 0
Cost <- dfs(C, i - 1)
if C >= c_i:
Cost <- max(Cost, dfs(C - c_i, i - 1) + v_i)
marked[C][i] <- true // Modification
DP[C][i] <- cost // Modification
return Cost
The modified algorithm now has the time complexity since there are vertices in total with atmost 2 edges each.
General observation
Dynamic Programming problems can be typically thought og as a decision-making processes. These decision problems can be converted to graphs where the states are vertices on a graph and the transitions are edges on a graph. Typically, the problem have a DP solution if the graph is a DAG and the number of states is not too large.
The algorithm shown above can then be used as a general procedure to solve the problems. Sometimes, it is beneficial to implement the algorithms with a loop rather than recursion.
Knapsack with unlimited items
The algorithm remains pretty much the same except that teh recrusion call has dfs(C - c_i, i) instead of dfs(C - c_i, i - 1).
Knapsack with limited items
We can consider another variant where item can be used at most times. Then, a similar algorithm would have the time complexity .
A better solution treats the th item as bounded-size items. For example, if , then divide the item as . Then the time complexity would be reduced to .
However, it can be improved to using a monotonic queue.
2D Knapsack
In this variant, each item has value , volume integer and a weight integer . The goal is to find a subset of items that has the total volume at most , total weight at most and the total value is maximized. The dynamic programming algorithm has a runtime of .
In the loop variant of the algorithm, it is better to iterate over the items first rather than the weights. Why is that? Furthermore, it is better to iterate decreasing the costs, because
Summary
Many intractable problems can be efficiently solved on trees - combining with DFS enforces the computation ordering.
Bellman-Ford algorithm
Single Source Shortest Path (SSSP)
Given a directed graph of vertices and edge, find the shortest paths for a vertex pair .
Recently, researchers showed that Dijkstra’s algorithm is the most optimal algorithm possible with a specially designed heap.
Would dynamic programming work for SSSP? represents a path from to using at most edges. This simply is the Bellman-Ford algorithm.
Floyd-Warshall algorithm
All pair shortest path algorithm in .
Traveling Salesman Problem
Given.a complete graph of vertices, every edge has a cost . The goal is to find a path that visits every node exactly once while minimizing the total cost. It is an NP-hard problem where the brute-force algorithm takes - enumerating all possible permutations of nodes.
There is a dynamic programming solutions of the order . This is computable with the modern computers upto . We discuss the framework here -
-
States - At node , set of all unvisited states - minimum cost to finish the rest of the task. The number of states is .
-
Decision-making
-
What will be the next node to visit? If we choose , then the next state will be $$(v, S - {v})$
This can be implemented using a bitmask for representing the state - saves space and is faster.