100 marks/120 minutes  CS 301 Midsemester Test  2:30-4:30, 14/9/2004

If you need to make assumptions, please state these carefully and proceed. Unless your assumptions make the problem too easy, you will receive some credit.

In problems 4,5 you are expected to use dynamic programming. More than half the marks are reserved for a proper statement of the optimal substructure, specifying which instances are relevant, directly and indirectly. If you do not use dynamic programming, you are still expected to argue about the correctness of your algorithm, and this will carry at least half the marks.

Problem 1: Suppose you are given a matrix A[1..m,1..n] in which each row and each column are sorted in non-decreasing, specifically, A[i, j] ≤ A[i, j + 1] and A[i, j] ≤ A[i + 1, j]. Your are to devise an algorithm for searching this matrix, i.e. given a value x determine if x is present in the matrix.

(a)[6 marks] Suppose you compare x with A[1, n]. What can you conclude if you find x < A[1, n], i.e. which part of the matrix do you need to search further, if at all? What if x > A[1, n]?

In the first case, we need to search A[1..m,1..n-1]. In the second case A[2..m-1,1..n]. (b)[14 marks] Use the above idea to devise a recursive algorithm for searching. Analyze the

time taken by it.

Search(x,rlow,rhi,clow,chi){ If x < A[rlow,chi] then {

if clow = chi then return false return Search(x,rlow,rhi,clow,chi-1)

}

If x = A[rlow,chi] then return true

If x > A[rlow,chi] then { if rlow = rhi then return false return Search(x,rlow+1,rhi,clow,chi)

} } Correct recursive calls: 4 marks, base cases: 2 marks, equality: 1 mark Time analysis: T(m,n) = max( T(m-1,n), T(m,n-1) ) + O(1) (4 marks) Hence T(m,n) = O(m+n) (3 marks) (If you assume that matrix needs to be copied and give the correct result based on that, that is also fine.)

Problem 2: Suppose we use binary trees to represent arithmetic expressions. As usual, leaf nodes in the tree will be numbers or names of variables, and internal names will be operators.

We are concerned with the case in which all the operators are binary, and commutative. You are to devise an algorithm which given two trees T1 and T2, determines if they represent the same expression. For example, suppose T1 and T2 correspond to the fully parenthesized expressions ((a+b)∗(c+(e∗d))) and (((e∗d)+c)∗(b+a)). Then T1 and T2 should be considered equivalent.

(a)[10 marks] Develop a simple recursive algorithm to determine if two given trees T1 and T2 are equivalent. Your algorithm need not be fast, but its correctness should be very obvious.

V(T) is value at root of T, L(T), R(T) denote left and right subtrees.

equiv(T1,T2){

if V(T1) ≠ V(T2) return false

If both T1,T2 are leaves return true

If only one is leaf return false

return ( equiv(L(T1),L(T2)) and equiv(R(T1),R(T2))

or equiv(L(T1),R(T2)) and equiv(R(T1),L(T2)) ) }

8 marks: idea of comparing left and right. 2 marks for other details.

(b)[10 marks] Assume that T1 and T2 are both complete binary trees with n = 2^{h} leaves. Under this assumption estimate the time taken by your algorithm as a function of n.

T (h) = 4T (h − 1) + O(1), T (h) = O(4^{h}) = O(n^{2}). or equivalent.

5 marks recurrence, 5 marks solution

5 marks extra credit if you observe that only 3 comparisons of size n/2 suffice, rather than the 4.

Problem 3:[10 marks] Order the following functions by their growth rates, in increasing order, i.e. put them in the order f_{1}, f_{2}, f_{3}, …, f_{9}, where f_{i} = O(f_{i+1}). Indicate the positions where the ordering is strict, i.e. where f_{i} = o(f_{i+1}).

The functions are: 4^{log n}, n^{log n}, n^{3}, n log^{2} n, (log n)^{n}, 2^{n}, 2^{n+1}, n^{2} + 3n, 4^{ln n}. Note that log x denotes the logarithm to base 2, and ln x to base e ≈ 2.72.

n log^{2} n < 4^{ln n} < 4^{log n} = n^{2} + 3n < n^{3} < n^{log n} < 2^{n} = 2^{n+1} < (log n)^{n}

f < g : f = o(g)

f ≤ g : f = O(g)

2 marks for identifying the two places where the order is not strict (1 mark for each). That leaves 8 marks. Then find the longest common subsequence with the correct ordering. If the longest common subsequence is length 9 (fully correct), then 8 marks. If it is length 8, 6 marks; if it is length 7, 4 marks; and if it is 6, 2 marks.

Problem 4:[25 marks] You are to design an algorithm for a single machine scheduling problem. The input consists of two integer arrays T [1..n] and P [1..n] and an integer D with interpretation as follows.

D denotes the number of steps for which the machine is available. T [j] denotes the number of steps needed by job j, and P [j] the profit job j produces if it is given its T [j] steps. The machine can process only one job at any step.

Give an algorithm which determines which job must be processed so as to maximize profit. Your algorithm should return an array S[1..n] where S[j] denotes whether or job j should be processed.

You may only describe how to compute the maximum possible profit if you wish.

