Question

Consider the problem where you are given an array of n digits [d_i] and a positive integer b, and you need to compute the value of the number in that base.
In general, you need to compute

dobo dib dib

For example:

(1011)₂ = 1(1) + 1(2) + 0(4) + 1(8) = 11;

(1021)₃ = 1(1) + 2(3) + 0(9) + 1(27) = 34, and

(1023)₄ = 3(1) + 2(4) + 0(16) + 1(64) = 75.

In these examples, I give the digits in the order d₃d₂d₁d₀, which corresponds to how we would normally write these numbers, though you can assume that d_i is in index i of the array for the questions below. (Yes, the indices will be numbered 0 to n - 1, not 1 to n.)

1. Give pseudocode for a divide-and-conquer algorithm that solves this problem by dividing the digit array into two subarrays of (roughly) the same size.

For example, d₅d₄d₃d₂d₁d₀ would be split into d₅d₄d₃ and d₂d₁d₀.

2. Give pseudocode for a divide-and-conquer algorithm that solves this problem by dividing the digit array into two interleaved arrays of (roughly) the same size.

For example, d₅d₄d₃d₂d₁d₀ would be split into d₅d₃d₁ and d₄d₂d₀.

Answer 1

1. Finding the value of function using divide and conquer.

//Before calling this function reverse the array to give you correct results.

int sumArray(int array[],int left,int right,int b) //initialize left and right as -1 if the size of array is 0 and it assuming you have initialized left and right as (1,n)
{
   int sum=0,index;
   if(left==-1 && right==-1)
       return 0;
   else if(left==right)
   {
       sum=pow(b,left)*array[0]; //sum will give you (b^i)*d
   }
   //Divide and conquer part
   int mid=right/2;
   int lsum=sumArray(array,left,mid,b);
   int rsum=sumArray(array,mid+1,right);
   return lsum+rsum;
}

2. Using the same method as above to divide and conquer

int sumArray(int array1[],int array2[],int size,int b) //array 1 will store the values and array 2 will store indices
{
   int sum=0,int array3[],array4[],pos=0;
   if(size==0)
       return 0;
   else if(siz==1)
   {
       sum=pow(b,array2[0])*array1[0]; //sum will give you (b^i)*d
   }
   //Divide and conquer part
   pos=0;
   for(int i=0;i<n;i++)
   {
       if(i%2==0)
       {
           array3[pos]=array1[i];
           array4[pos]=array2[i];
       }
   }
   int sum1=sumArray(array3,array4,i,b);//this will call sum function for 1st interleaved array
   for(int i=0;i<n;i++)
   {
       if(i%2!=0)
       {
           array3[pos]=array1[i];
           array4[pos]=array2[i];
       }
   }
   int sum2=sumArray(array3,array4,i,b);//this will call sum function for 2nd interleaved array
   return sum1+sum2;
}