Written Assignment
Question 1
From Introduction to Algorithms ISBN 978 − 0 − 262 − 03293 − 3
Draw the recursion tree for the Merge-Sort procedure presented below on an array of 16 elements. Explain why memoization is ineffective in speeding up a good divide-and-conquer
algorithm such as Merge-Sort.
if p < r then q ←b(p + r)/2c;
Merge-Sort(A,p,q);
Merge-Sort(A,q + 1,r);
Merge(A,p,q,r); end
Algorithm 1: Merge-Sort(A,p,r)
n1 ← q − p + 1; n2 ← r − q;
create arrays L[1..n1 + 1] and R[1..n2 + 1]; for i ← 1 to n1 do
L[i] ← A[p + i − 1]; end for j ← 1 to n2 do
R[j] ← A[q + j]; end
L[n1 + 1] ←∞; R[n2 + 1] ←∞; i ← 1; j ← 1; for k ← p to r do
if L[i] ≤ R[j] then A[k] ← L[i]; i ← i + 1;
end else
A[k] ← R[j]; j ← j + 1; end end
Algorithm 2: Merge(A,p,q,r)
Question 2
Question 8.1.3 in The Design and Analysis of Algorithms
Question 3
From Algorithm Design and Applications ISBN: 9781118335918
Binomial coefficients are a family of positive integers that have a number of useful properties and they can be defined in several ways. One way to define them is as an indexed recursive function, C (n,k), where the C stands for “choices” or “combinations”. In this case, the definition is as follows:
C (n,0) = 1,
C (n,n) = 1,
and, for 0 < k < n,
C (n,k) = C (n − 1,k − 1) + C (n − 1,k)
- Show that, if we don’t use memoization, and n is even, then the running time for computing is at least 2
- Describe a scheme for computing C (n,k) using memoization. Give a big-oh characterization of the number of arithmetic operations needed for computing in this case.
Question 4
From Algorithms ISBN: 9780073523408
Given two strings x = x1,x2 …xn and y = y1,y2 …ym, we wish to find the length of their longest common substring, that is, the largest k for which there are indices i and j with xixi+1 …xi+k−1 = yjyj+1 …yj+k−1. Show how to do this in time O (mn).
Question 5
From Algorithms ISBN: 9780073523408
Counting Heads. Given integers n and k, along with p1,…,pn ∈ [0,1], you want to determine the probability of obtaining exactly k heads when n biased coins are tossed independently at random, where pi is the probability that the ith coin comes up heads. Give an for this task. Assume you can multiply and add two numbers in [0,1] in O (1) time. A O(nlogn) time algorithm is possible.
