=========================preview======================
(COMP271)2001Fall_Midterm_SOL.pdf
Back to COMP271 Login to download
======================================================
COMP 271:Fall 2001 Lecture L3, Cunsheng Ding
Solutions to the Midterm Exam
Solution 1:
(a) There are ncalls to the output statement for each recursive call, except when n.1and then there are 0 calls. There are three recursive to subarrays of length n.3, and so this leads to the following recurrence, where nis a power of 3.
T(1).0 T(n).3T(n.3)+nfor n.1.
(b) We solve this by expansion (substitution).
T(n).3T(n.3)+n
.3(3T(n.9)+n.3)+n.9T(n.9)+2n
.9(3T(n.27)+n.9)+2n.27T(n.27)+3n
.:::
.3kT(n.3k)+kn:
Since we know T(1).0,welet k.log3n. This gives us
3log3
T(n).nT(1)+n(log3n)
.nlog3n:
This is .(nlogn). We could also get an asymptotic bound by applying the Master Theorem. We have a.b.3and k.1. Since a.bkit follows that the running time is .(nlogn).
Solution 2: This can be done in O(V+E)time by DFS. Start a DFS of Gat vertex s. We detect and delete each back edge that is incident to s.
DFSvisit(Graph G, Vertex u) {
color[u] = gray
for each (v in Adj(u)) {

if (color[v] == white) { // (u,v) is a tree edge
pred[v] = u
DFSvisit(v)

}
else if (v != pred[u]) { // (u,v) is a back edge
if (v == s)
delete (u,v) (and of course (v,u)) from G
}
}
}

1
0
To establish correctness we claim that (1) the resulting graph Gis connected and (2) sis not in any simple cycle. To see the .rst claim, observe that because we have only deleted back edges, the graph is still connected through its tree edges. To prove the second claim, observe that in any DFS tree, if there is no back edge to the root, then the root cannot be in any simple cycle. The reason is that any path that leaves the root descends into one of its subtrees along some edge e. Because there are no cross edges in the DFS of a undirected tree, the only way to return to the root is along edge e, but then such a cycle would not be simple. Since each back edge to sgenerates a simple cycle, every edge we delete lies on a simple cycle through s.

Solution 3:
(a) We will prove this by contradiction. Suppose that e.(u.v)is the maximum weight edge on some simple cycle. We claim that ecannot be in the MST of G. Suppose to the contrary that this edge is in the MST, denoted T. Remove this edge from the MST. This splits the MST into two subtrees Tuand Tv, where uis in Tuand vis in Tv. If we follow the path from uto von the cycle, there is at least on edge (x.y)on this cycle such that x2Tvand y2Tu. By removing (u.v)and adding edge (x.y)we form a new spanning tree T0whose weight is
w(T0).w(T);w(u.v)+w(x.y):
Since (u.v)is the maximum weight edge on the cycle and since edge weights are distinct, it follows that w(T0).w(T), but this contradicts the hypothesis that Tis the MST.
(b) If the weight of an edge e.(u.v)that is not in the MST decreases, then the MST may change. In particular, its addition creates a simple cycle, and the highest weight edge on this cycle must be deleted. The MST can be updated in O(V+E)time. We .rst compute the path from uto vin the original MST.