Consider the problem where you are given an array of n digits [di] and a positive...

Transcribed Image Text:

Consider the problem where you are given an array of n digits [di] and a positive integer b, and you need to compute the value of the number in that base. In general, you need to compute For example: n-1 x = = dobº + d₁b¹ + ….. + dn-1b-1 = [d₂b². i=0 (1011)2 = 1(1) + 1(2) + 0(4) +1(8) = 11, (1021)31(1) + 2(3) +0(9)+1(27) = 34, and (1023)4 = 3(1) + 2(4) + 0(16) + 1(64) = 75. In these examples, I give the digits in the order d3d2d1do, which corresponds to how we would normally write these numbers, though you can assume that d; 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 prob- lem by dividing the digit array into two subarrays of (roughly) the same size. For example, d5d₁d3d2d₁do would be split into d5d4d3 and d2d1do. Consider the problem where you are given an array of n digits [di] and a positive integer b, and you need to compute the value of the number in that base. In general, you need to compute For example: n-1 x = = dobº + d₁b¹ + ….. + dn-1b-1 = [d₂b². i=0 (1011)2 = 1(1) + 1(2) + 0(4) +1(8) = 11, (1021)31(1) + 2(3) +0(9)+1(27) = 34, and (1023)4 = 3(1) + 2(4) + 0(16) + 1(64) = 75. In these examples, I give the digits in the order d3d2d1do, which corresponds to how we would normally write these numbers, though you can assume that d; 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 prob- lem by dividing the digit array into two subarrays of (roughly) the same size. For example, d5d₁d3d2d₁do would be split into d5d4d3 and d2d1do.