General instructions

1.  Answer all of the questions.

2.  Show your workings where appropriate. You can still get credit for a question with an incorrect final answer if your workings show that you understood what the problem was and how to solve it.

3.  Do not copy the work of another student. Plagiarism is a very serious matter. Discussion between students is to be encouraged – copying is an academic disciplinary matter.

4.  Check that you provide any working or information that the question asks for.

5.  Hand your submission in on time. There are penalties for late submission.

6.  If I cannot read your submission, I cannot mark it. It is your responsibility to    ensure that the presentation of your submission is appropriate for a University student.

7.  Do not forget to state units if they are relevant and apply to a question.

8.  You should use any calculating aids your feel appropriate to help you solve the problems including, although not limited to, calculators, spreadsheets   such as Excel and MATLAB.

9.  If you do not understand the questions, you can get help at the workshop sessions.

10. This assignment is marked out of a total of 100

Q1)

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 A 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.

FindAverageAndSum(a1, … , an )

Input: A sequence of real values A = (a1, … , an ) .

Output:, A 2-tuple (average, sum) containing the average (average) of all the values and the sum (sum) of all the values of the elements in A .

Your recursive algorithm should use a single recursive structure to find the average and sum 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.

[5 marks]

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

algorithm when called using the sequence = (12, 8, −4, 3, −6, −1).

[5 marks]

(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.

[4 marks]

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

Q2)

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:

T(n) = T(n − 2) + 2(n − 2) + c1

T(2) = c2

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

Determine the running time complexity of this recursive algorithm. To get the full  marks, your analysis should be as complete as possible. To get an idea of how to perform a complete analysis, refer to the example recursive algorithm analysis on Canvas. 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 T(n) .

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

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

(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, … . k) is given by the formula:

m = 

[20 marks]

Q3)

This question is concerned with dynamic programming.

A bottom up dynamic programming method is to be used to solve the subset sum problem. The problem is to find the optimal sum of weighted requests from a set of requests A subject to a weight constraint W. The set of weighted requests A = {a1, a2, a3, a4, a5, a6 } can be summarised as following:

The maximum weight constraint is 13.

Using the following algorithm (reproduced from the notes on Canvas):

(a) Produce a table showing the space of the problem and all of the sub

problems, and use that table to determine the optimal subset sum of  requests when the weight constraint of 13 is applied. The table should take the form of a matrix with 7 rows (values of i in the range 0 to 6     inclusive) and 14 columns (values of w in the range 0 to 13 inclusive).

[20 marks]

Q4)

In this question, we consider the operation of the Ford-Fulkerson algorithm on the network shown overleaf:

Each edge is annotated with the current flow (initially zero) and the edge’s        capacity. In general, a flow of x along an edge with capacity y is shown as x/y .

(a) Show the residual graph that will be created from this network with the       given (empty) flow. In drawing a residual graph, to show a forward edge    with capacity x and a backward edge with capacity y , annotate the original edge ;  .

[4 marks]

(b) What is the bottleneck edge of the path (s, v1, v3, v5, t) in the residual graph you have given in answer to part (a) ?

[2 marks]

(c) Show the network with the flow (s, v1, v3, v5, t)  that results from           augmenting the flow based on the path of the residual graph you have given in answer to part (a).

[3 marks]

(d) Show the residual graph for the network flow given in answer to part (c).    [4 marks]

(e) What is the bottleneck edge of the path (s, v3, v4, t)  in the residual graph you have given in answer to part (d) ?

[2 marks]