100 marks  CS 301 Midsemester Test  9:30-11:30, 9/9/6

Whenever you are asked to give an algorithm, it is expected that you will give an argument as to why the algorithm is correct (unless it is obvious), and also evaluate the time taken by the algorithm.

For problems 2,3,4 it is sufficient if you estimate the optimal cost/value and not give an algorithm to compute the optimal solution itself.

Problem 1: A polynomial A(x) = a_{0} + a_{1}x + a_{2}x^{2} + … + a_{n}x^{n} can be represented by a vector A[0..n] in which A[i] = a_{i}. It is customary to use A to denote the polynomial as well as the vector.

(a)[5 marks] Given two vectors A[0..1] and B[0..1] representing first degree polynomials, show how C[0..2] representing the product of the polynomials can be formed using 3 multiplications (and a small number of additions/subtractions).

We need c_{2} = a_{2}b_{2}, c_{1} = a_{1}b_{0} + b_{1}a_{0} and c_{0} = a_{0}b_{0}. So calculate p = (a_{0} + a_{1})(b_{0} + b_{1}), q = a_{0}b_{0} and r = a_{1}b_{1}. Then c_{2} = r, c_{1} = p − q − r, c_{0} = q.

(b)[15 marks] Using the above show how to multiply two degree n = 2^{k} − 1 polynomials in o(n^{2}) time. Hint: Let A′[0..2^{k−1} − 1] = A[0..2^{k−1} − 1] and A′′[0..2^{k−1} − 1] = A[2^{k−1}..2^{k} − 1]. Then A(x) = A′′(x)x^{2^{k−1}} + A′(x). Express the product involving polynomial A in terms of products involving A′ and A′′. If you did not get part (a) then you may follow the hint and give an O(n^{2}) algorithm for less credit.

Suppose A and B are the input polynomials. Let C be the product. Define ’ and ” as before.

C(x) = A′′(x)B′′(x)x^{2k} + [A′(x)B′′(x) + A′′(x)B′(x)]x^{k} + A′(x)B′(x)

So clearly the recurrence is T (2^{k}) = 3T (2^{k−1}) + O(2^{k}). This has solution T (2^{k}) = O(3^{k}) or T (n) = O(n^{log 3}).

Problem 2:[25 marks] Suppose there are n projects on which you can work. There are a total of H hours you can spend on these projects. The returns you get on each project are given to you as an n × H matrix R, where R[i, j] denotes the return (in rupees) you get if you spend j hours on project i. The returns need not be linear, i.e. doubling the time spent on a project may not double the return.

Give an algorithm that takes as input integers n, H and the matrix R and determines how many hours to allocate to each project so that the total return (the sum of the returns on each project) is maximized.

Let G[i,H] denote the maximum return for projects i through n using H hours.

G[i, H] = max_{r∈[0,H]}{R[i, r] + G[i + 1, H − r]}

G[n,j]=R[n,j] for all j. Thus every entry takes time O(H) to fill. Total of nH entries, so time O(nH^{2}).

Problem 3: This problem is about approximating a polygonal line (polyline for short) by another polyline with fewer vertices.

Let P [1..n] denote a sequence of n points in the plane. Then the sequence of line segments (P [i], P [i + 1]), for i = 1, …, n − 1 will be called the n-polyline represented by P [1..n]. The straightness of this polyline is defined as the sum of the squares of the distance of each point P [i] from the line P [1], P [n]. For example, P = [(0, 0), (0, 1), (1, 1)] has straightness 0 + 1/2 + 0 = 1/2. Actually the details of straightness are not important: assume you are given a procedure S which given P returns the straightness in time proportional to the length of P.

Given a polyline P [1..n], and an integer m you are to find an increasing sequence of integers i_{1}, i_{2}, …, i_{m} with i_{1} = 1 and i_{m} = n such that the following is minimized:

∑_{j=1}^{j=m−1} S(P [i_{j}..i_{j+1}])

Note that this is as good as saying that the polyline defined by the points P [i_{1}], P [i_{2}], …, P [i_{m}] is the best possible if S is the error measure.

(a)[5 marks] Give an algorithm from specification for this problem.

Need to choose m − 2 points from the set {2, …, n − 1}. The easiest, acceptable way is to enumerate each set, then check whether only n−2 have been chosen, and if so, evaluate the sum of straightnesses, this requires O(n) time for a single set. So total time is O(2^{n}n).

You lose 2 marks if you only gave the algorithm but did not calculate the time taken.

(b)[20 marks] Give a faster dynamic programming algorithm.

