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.