Instance: D,T,P. Let OPT(D,T,P) denote the optimal solution; this is an array giving the numbers of the selected jobs. Instances characterised as d,j which denotes the instance with at most d, and only objects j..n, i.e. using values T[j..n],P[j..n]. OSC:

If S[1]=true, then Opt(D,j) = true || Opt(D-T[1],j+1)

else OPT(D,j) = false || Opt(D,j+1) Directly relevant instances: 2. Indirectly relevant: All values of d,j. Table[d,j] will contain solution to (d,j) Base cases: Table[d,n] = if T[n] ≤ d then true else false Updating Table[d,j]: Compute the costs of relevant instances: d-T[j],j+1 and d,j+1. Then pick solution to (d,j) as per OS. These calculations can be done incrementally, if we store the total profit in the table. The update rule then is: Profit(d,j) = max(P [j] + profit(d − t[j], j + 1), profit(d, j + 1)) Time: O(Dn) entries, each update takes O(1). So total O(Dn). 15 marks for OS Claim (including definition of directly relevant instances, and update rule. Update rule may be stated as a part of the OS claim or given separately as part of algorithm) 5 marks : how many indirectly relevant instances are present, how table is indexed/initialized. 5 marks: computing the total time. ——— Some students gave a different optimal substructure as follows. Let S be a solution to the original instance I. Then the solution S’ obtained by removing any job j is a solution to I’ = I without job j. With this, the indirectly relevant instances become all possible subsets of I, which are Ω(2^{n}). This solution is really not good, since the brute force solution is as good. However, if you worked it out correctly till the end then you got upto 12 marks for it.

Problem 5:[25 marks] Suppose you are given an integer array D[1..n] where D[i] is the demand for a certain commodity on day i. You have a machine which has cost s for starting up. But once the machine is running it will produce q units of the commodity every day. If you wish to produce fewer than q units on any day, then the machine must be shut down that day (and so will have to be restarted later). All units that are left over at the end of each day incur a holding (storage) cost of h per unit. It is required that no items remain after day n.

You are to devise an algorithm which given the values for s, q, h and D[1..n] determines a minimum cost production schedule S[1..n] where S[i] denotes the number of units produced on day i. If you wish you may only describe how to determine the minimum cost.

(You may assume that there is at least one Schedule that can satisfy the demand.) (An example: Suppose s = q = 6, h = 1. Suppose D = (3, 3, 0, 3, 0, 0, 9). Then this can

be met with the machine producing S = (6, 3, 0, 0, 0, 6, 3) units on the respective days. There will be two times when the machine will have to be started (day 1 and day 6) for a total cost of 12. Further the 3 extra units produced on the first day will have to be stored for 3 days, and the 6 produced on day 6 for 1 day, for a total storage cost of 15. The overall total cost is thus 12 + 15 = 27 Another way to meet this demand is by using S = (6, 6, 6, 0, 0, 0, 0). For this there will be only one startup, with cost 6. But 3 units will be held over on day 1, 6 on day 2, 12 on day 3, 9 on day 4, 9 on day 5, 3 on day 6. So the total holding cost is 3 + 6 + 12 + 9 + 9 + 3 = 42. The total cost for this schedule is 6 + 42 = 48. Clearly, the first schedule is better.)

The problem needs a reformulation. Given an initial inventory i (number of units in stock at the beginning), and the initial machine state s (running/stopped) what is the best schedule.

A general instance is given by the triple (i,m,D[j..n]), where is is the initial inventory, s the machine state, and j is the starting day. We can use (i,m,j) to denote the instance, and assume that D is global.

Solution to (i,m,j) is Opt(i,m,j) = S[j..n], where S[k] is the production on day k.

OS:

If S[j]=p, p¡q, then OPT(i,m,j) = p || Opt(i-D[j]+p, stopped, j+1)

If S[i]=q, then OPT(i,m,j) = q || Opt(i-D[j]+q, running, j+1)

Relevant instances are q+1, corresponding to the values 0..q that S[j] can take.

Indirectly relevant instances are all instances of the form (i,s,j), where i can be as large as the total demand D=sum of D[i], s can take two values stopped/running, and j can take n values.

Table will have the 3 dimensions as above.

Easy instances: (i,m,n) : This has solution S[n,n], which must be D[n]-i. If this value is bigger than s, then mark this infeasible.

Update rule: Given the complete solution to an instance, we can calculate its cost as per the problem statement. However, we could also optimize in this step. Keep the cost of the instance in the table as well, and then the cost of an instance can be INCREMENTALLY calculated from the costs of the relevant instances. This is as:

Cost(i, m, j) = min_{p=0..q} h(i+p−D[j])+s(1−m)(D[j] > 0)+Cost(i+s−D[j], D[j] == q, j+1)

In the above the first term is the holding cost for day j; further the machine state m is to be thought of as a 0-1 variable with 0 representing “stopped” and 1 representing “running”. Further, the conditional expressions D[j] > 0 and D[j] == 0 are to have values 1/0 for true/false.

Defining what an instance is: 3 marks

OS + directly relevant instances : 12 marks.

Table details: 5 marks

Analysis: 5 marks.