Let the optimal solution be I[1..m], where I[j] = i_{j} as above.

Now I[2..m] must be an optimal solution for instance P [I[2]..n]. If not, suppose some J[2..m] is, and has smaller total straightness. Then I[1]——J[2..m] is also a solution for P. Since P[J[2]..n]=P[I[2]..n] we must have J[2]=I[2]. Hence the new solution will have smaller straightness.

So then we know that Opt solution of P[1..n],m = 1 —— optimal solution to P[I[2]..n] for some unknown I[2].

So defining the cost of the optimal solution of instance P[i..n],m as C[i,m] we get

C[1, m] = min_{j=2}^{j=n−m+2} S(P [1..j]) + C[j, m − 1]

Or in general:

C[i, m] = min_{j=i+1}^{j=n−m+2} S(P [i..j]) + C[j, m − 1]

12 marks for a correct recurrence.

The base case is C[i, 2] = S(P [i..n]). The time required for this is O(n − i). Thus the total time for setting the base cases is O(n^{2}). Filling a single table entry requires n − m calculations each requiring O(n) time. Thus the total time for a single entry is O(n^{2}). Finally, there are nm table entries. So the total time is O(n^{3}m).

Note that S(P [i..j]) can be calculated just once and saved for all i, j in time O(n^{3}). Given this, a single table entry requires only O(n) time. Thus the time can be reduced to O(n^{2}m) for the main algorithm; giving a total time of O(n^{3} + n^{2}m) = O(n^{3}). You dont have to get this last optimization; however, if you lose 3 marks if you incorrectly claim O(n^{3}).

Problem 4: Three job scheduling: Suppose you have a workshop in which there are m machines. A job consists of a list of the machines on which it requires processing, in the order in which it requires processing. Suppose every machine appears at most once in the list of each job. Furthermore, assume that if a job is to be processed on machine i then it is to be processed for exactly 1 step. A job must wait if the machine it requires is being used to process some other job.

Suppose 3 jobs arrive in the workshop, i.e. you are given 3 lists L, M, N each of length at most m giving the processing requirement as above. You are to devise a schedule for the jobs, i.e. determine which machine is to be used by which job (if any) at each step. The length of the schedule is simply the largest time step at which any machine is busy, and this is to be minimized.

As an example, suppose there are 4 machines and the job lists are L=[1,2,3,4], M=[1,3,4], N=[3,2,4]. Then two possible schedules are:

    Schedule 1         Schedule 2
    1 2 3 4 5 6 7      1 2 3 4 5 6 7
  +----------------    -----------------
L | 1 2 3 4            . 1 2 3 4
M | . 1 . 3 4          1 3 4
N | 3 . 2 . . 4        3 2 . 4

In each schedule, the entry in row i column j shows which machine is being used by job i at time step j, with the “.”s marking the position where the jobs are idling because the machine they require is busy. Clearly Schedule 2 is better because its length is 5 rather than 6.

Note that in this problem the problem size is the number of machines, with the number of jobs always being 3.

(a)[3 marks] For fixed L,M,N, how many ways are there in which execution can happen in step 1?

(b)[7 marks] Using the above or otherwise devise an obviously correct algorithm (which might take time exponential in m). Estimate the time taken.

At least one machine has to be busy at each step. There are 7 ways in which this can happen. Since it doesnt hurt to keep more machines busy if possible, if you check carefully you will see that this number is actually just 3.

There can be at most 3m steps. Thus the total number of schedules is at most 7^{3m}. Examining these and taking the best can be done in the same amount of time.

(c)[20 marks] Give a dynamic programming algorithm which runs in time O(m^{3}). If you feel the details are messy, you may only write down a high level description, stating clearly what the recurrence will be over and its general form, and estimate the time.

The solution space consists of all possible schedules. The first step can be taken in at most 7 ways. This splits the search space into 7 subspaces. Consider any subspace S_{i}. All solutions in this subspace have the same value in the first step. Thus in steps 2 and later, the same subproblem instance is being solved. This instance is same as the original instance L,M,N, except that at most one job from each of L,M,N might have been removed. So in general the subproblems that arise in this way will have some suffix of each list L,M,N. Define T(i,j,k) = optimal time required by instance L[i..], M[j..], N[k..]. Now we can write a recurrence relating T(i,j,k) and at most 7 T(i’,j’,k’) where i’,j’,k’ are the same as i,j,k respectively or smaller by 1. Thus T (i, j, k) can be calculated in constant time from the T (i′, j′, k′) values. The base case is simply when the strings are empty, for such case the time is 0. Since there are m^{3} entries the time required is also the same.