50 marks  CS 301 Quizz 1  9:30-10:30, 31/8/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.

Spend about 1 minute per mark. If a problem has few marks, it is probably easy and you are expected to write in brief.

Problem 1[12 marks] Strassen’s algorithm for multiplying two n×n matrices is based on a divide and conquer strategy as follows. The original matrices are partitioned into 4 matrices each of size \frac{n}{2} × \frac{n}{2}. These smaller matrices are then added or multiplied together to give the product of the original matrices. The algorithm performs 7 matrix multiplications involving these small matrices, and also 12 matrix additions, also involving the small matrices. Assuming that the rest of the work done by the algorithm is negligible, write a recurrence for the time required by Strassen’s algorithm and solve it. (You are NOT expected to figure out how the algorithm works, but just estimate the time.)

The basic recurrence is (4 marks):

T (n) = 7T (n/2) + O(n^{2})

We will solve by repeated substitution. We will write this as T (n) ≤ 7T (n/2) + cn^{2} first for simplicity.

T (n) ≤ cn^{2} + 7T (n/2)

≤ cn^{2} + 7(c(n/2)^{2} + 7T (n/4))

≤ cn^{2} + 7cn^{2}/4 + 49T (n/4)

≤ cn^{2} + 7cn^{2}/4 + 49(c(n/4)^{2} + 7T (n/8))

≤ cn^{2} + 7cn^{2}/4 + 7^{2}cn^{2}/4^{2} + 7^{3}T (n/2^{3}))

≤ cn^{2}(1 + 7/4 + ..(7/4)^{k−1}) + 7^{k}T (n/2^{k})

≤ cn^{2} \frac{1−(7/4)^{k}}{1−7/4} + 7^{k}T (n/2^{k})

We can do this until k = log n. Then T (n/2^{k}) = T (1) = d for some constant d. Further 7^{k} = 7^{log_{2} n} = 2^{log_{2} 7 log_{2} n} = n^{log_{2} 7}. Also 4^{k} = n^{2}. Thus we get

T (n) ≤ cn^{2} \frac{7^{log n}n^{2}−1}{3/4} + 7^{log n}d

≤ c′7^{log n}

Thus T (n) = O(n^{log_{2} 7}). Similarly we can argue T (n) = Ω(n^{log_{2} 7}). (solving recurrence: 8 marks).

Problem 2 Consider the problem of determining whether a string A[1..m] is a substring of another string B[1..n], i.e. whether there exists an integer d such that A[i] = B[i + d] for all 1 ≤ i ≤ m.

(a)[5 marks] Give a simple, possibly brute force algorithm for solving the problem, and estimate the time taken by it. Say this algorithm is called brute. brute(A,B){ m = length(A) n = length(B) for i=1 to n-m+1

match = true for j = 1 to m

if A[j] ≠ B[i+j-1] then match = false end

if match = true return true end return false } Worst case time : both loops will execute the maximum number of times; then time will be O(m(n − m))

(b) Consider the following divide-and-conquer strategy for solving the problem:

DandC(A,B){
 m = length(A)
 n = length(B)
 if n < 2m then return brute(A,B)
 if DandC(A,B[1..n/2]) or DandC(A, B[n/2+1..n]) then return true
 Else
   ...
}

(i)[9 marks] Complete the algorithm given above – state what is needed in place of ....

The recursive parts check for occurrences of A entirely within the halves, but not occurrences in which a part of A appears in one half and the rest of it in the other half. So the following code is needed.

return brute(A,B[n/2-m+1..n/2+m-1])

Anything equivalent will also be fine. (ii)[9 marks] Write a recurrence to estimate the time taken by your algorithm. Solve the

recurrence. Do not worry if this algorithm does not appear to be an improvement over Brute.

Since any call solves two problems of half the size, and calls brute for finding a string of length m in a string of length n (for this the time taken is O((2m − m)m) = O(m^{2})), we get the recurrence: T (m, n) = 2T (m, n/2) + O(m^{2}), with base case T (n, m) = O(m^{2}) for n ≤ 2m.

