University of Sussex
Program Analysis G6017
Coursework 2
Due: XVAC Week 11 Thursday 21 December 2023 by 4PM
Format: Electronic submissions only by Canvas. You should write your
answers in the blanks in your answer sheet we have provided for
you and submit this answer sheet only. If you want to do your
work in a handwritten form, please print the answer sheet, fill it
properly, and then again scan it and upload the work as a single
PDF document. No paper copies of this submission will be
accepted.
Weighting 50.0 % of the coursework element for this module
25.0 % of the overall module mark
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 𝐴 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.
[5 marks]
(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).
[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.
[6 marks]
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:
𝑇(𝑛) = 𝑇(𝑛 − 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. 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 𝑇(𝑛).
(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:
∑ 𝑚
𝑚=𝑘
𝑚=1
=
𝑘(𝑘 + 1)
2
[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 𝐴 subject to a weight constraint W. The set of weighted requests 𝐴 =
{𝛼1, 𝛼2, 𝛼3, 𝛼4, 𝛼5, 𝛼6} can be summarised as following:
Request 𝒘(𝜶𝒊)
𝛼1 2
𝛼2 2
𝛼3 1
𝛼4 7
𝛼5 7
𝛼6 1
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 𝑖 in the range 0 to 6
inclusive) and 14 columns (values of 𝑤 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 𝑥 along an edge with capacity 𝑦 is shown as 𝑥/𝑦.
(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 𝑥 and a backward edge with capacity 𝑦, annotate the original
edge 𝑥⃗; 𝑦⃖ .
[4 marks]
(b) What is the bottleneck edge of the path (𝑠, 𝑣1, 𝑣3, 𝑣5,𝑡) in the residual
graph you have given in answer to part (a) ?
[2 marks]
(c) Show the network with the flow (𝑠, 𝑣1, 𝑣3, 𝑣5,𝑡) 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 (𝑠, 𝑣3, 𝑣4,𝑡) in the residual graph
you have given in answer to part (d) ?
[2 marks]
(f) Show the network with the flow that results from augmenting the flow
based on the path (𝑠, 𝑣3, 𝑣4,𝑡) of the residual graph you have given in
answer to part (d).
[3 marks]
(g) Show the residual graph for the network flow given in answer to part (f).
[4 marks]
(h) What is the bottleneck edge of the path (𝑠, 𝑣2, 𝑣3, 𝑣1, 𝑣4,𝑡) in the residual
graph you have given in answer to part (g) ?
[2 marks]
(i) Show the network with the flow that results from augmenting the flow
based on the path (𝑠, 𝑣2, 𝑣3, 𝑣1, 𝑣4,𝑡) of the residual graph you have given
in answer to part (g).
[3 marks]
(j) Show the residual graph for the network flow given in answer to part (i).
[4 marks]
(k) Show the final flow that the Ford-Fulkerson Algorithm finds for this
network, given that it proceeds to completion from the flow rates you have
given in your answer to part (i), and augments flow along the edges
(𝑠, 𝑣1, 𝑣3,𝑡) and (𝑠, 𝑣2, 𝑣5,𝑡).
[4 marks]
(l) Identify a cut of the network that has a cut capacity equal to the maximum
flow of the network.
[5 marks]
Dr Kingsley Sage
Khs20@sussex.ac.uk
November 2023
END.