125 marks  CS 301 Sample Endsemester Test  Nov 2005

Problem 1[30 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 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 u + v ≥ ∑_{i} q_{i}. Your algorithm must run in time polynomial in u, v, n – prove this.

Problem 2:[35 marks] Suppose you are given numbers r_{1}, …, r_{n} and d_{1}, …, d_{n} which are respectively the release times and deadlines for n unit time tasks. These numbers are to be interpreted as: task i must be scheduled at some time between r_{i} and d_{i} (both inclusive). Further, only one task can be scheduled at each instant (i.e. only one processor is available). Devise an algorithm which does this. (It is possible that several tasks may have the same release time and/or the same deadline.)

Problem 3 (a)[5 marks] Define reducibility among decision problems. (b)[15 marks] Let G = (V, E) be a graph. A set of vertices V′ is said to be a dominating set if for every v ∈ V either v ∈ V′ or there is some neighbour u of v in G such that u ∈ V′. Given a graph G and an integer k, the dominating set problems asks whether there exists a dominating set in G of size at most k. Show that dominating set reduces to circuit satisfiability.

Problem 4(a)[5 marks] Define the notion of a polynomial time verifier for a decision problem. (b)[5 marks] Define NP. (c)[5 marks] Define NP-complete.

Problem 5[25 marks] A l×h transparency S is a two dimensional array of bits S[i, j] with 1 ≤ i ≤ l and 1 ≤ j ≤ h. When two transparencies S and T are overlayed we get a new transparency R where R[i, j] = S[i, j] ∨ T [i, j]. Define the transparency construction problem as follows:

INPUT: (i) Integers l, h respectively giving the dimensions of each transparency, (ii) Transparencies S_{1}, …, S_{n} (each specified as a sequence of lh bits) (iii) The desired transparency D (again specified as a sequence of lh bits). (iv) integer k, denoting the number of transparencies allowed.

OUTPUT: Can D be obtained by overlaying at most k of the transparencies S_{1}, …, S_{n}? (Overlaying of several transparencies A, B, C, D, … is defined in the natural manner, i.e. if R denotes the resulting transparency then R[i, j] = A[i, j] ∨ B[i, j] ∨ C[i, j] ∨ …)

Prove that transparency construction is NP-complete.