1 Consider the binary numbers x 10011011 and y 10111010 De

1. Consider the binary numbers x = 10011011 and y = 10111010. Decomposing x using a = 1001, b = 1011 and y using c = 1011, d = 1010, compute the product xy using the ordinary way and the way done in divide-and-conquer method by forming w₁  = a + b, w₂  = c + d, u = w₁ w₂ , v = ac, w = bd. Recall xy = 2ⁿ v + 2^n/2(u v w) + w. Each multiplication by 2 amounts to a shift. Count the binary operations in each method.

2. You are given an infinite array A[i] in which the first n elements are integers in sorted order and the rest are filled with , You are not given n. Describe an algorithm that takes as input an integer x and finds a position in the array containing x, if such a position exists, in O(log n) time.

3. Solve each of the recurrence relations and give bound for each. You can use the master theorem if applicable.

a.) T(n) = 49T(n/25) + n^3.5log n.

b.) T(n) = T(n) + 1.

4. Find the coefficients of the polynomial of degree 2, p(x) = a₂ x²+ a₁ x + a₀  such that p(1) = 2, p(2) = 1,p(3) = 0.

Solution

Hi, I have answered Q2.

Please repost others in separate post.

Please let me know in case of any issue.

2. You are given an infinite array A[i] in which the first n elements are integers in sorted order and the rest are filled with , You are not given n. Describe an algorithm that takes as input an integer x and finds a position in the array containing x, if such a position exists, in O(log n) time.

Algorithm:
   Since array is sorted, the first thing clicks into mind is binary search, but the problem here is that we don’t know size of array.
   If the array is infinite, that means we don’t have proper bounds to apply binary search. So in order to find position of key, first we find bounds and then apply binary search algorithm.

   Let low be pointing to 1st element and high pointing to 2nd element of array, Now compare key with high index element,
   ->if it is greater than high index element then copy high index in low index and double the high index.
   ->if it is smaller, then apply binary search on high and low indices found.

  
   // Simple binary search algorithm
   int binarySearch(int arr[], int l, int r, int x)
   {
   if (r>=l)
   {
   int mid = l + (r - l)/2;
   if (arr[mid] == x)
   return mid;
   if (arr[mid] > x)
   return binarySearch(arr, l, mid-1, x);
   return binarySearch(arr, mid+1, r, x);
   }
   return -1;
   }
     
   // function takes an infinite size array and a key to be
   // searched and returns its position if found else -1.
   // We don\'t know size of arr[] and we can assume size to be
   // infinite in this function.
   // NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE
   // THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING
   int findPos(int arr[], int x)
   {
   int l = 0, h = 1;
   int val = arr[0];
     
   // Find h to do binary search
   while (val < x)
   {
   l = h; // store previous high
   h = 2*h; // double high index
   val = arr[h]; // update new val
   }
     
   // at this point we have updated low and high indices,
   // thus use binary search between them
   return binarySearch(arr, l, h, x);
   }