[Solved] CSCE310 Homework 4

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)

n₁ q p + 1; n₂ r q;

create arrays L[1..n₁ + 1] and R[1..n₂ + 1]; for i 1 to n₁ do

L[i] A[p + i 1]; end for j 1 to n₂ do

R[j] A[q + j]; end

L[n₁ + 1] ; R[n₂ + 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 dont 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 = x₁,x₂ x_n and y = y₁,y₂ y_m, 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 x_ix_i+1 x_i+k1 = y_jy_j+1 y_j+k1. Show how to do this in time O (mn).

Question 5

From Algorithms ISBN: 9780073523408

Counting Heads. Given integers n and k, along with p₁,,p_n [0,1], you want to determine the probability of obtaining exactly k heads when n biased coins are tossed independently at random, where p_i 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.