$[20\%]$ Design a recursive algorithm to solve each of the following problems and

analyse the worst$-$case time complexity of your algorithm. $[$Non$-$recursive

algorithms will score $0$ marks.$]$

$($a$)$ Given an array of numbers $A[1..n],$ find the average of all numbers in the

array. For example, if the given array $A$ is $1\mathrm{.}5,2,3\mathrm{.}5,-0\mathrm{.}5,6\mathrm{.}5,$ the output

of the algorithm should be $2\mathrm{.}6.$

$($b$)$ Given an array of integers $A[1..n],$ reverse the entries in the array. You are

only allowed to use constant amount of extra storage $($e$.$g$.$ if you use

another array of $n$ entries in your algorithm, you score $0$ marks$).$ For

example, if the given array $A$ is $10,-2,3,4,5,$ the output of the algorithm

should be $5,4,3,-2,10.$

$($b$)$ Given an integer $n(0),$ output all binary strings of length $2n$ such that

the sum of the first $n$ bits $=$ the sum of the second $n$ bits. For example, if $n$

$=2,$ then the algorithm should output:

$0000,0101,0110,1001,1010,1111$