T (m, n) ≤ cm^{2} + 2(cm^{2} + 2T (m, n/4))

We can repeat this till the second argument to T becomes at most 2m i.e. until n/2^{k} ≤ 2m, i.e. till k = log(n/2m) times. Then we will have

T (m, n) ≤ cm^{2} ∑_{i=0}^{i=k} 2^{k} + 2^{k}T (m, m)

T (m, n) ≤ cm^{2}O(n/m) + (n/2m)O(m^{2})

Thus T(m,n) = O(mn). It is possible to show that T (m, n) = Ω(mn) as well.

(3 marks for the recurrence, 6 marks for the solution)

Problem 3: Suppose you are given a sequence A[1..n]. You are to determine the longest palindromic sequence that is a subsequence of A. A sequence P [1..2k] is said to be palindromic if P [i] = P [2k − i] for all i. For example if A = “computer science”, then “ceec” is a longest palindromic subsequence.

(a)[5 marks] Does this problem have optimal substructure? Explain.

I am giving two solutions to the problem.

Optimal substructure 1: If P[1..2k] is a solution to A[1..n], then P[2..2k-1] must be a solution to some A[i..j] where i > 1, j < n.

Proof: Let i′ be the first occurrence of P[1] in A, and j′ be the last. Then for i = i′ + 1 and j′ = j − 1 clearly P[2..2k-1] must be a subsequence of A[i..j]. If A[i..j] has a larger palindromic subsequence P′ then P [1] · P′ · P [1] is also a palindromic subsequence of A[1..n], and it is larger than P [1..2k]. But we assumed that P [1..2k] was the longest. Hence this is a contradiction, and so P′ cannot exist.

Note: The above is gets full marks, but note that it only works assuming k ≥ 2. For the case k ≤ 1: P[2..2k-1] as mentioned in the statement of optimal substructure is not well defined. So we really need to handle this case separately. In this case observe that A[1..n] is given to have a palindrome of length at most 2. So we only need to find an instance whose longest contained palindrome is a (strict) subsequence of P, i.e. is null. So instance A[1,1] satisfies this since we have defined palindromes to have even length.

——–

Optimal substructure 2: Let P[1..2k] be a longest palindrome of A[1..n]. Then one of the following is true:

• P[1..2k] is a longest palindrome of A[1..n-1].

• P[1..2k] is a longest palindrome of A[2..n].

• P[2..2k-1] is a longest palindrome of A[2..n].

Proof: Along the lines in the electronic lesson, and CLR.

(b) Say that an instance Q is relevant to an instance P if the solution to Q can be a part of the solution to P as indicated in the optimal substructure (as you have described it). (i)[5 marks] How many relevant instances does an instance A[1..n] have?

Optimal substructure 1: Every possible way of choosing i, j in the statement of the optimal substructure gives a relevant instance, they must be chosen distinctly from 2..n − 1. Thus the number of relevant instances is \binom{n}{2}.

Optimal substructure 2: There are only 3 relevant instances.

(ii)[5 marks] Suppose that you are given the solutions to all the relevant instances. How will you now determine the optimal solution to A[1..n] (If you like, you may assume that the elements of A come from an alphabet Σ.)?

Let LP S(i, j) denote the longest palindromic subsequence of A[i..j].

Optimal substructure 1: It suffices to check for each i, j, c where c is a character in Σ the following: “Does c appear in A[1..i-1] and A[j+1..n]?”. If the answer to this is yes for some i, j, c then c · LCS(i, j) · c is a palindromic subsequence of A. We just find the longest of these and return it.

Optimal substructure 2: If A[1]=A[n] then LP S(i, j) = A[1] · LP S(i + 1, j − 1) · A[n], else it is the larger of LPS(i+1,j) and LPS(i,j-1).