Topic ALGORITHMS Consider the problem of evaluating polynomi

Consider the problem of evaluating polynomial f(x) = a_n-1x^n-1 + ... + a_1x + a_0 at x = c, i.e. compute f(c). Write a divide and conquer algorithm that computes f(c) such that the division of the problem instance is into two sub problems of roughly equal size. That is treat f(x) as an operation on (a_n-1, ...a_1, a_0) to be evaluate at x = c. Determine the recurrence relation? Determine its running time. Suppose you have w many lists, each list has n elements and is sorted. (a) Consider a loop-based w-way merge that merge in right-to-left manner, merging two lists at a times.

Solution

(2)divide and conquer:

divcon(arr[],1,r)

if r>1

(a)finding the mid-point to divide the array into 2 halves

middle m = (l+r)/2

(b)call divcon for firsthalf

divcon(arr,l,m)

(c)call divcon for seconhslf:

divcon(arrm,m+1,r)

merge two halves

divcon(arr,l,m,r)

running time:bigoh(nlogn)

(2)assume that both arrays are sorted in ascending orderA[0...m-1]and B[0-n-1].

1)introduce i,j and traverse arrays A,B,which are sorted lists divided into arrays

2)introduce index-k to store position of first cell in resulting array.

3)by default i=j=k=0

4)if both indices are in range(i<m and j> n),choose min(a[i],b[j])

increase k and index of array locate min value and repeat step2

5)copy the rest values,to the resulting array according index sill in range.

complexity is big=oh(n+m).