induction and recursion to develop an algorithm

Q1) A simple method that was invented around 1,200 years ago to multiply two non-negative integers X and Y can be represented by a 2-column table where the first row contains the values of X and Y in its first and its second columns; respectively, and every successive row below that is obtained from the one above it by doubling the value in the 1st column and dividing by 2 the value in the second column (with the result of division being rounded down, if needed, to drop the fraction 0.5 so as to obtain an integer value). The last row will have a value equal to 1 in its second column, and the final result X*Y is obtained by going over the rows, and adding together each value from the first column if the corresponding value in the second column of the same row is odd. The example below shows the multiplication of 7 by 11. ------------------ X Y ------------------ 7 11 14 5 28 2 56 1 ------------------ 7 * 11 = 7 + 14 + 56 = 77 Use this method to multiply each pair below: a. X= 8 and Y= 11 b. X= 11 and Y= 13 c. X=1024 and Y= 1024 Q2) Use both induction and recursion to develop an algorithm to solve each problem stated below. a) Computing the factorial function Fac(n); b) Searching a non-sorted array A of n integers. Q3) Let A denote an array whose elements represent an integer in some number system, e.g., in binary, octal, etc. To convert the number in A into an equiavelnt decimal number M, we use the formula: M= A[0] + A[1] * (b^1) + A[2] * (b^2) + ... + A[n-1] * (b^(n-1)). Where b is called the base or radix, e.g., b= 2 if the number is binary; and b= 8 if the number is octal, etc. For example, if A contains a binary number consisting of 4 digits A[0]=1, A[1]=0, A[2]=0 and A[3]=1, then the corresponding decimal number M would be M = 1 + 0 * (2^1) + 0 * (2^2) + 1 * (2^3) = 9. Write an algorithm by induction or recursion which receives the array A (i.e., its elements and size), and the base b, and which returns a decimal number equivalent to A. Your algorithm should run in O(n) time. You can name your algorithm: convert2decimal(int A[], int n, int b). Q4) Write a program to implement your solution for Q3. Test your program using at least 6 different inputs (i.e., 6 arrays A of varying length). You can limit your algorithm only to convert binary numbers (if you wish). In the document to be uploaded, include a copy of your your program, each input you tested, and the decimal number obtained as output.