COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 5 School of Computer Science
Tutorial
This tutorial will be mostly reviewing greedy and divide-and-conquer algorithms. Please make sure you do Problem 4 as it will be important for next week’s lecture.
Problem 1
Suppose we are to schedule print jobs on a printer. Each job j has an associated weight wj > 0 (representing how important the job is) and a processing time tj (representing how long the job takes). A schedule σ is an ordering of the jobs that tell the printer how to process the jobs. Let Cjσ be the completion time of job j under the schedule σ.
Design a greedy algorithm that computes a schedule σ minimizing the sum of weighted completion times, that is, minimizing j wjCjσ.
Solution: An optimal schedule can be obtained by sorting the jobs in increasing tj order; wj
assume for simplicity that no two jobs have the same ratio. To show that the schedule is
optimal, we use an exchange argument. Suppose the optimal solution is σ and there are two
adjacent indices, say i and k such that ti > tk . We build another schedule τ where we wi wk
swap the positions of i and k, and leave other jobs in their places. We need to argue that this change decreases the cost of the schedule. Notice that the completion time of jobs other thaniandkisthesameinσandτ. Thus,
wjCjσ −wjCjτ =wiCiσ +wkCkσ −wiCiτ −wkCkτ. (1) jj
Let X = Ciσ − ti, the time when job i starts in σ, which equals the time when job k starts in τ. Then Ciσ = X + ti, Ckσ = X + ti + tk, Ckτ = X + tk, and Ciσ = X + ti + tk. If we plug these values into the above equation and simplify, we get
wjCjσ −wjCjτ =−witk +wkti. (2) jj
The proof is finished by noting that ti > tk implies −witk + wkti > 0 and therefore wi wk
wjCjσ >wjCjτ. jj
Hence, the schedule σ is not optimal.
Problem 2
Consider the following algorithm for the MST problem:
1
Algorithm 1 Reverse-MST
1: 2: 3: 4: 5: 6: 7: 8: 9:
10:
functionReverse-MST(G,w)
sort edges in decreasing weight w T←E fore∈E[inthisorder]do
if T − e is connected then T←T−e
end if end for
return T end function
Prove its correctness and analyze its time complexity. To simplify things, you can assume the weights are different.
Solution: Suppose e was one of the edges the algorithm kept. If e belongs to the optimal solution we are done, so assume for the sake of contradiction that this is not the case.
If the algorithm decided to kept e then it must be that T − e was not connected, say T − e had two connected components X and Y . Notice that all edges in the cut (X, Y ) have a weight larger than w(e). Therefore, we can take the optimal solution, add e to form a cycle C. This cycle must contain one edge f from cut(X, Y ), so we could remove f and improve the cost of the optimal solution, a contradiction. Therefore, e must be part of the optimal solution. Since this holds for all e in the output the algorithm is optimal.
Regarding the time complexity, we note that checking connectivity can be done O(n + m) time using DFS. There are m iteration, so the overall time complexity is O(m(n + m)).
Problem 3
A computer network can be modeled as an undirected graph G = (V, E) where vertices represent computers and edges represent physical links between computers. The maximum transmission rate or bandwidth varies from link to link; let b(e) be the bandwidth of edge e ∈ E. The bandwidth of a path P is defined as the minimum bandwidth of edges in the path, i.e., b(P ) = mine∈P b(e).
Suppose we number the vertices in V = {v1, v2, . . . , vn}. Let B ∈ Rn×n a matrix where Bij is the maximum bandwidth between vi and vj. Give an algorithm for computing B. Your algorithm should run in O(n3) time.
Solution: Let T be a maximum weight spanning tree, that is, the spanning tree maximizing e∈T b(e). We claim that in this tree for any two vertices u, v ∈ V , the unique u-v path in T is a maximum bandwidth path. Indeed, assume that there is a pair of vertices u and v contradicting our claim. That is, let e be the minimum bandwidth edge in the unique u-v path in T and let P be an alternative u-v path p in the graph whose bandwidth is b(P) > w(e). Now remove e from T breaking the tree into two connected components A and B having u on one side and v on the other. Then the path P must contain at least one edge, call it f, with one endpoint in A and another endpoint in B. Since b(P) > b(e) then b(f ) > b(e), and so T − e + f is also spanning tree with greater weight. A contradiction.
After computing T we could loop over every pair of vertices vi and vj , computing the lightest edge in the unique vi-vj path in T. This takes O(n) time per pair of vertices, so we get overall O(n3) time.
2
Problem 4
Recall the optimal time investment window problem from Lecture 1. In this problem, we are given an array A of n integers (each integer can be positive, zero, or negative). A time window is an interval [i,j] and its return is the sum of elements of the array with indices between i and j (inclusive), i.e. the return of [i,j] is i≤k≤j A[k]. Note that a time window with i = j is allowed; in this case, its return is A[i].
Give a divide-and-conquer algorithm that finds a time window with maximum return and runs in time O(n log n).
Solution: (Sketch.) Base case: n = 1, return A[1].
Divide step: divide array in half and recurse on each half.
Merge step: The optimal time window [i,j] either has i,j ≤ n/2 (both in first half) or i,j ≥ n/2+1 (both in second half) or i ≤ n/2 and j ≥ n/2+1. The recursive calls give us the optimal time windows of the first two types so we just need to find the optimal time window of the third type and take the best of these three options. To find an optimal window containing n/2 and n/2 + 1, observe that it must be a concatenation of an optimal time window ending at n/2 and and an optimal time window starting at n/2 + 1; otherwise, we can exchange with a better time window ending at n/2, or a better time window starting at n/2 + 1. To find the best time window starting from some index i, we scan the array in O(n) time to compute the return of all time windows [i,j] with j > i and take the maximum of these time windows. Ditto for best time window ending at i. Thus, overall the merge step can be done in O(n) time.
The divide step takes O(1) time and merge step takes O(n) time. So the recurrence relation is T (n) = 2T (n/2) + O(n) = O(n log n).
Problem 5
(Exercise 6, Chapter 5 from textbook Algorithm Design) Let T be a complete binary tree with n vertices. Each vertex v has a distinct weight w(v). A vertex is a local minima if its weight is less than the weight of its neighbors. Give a divide-and-conquer algorithm that finds a local minima in time O(log n).
3
Solution: The algorithm starts at the root and does the following recursively. If the current vertex is an internal vertex with smaller weight than both of its children, return the current vertex as a local minima; otherwise, recurse on one of the children with smaller weight. If the current vertex is a leaf, then return the current vertex as a local minima.
To see why this is O(logn) time, note that we take O(1) time to decide whether to return the current vertex as a local minima or to recurse on one of the two children, and whenever we recurse, we go down one level of the binary tree. Since a complete binary tree with n vertices has at most O(log n) levels, the total time taken by this algorithm is O(log n).
The proof of correctness is easiest to see without using induction (see below for an induction proof). Suppose, towards a contradiction, that the algorithm returns a vertex v that is not a local minima. By definition of the algorithm, v cannot be an internal vertex because the algorithm only returns an internal vertex u after checking if its weight is indeed smaller than all of its neighbors. Thus, v must be a leaf. But then the algorithm reached v only because the v’s parent has larger weight than v. Since v is a leaf, its parent is its only neighbor. Thus, v is a local minima.
Here’s a proof of correctness via induction.
Base case: (n = 1) The algorithm correctly returns the single vertex as a local minima. Induction case: (n > 1). Suppose the algorithm is correct for complete binary trees with less than n vertices. If the root r is a local minima, then the algorithm correctly returns the root. Otherwise, suppose the algorithm recursed on r’s child u, and let v be the vertex returned by the recursive call. There are two cases: either u = v is a child of the root r or not. In the latter case, the correctness follows from the induction hypothesis. For the former case, the induction hypothesis only tells us that v is smaller than both of v’s children. We still need to show that v is smaller than its parent r. But this follows from the fact that we recursed on v precisely because v is smaller than r.
Problem 6
(Due to Jeff Erickson.) For this problem, a subtree of a binary tree means any connected subgraph. A binary tree is complete if every internal node has two children, and every leaf has exactly the same depth. Describe and analyze a recursive algorithm to compute the largest complete subtree of a given binary tree. Your algorithm should return both the root and the depth of this subtree. See Figure 1 for an example.
Figure 1: The largest complete subtree of this binary tree has depth 3.
4
Solution: Suppose that n is the number of vertices of the tree. Let r be the root and vL,vR be its left and right child. Our algorithm will return the largest complete subtree as well as the largest complete subtree rooted at r.
Base case: (n = 1) Return the single vertex.
Divide step: recurse on subtrees rooted at vL,vR.
Merge step: We need to know what the largest complete subtree rooted at the r and return the best of this and the largest complete subtrees contained in its children’s subtrees. To do this, take the largest complete subtree TL rooted at vL and the largest complete subtree TR rooted at vR. Suppose TL has depth dL and TR has depth dR. The largest com- plete subtree rooted at r is then the complete subtree rooted at r with depth 1+min{dL, dR}.
Here’s a proof of correctness by induction: Base case: (n = 1). This is trivial.
Inductive case: (n > 1). Suppose the algorithm is correct for trees with less than n vertices. Then the largest complete subtree is either rooted at r or is entirely contained in the subtree rooted at vL or entirely contained in the subtree rooted at vR. The largest complete subtree rooted at r consists of r and the first min{dL, dR} levels of TL as well as the first min{dL, dR} levels of TR. This is because otherwise, either the largest complete subtree rooted at vL is larger than TL or the largest complete subtree rooted at vR is larger than TR, contradicting the inductive hypothesis. Thus, the algorithm is correct for trees with n vertices.
The divide step and merge step takes O(1) time. Then the recurrence relation is T(n) = T(nL)+T(nR)+O(1)wherenL,nR arethesizesofthesubtreesrootedatvL,vR,respectively. Unrolling the recurrence, we see that we spend O(1) time per vertex of the binary tree. So, total time is T (n) = O(n).
Problem 7
Describe an algorithm to insert and delete points from a kd-tree. You do not have to rebalance the structure.
Solution: It’s just a binary tree so insertion/deletion is trivial.
Problem 8
Describe an algorithm to insert and delete points from a range-tree. You do not have to rebalance the structure.
Problem 9
[Optional] Consider the following algorithm for the MST problem:
Algorithm 2 Improving-MST
Solution: Slightly trickier since a point exists in O(logd−1 n) canonical subsets (binary trees). Insert/delete in each of them.
1: 2: 3: 4: 5: 6: 7: 8: 9:
10:
functionImproving-MST(G,w) T ← some spanning tree of G fore∈E[inanyorder]do
T←T+e
C ← unique cycle in T f ← heaviest edge in C T←T−f
end for
return T end function
5
Prove its correctness and analyze its time complexity. To simplify things, you can assume the weights are different.
Solution: Let T0, T1, T2, . . . , Tm be the trees kept by the algorithm in each of its m iterations. Consider some edge (u,v) ∈ E that did not make it to the final tree. It could be that (u,v) was rejected right away by the algorithm, or it was in T for some time and then it was removed. Suppose this rejection took place on the ith iteration. Let p be the u-v in path in Ti. Clearly all edges in p have weight less than w(u,v). It is easy to show using induction that this is true not only in Ti but in all subsequent trees Tj for j ≥ i.
Let (x,y) be an edge in the final tree Tm. Remove (x,y) from Tm to get two connected components X and Y. In the textbook (Property 4.17) it is shown that if (x,y) is the lightest edge in the cut (X, Y ) then every MST contains (x, y). Suppose for the sake of contradiction that there is some edge (u, v) ∈ cut(X, Y ) such that w(u, v) < w(x, y). This means that (u,v) is not the heaviest edge in the unique u-v path in Tm, which contradicts the conclusion of the previous paragraph. Thus, (x,y) belong to every MST. Since this holds for every edge in Tm, it follows that the Tm itself is an MST.
Regarding the time complexity, we note that finding the cycle in T + e can be done O(n) time using DFS. Similarly finding the heaviest edge and removing it take O(|C|) = O(n) time. There are m iteration, so the overall time complexity is O(nm).
Problem 10
[Optional] (Due to Jeff Erickson.) Let T be a binary tree with n vertices. Deleting any vertex v splits T into at most three subtrees, containing the left child of v (if any), the right child of v (if any), and the parent of v (if any). We call v a central vertex if each of these smaller trees has at most n/2 vertices. See Figure 2 for an example.
1. Show that every tree has a central vertex.
2. Give an algorithm that finds a central vertex of v in O(n) time.
Figure 2: Deleting a central vertex in a 34-node binary tree, leaving subtrees with 14, 7, and 12 nodes.
6
Solution: (Rough sketch.)
1. Base case (n = 1): return 1
Divide step: Recurse on subtrees rooted at children
Merge step: Let vL and vR be left and right child of root vertex. Return s(vL) + s(vR) + 1.
Time complexity analysis same as Problem 6.
2. Observe that if we remove a vertex v from T, the subtree containing its left child vL has s(vL) vertices, the subtree containing its right child vR has s(vR) vertices, and the subtree containing its parent has n−s(v) vertices. Consider the following process: start at some vertex, check if any of s(vL), s(vR), n − s(v) is more than n/2. If s(vL) > n/2, move to vL; else if s(vR) > n/2, move to vR; else if n−s(v) > n/2, move to v’s parent; else stop.
Observe that if the process stops, the vertex it stops at must be a central vertex. So it suffices to prove that the process must stop. Suppose, towards a contradiction, that the process never stops. Then, since the graph is a tree, it must have traversed some edge (u, v) in both directions. Suppose that u is the parent of v. The process traveled from u to v at some point, implying that s(v) > n/2. Similarly, it traveled from v to u at some point, implying that n − s(v) > n/2. But adding these two inequalities gives us n > n, a contradiction. Thus, the process must stop and so a central vertex exists.
3. Determine s(v) for each vertex v in O(n) time and run the above process. Since the process never repeats a vertex, it takes only O(n) time.
7