Homework 6 COMS 311 Points: 100 Due: Oct 24, 11:59PM
1. Solve the following recurrences (Do not use Master theorem)
(a) T(n) = T(n/2) + cn2
Ans. Imagine expanding the recurrence tree. At level zero, there is one node with size n. At level one, there is one node with size parameter n/2. In general at level k, there is a node with size parameter n/2k. The time at level k is (n/2k)2 and there are logn levels. Thus the total time is
Above can be written as
cn2 +cn2/4+cn2/16+···+c cn2(1+1/4+1/16+···1/n2)
Thus summation 1 + 1/4 + · · · is bounded by 2. Thus the total time is O(n2). (b) T(n)=T(n/2)+T(n−1)+c
Ans. This is a tricky recurrence for which we can only hope to obtain a bound, not an exact solution. Consider the recurrence tree. This tree has terms n,n/2,···1. These terms contribute O(log n). The tree also will have terms n − 1, (n − 1)/2, (n − 1)/4 · · · contributing to O(log(n − 1)) In general the terms (n − i), (n − i)/2, · · · , 1 will contribute O(log(n − i)). Now
logn + log(n − 1) + log(n − 2) + · · · log 1 = O(n log n)
Thus T (n) is bigger than O(n log n).
Here is a way to get better bounds. For now, we will ignore c. We will re-write the above recurrence as follows:
T (n) − T (n − 1) = T (n/2)
T(n) − T(n − 1) = T(n/2) T(n−1)−T(n−2) = T((n−1)/2) T(n−2)−T(n−3) = T((n−2)/2)
··· ···
1
Adding the equations, we get
T (n) = T (n/2) + T ((n − 1)/2) + T ((n − 2)/2) + · · · + T (1)
Let us try to upper and lower bound this. We can say
Solving this, we would get
T (n) ≥ n/4T (n/4)
T(n)≥n× n ×···×1 4 16
Note that RHS has O(log4 n) terms.
Thus T(n) = Πlog4 n n Thus T(n) = nlog4 nΠlog4 n 1 . Note that
log2 n T(n)≥2 4
i=1 4i
i=1 4i 1
Πlog4 n 1 = i=1 4i
41+2+···+log4 n
Since log n = log2 n, and using the fact that 2logn = n, we obtain
which is atmost 1 4(log4 n)2/2
42
We can prove an upper bound bound on this as follows: Consider the recurrence tree: 1 node at level 1. We have n/2 nodes at level 2. Each of of these nodes have at most n/4 nodes and thus at level 3 we have at most n2/8 nodes. Each of these nodes have at most n/8 children thus there are n3/64 nodes at level 4 and so on. Maximum depth is O(log n). In general level i has at most ni nodes.
nlog n log2 n
Thus the number of leaves is at most Πlog n2i . This is at most O(2 2 ). Note that the
i=1
number of leaves in a tree are bigger than the number of internal nodes. Thus T(n) is
log2 n at most O(2 2 ).
(c) T(n) = 3T(n/3) + cn
Ans, Consider the recurrence tree. At level 0, there is one node with size parameter n and the time is cn. At level 1, there are 2 nodes with size parameter n/3 and time for each node is cn/3. Thus the total time for level 1 is cn/3 + cn/3 + cn/3 = cn. In general at level k, there are 3k nodes each with size parameter n/3k. Time for each node at level k is cn/3k. Thus the total time at level k is 3k ×cn/3k = cn. Finally the recurrence tree has log3 n levels. Thus the total time is O(n log n).
2. Given a connected graph G where edge costs are pair-wise distinct, prove or disprove that the G has a unique MST.
Ans. We will first prove the following property of MST (for graphs with distinct edge weights). Let T be an MST. Suppose e = ⟨u,v⟩ is not in T. Then for every edge f that lies in the path from x to y, c(e) > c(f). Otherwise, we could remove f from T and add e, and thus get a smaller MST.
2
2×···2i
Now suppose that there exist two MST T1 and T2. Let e = ⟨u, v⟩ be the edge with smallest weight such that e is in exactly one of T1 or T2. Without loss of generality assume that e is in T1. Let P be a path from x to y in T2. By previous claim, for every edge f ∈ P, have c(e) > c(f). We now observe that for every f ∈ P, it must be the case that e ∈ T1. Suppose that g ∈ P, but not in T1. Since c(g) < c(e), it would contradict the choice of e. Thus the path P (from u to v) exists in T1, however the edge e = ⟨u, v⟩ also is in T1, This implies that T1 has a cycle and thus an not be MST. This is a contradiction.
3. Let’s consider a long, quiet country road with houses scattered very sparsely along it. (We can Picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let’s suppose that desPite the bucolic setting, the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road.
Assume the country road has mile-markers: 0 at the extreme west end of the road and N at the extreme east. Each house hi denotes the mile at which it is located. For instance, hi = k means the i-th house is k miles from the west end of the road. Also assume that each base station has a range of R miles. That is, if the base station is placed at t miles from the west end, then all houses |t − hi| ≤ R are covered by that base station.
Give an efficient algorithm that achieves the goal of covering all houses, using as few base stations as possible. Prove the correctness of your algorithm.
Ans. Consider the following algorithm.
• Sort the houses in based on hi values (in increasing order). • Repeat until there are no more houses to cover
– Let h be the first house not covered by any base station. – Place a base station at h + R.
Time taken by the algorithm is O(n log n). Let us assume that k1, · · · kn are the locations in sorted order. To prove the correctness let us assume that the above algorithm places l bases stations at locations g1, g2, · · · gl (in sorted order). Assume that there is a optimal solution that places r base stations at locations o1, o2 · · · , or (in sorted order). Our goal is to prove that l equals r. For this we first claim the the following: gi ≥ oi for 1 ≤ i ≤ l.
We prove this by induction. For base case: Note that g1 = k1 + R. If g1 < o1, then the house at k1 is not covered by o1, and thus O will not be a valid solution. Thus g1 ≥ o1.
Assume that gp ≥ op, We will prove that gp+1 ≥ op+1. Consider a house that is not covered gp and k be the location of this house. Since op ≤ gp, op also can not cover this house. Note thatgp+1 =k+R,nowifop+1 >k+R,thenthehouseatlocationkcannotbecoveredby the solution O. Thus gp+1 ≥ op+1. This proves our claim.
Now suppose that r < l. By previous claim, it must be the case that or ≤ gr. Since the greedy algorithm places a base station at gr+1, there is a house that is not covered by gr and this house can not be covered by or (as or ≤ gr). This means that O can not be a valid solution, and this is a contradiction. Thus r can not be less than l and this must equal l. Thus gredy solution is as optimal solution.
3
house
4. Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection of n bank cards that they’ve confiscated, suspecting them of being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank. Each account can have many bank cards corresponding to it, and we’ll say that two bank cards are equivalent if they correspond to the same account.
It’s very difficult to read the account number off a bank card directly, but the bank has a high- tech “equivalence tester” that takes two bank cards and, after performing some computations, determines whether they are equivalent. Their question is the following: among the collection of n cards, is there a set of more than n/2 of them that are all equivalent to one another?
Assume that the only feasible operations you can do with the cards are to Pick two of them and plug them in to the equivalence tester. Show how to decide the answer to their question with only O(nlogn) invocations of the equivalence tester.
Ans. This question can be re-phrased as follows. There is a collection of objects, given two objects we can only test whether one object equals the other or not. Find if there majority object–an object that appears more than n/2 times. Suppose that we divide the set of objects into two equal size parts L and R. If an object O is the majority object, then it must be a majority in either L or R. Thus observation leads us to the following algorithm: Let S be the set of objects. If there is only one object return that object. Else divide the set of objects in to two equal sized parts L and R. Recursively compute a majority object X for L and a majority object Y for R. Now count number of times X appears in S and number of times Y appears in S. If any of them appear more than n/2 times, then return that object.
Let T(n) be the number of comparisons. T(n) can be expressed as 2T(n/2) plus the number of comparisons made to count number of times X appear in S and number of times Y appear in S. The latter is O(n). Thus the recurrence is T (n) = 2T (n/2) + O(n), T (1) = 1. The solution is O(n log n).
4