Personal project Q5.

This question is concerned with the design and analysis of recursive algorithms.

You are given a problem statement as shown below. This problem is concerned with performing calculations on a sequence of real numbers. Whilst this could be done using a conventional loop-based approach, your answer must be developed using a recursive algorithm. No marks will be given if your answer uses loops.

(1, ... , ) such that > 1

Input: A sequence of real values = (1, ... , ). Output:, A 2-tuple (, ) containing the average () of all the values and the product () of all the values of the elements in .

Your recursive algorithm should use a single recursive structure to find the average and product values, and should not use two separate instances of a recursive design. You should not employ any global variables.

(a) Produce a pseudo code design for a recursive algorithm to solve this problem.

(b) Draw a call-stack diagram to show the application of your recursive

algorithm when called using the sequence = (24, 8, 4, 6, 6, 3).

(c) Write down the set of recurrence equations for your recursive algorithm. Remember that one of the equations should correspond to the recursive algorithm base case.

(d) Using the recurrence equations you gave in your answer for part (c), determine the running time complexity of your recursive algorithm.

Personal project Q8.

A piece of code implementing a recursive algorithm has been produced, and a student has analysed the recurrences. They have produced the recurrence equations as shown below:

() = ( 3) + 2( 3) + 1 (3) = 2

So the recursive algorithm features a base case when the size of the problem is = 3. The values of 1 and 2 are constants. You should assume the initial value of (the size of the problem) is divisible by 3.

Determine the running time complexity of this recursive algorithm. To get the full marks, your analysis should be as complete as possible. You can verify your analysis by modelling the recurrence equations in a program like Excel or MATLAB. Your answer must include:

(a) Evidence of at least two cycles of substitutions to establish the running time function ().

(b) A clear statement of the generalisation of that pattern to iterations of the recursive step.

(c) A statement of the number of iterations required to solve a problem of size .

(d) A statement of the final overall running time complexity that follows from your previous algebra.

You may find it useful to know that the formula for a sum of an arithmetic sequence of numbers of the form (1,2,3, ... . ) is given by the formula:

_m=1 ^m=k m = (k+1) /2