50 marks  CS 301 Quiz 2  3:30-5:00, 30/10/6

Problem 1: [20 marks] Suppose you have two warehouses U and V, respectively holding quantities u and v of a certain item. There are n customers, the ith amongst whom needs to be supplied with q_{i} items. The cost of shipping a single item to the ith customer from U and V are respectively u_{i} and v_{i}. So if r_{i} iterms are shipped to customer i from U and the remaining q_{i} − r_{i} from V, then the shipping cost is ∑_{i} r_{i}u_{i} + (q_{i} − r_{i})v_{i}. The problem is: given the numbers u, v and q_{1}, …, q_{n}, u_{1}, …, u_{n} and v_{1}, …, v_{n}, determine r_{1}, …, r_{n} such that the shipping cost is minimized, and the total amount shipped out of each warehouse is no more than the quantity originally present there. Assume that ∑_{i} q_{i} ≤ u + v. Give a greedy algorithm to solve this problem.

(Hint: What are the decisions you are making? What gain/loss can be associated with each decision?)

The decision to be made for each i, is to decide r_{i} that is to be shipped from U. Gain from shipping a single item to i from U rather than V is x_{i} = v_{i} − u_{i}. Since we can decide separately for each item, each decision for the ith customer causes us to gain or lose x_{i}.

The greedy idea is to make decisions of high gain first. Thus we begin by picking i such that |x_{i}| is as large as possible. Then if u_{i} < v_{i}, then we ship to i as much as possible from warehouse U and the rest from warehouse V, i.e. r_{i} = min(u, q_{i}). If u_{i} ≥ v_{i}, then we ship to i as much as possible from warehouse V and the rest from warehouse U, i.e. r_{i} = q_{i} − min(v, q_{i}).

Let us establish greedy choice, i.e. there is an optimal solution consistent with the above. Suppose the first case holds, i.e. u_{i} < v_{i}. Suppose an optimal solution Q ships a different value r < r_{i} from U to i. (r > r_{i} is illegal)

If in Q, U is not empty, we simply get an item from U to i and refuse one item at i coming from V. This will decrease the cost of Q, giving a contradiction. Thus U must be empty in Q. But then some customer j ≠ i must have received at least 1 unit from U. Consider what happens if we divert 1 unit to i from j. The gain for i is x_{i}, while the gain for j is −x_{j}. The total gain is thus x_{i} − x_{j} ≥ 0. In this way we can raise r upto r_{i} – and thus we will have proved that there exists an optimal solution in which r_{i} is shipped from U.

So we can recurse. But the recursion just requires us to find the largest |x_{i}| at each stage. So the greedy order is simply decreasing order of |x_{i}|. Thus the time = O(n log n) suffices.

About 10 marks for getting the algorithm idea: sort by decreasing |x_{i}|. 7 marks for correctness proof. 3 marks for stating the time. Note that sorting by x_{i} does not work– you lose 6 marks if you said this from the first 17.

Problem 2:(a)[5 marks] Consider the problem of mergeing two sequences. The input consists of sorted sequences x_{1}, x_{2}, x_{3} and y_{1}, y_{2}. How many leaves will a decision tree solving this problem have? How much time is thus needed? (b)[5 marks] Consider now the problem of merging 3 sorted sequences: x_{1}, x_{2}, x_{3}, y_{1}, y_{2}, and z_{1}, z_{2}. How much time is needed in this case? Only lower bounds are required in both cases.

A number (not an expression) is expected as the answer (as well as short explanation), and you will get no credit if your number is wrong, in both cases.

The number of answers are 5 choose 2, or 10. The tree height is thus 4 = minimum time needed.

The number of ways in this case are 7!/(3!2!2!) = 5*6*7 = 210. Thus the minimum number of comparison is 8.

An astounding number of people did not bother to work out ⌈log_{2} 10⌉ = 4. This cost 2 marks on each part. You were specifically asked to give a numerical answer!!! The point of this was that you should get some sense of the actual numbers.

Problem 3:(a)[5 marks] Define polynomial time reducibility among decision problems. Your definition should be completely correct to get any credit. (b)[5 marks] In the facility location problem you are given a bipartite graph G = (U, V, E) in which each vertex u ∈ U represents a village, each vertex v ∈ V represents a possible location for a facility (say a hospital), and edge (u, v) ∈ E iff u can be served by a facility opened at v. An additional input to the problem is an integer k. The decision problem is to determine if there exists a subset V′ ⊆ V of size |V′| = k such that every village will be served by at least one of the facilities in V′. Show that vertex cover reduces to the facility location problem. (c)[10 marks] Show that faciliity location reduces to circuit satisfiability.

(a) You must get definitions completely right – please note for the final examination. I ask definitions because you should know them, they also often help you for the other questions (by reminding you what is needed).

(b) This is simply set cover, with U = ground set, and each v ∈ V representing a set, and V the collection of sets. See the solution I posted for the homework.

(c) The input to the circuit is the candidate set of locations, specified as a bit vector —V— long. The constraint that village u is covered can be represented by specifying the OR of bits corresponding to the locations which can serve u. These constraint results are the ANDed to produce the output of the circuit. If the circuit is satisfiable, then the input gives us a set of locations such that all villages can be served, i.e. FL has answer yes. If FL has answer yes, then the set of locations fed to the circuit will produce a true answer, i.e. circuit is satisfiable.

Common mistakes for part (b) and (c): using the solutions to the instances to construct the reduction, e.g. using the vertex cover itself to construct the circuit. Having k as an input to the circuit – note that this will cause the circuit to be satisfiable, since for some value of k the set of locations will suffice.