Program Analysis
University of Sussex
Program Analysis G6017
Coursework 2
Due: Semester 1 Week 11 Wednesday 9 December by 4PM
Format: Electronic submissions only by Canvas. Your submission does
not need to be typed, although handwritten scripts must be
legible. If you do the work in a handwritten form, please 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
12.5 % 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 inco
ect 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
e 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, … , ??)
Input: A sequence of real values ? = (?1, … , ??)
Output: Where no element in A is equal to 0, a pair (???, ???????) containing the
sum and product values of the elements in A. Where an element in A is equal to
zero, the output should be the pair (????, ????)
Your recursive algorithm should use a single recursive structure to find the sum
and product values, and should not use two separate instances of a recursive
design.
(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 = (8,3,1,3,2,6) and the
sequence = (8,3,0,3,2,6) .
[5 marks]
(c) Write down the set of recu
ence equations for your recursive algorithm.
The recu
ence equations should take a form like this:
?(?) = {
(??????????) ?? (??????????)
(??????????) ??ℎ??????
The “otherwise” case here refers to the recursive algorithm base case.
[4 marks]
(d) Using the recu
ence 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 recu
ences. They have produced the recu
ence
equations as shown below:
?(?) = ?(? − 1) + 2(? − 1) + ?1
?(2) = ?2
So the recursive algorithm features a base case when the size of the problem is
? = 2. The values of ?1 and ?2 are constants.
(a) 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 recu
ence equations in a program like Excel or MATLAB.
You will 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 1
?3 3
?4 5
?5 1
?6 3
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
equests when the weight constraint of 13 is applied. The table should
take the form of a matrix with 6 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 below:
Each edge is annotated with the cu
ent 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
ased 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
ased 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
XXXXXXXXXX
September 2020
END.
mailto: XXXXXXXXXX