Assessed Coursework 2
Due date: Submit to Engineering and Informatics School Office by 4pm
on Wednesday 13th of December 2017.
Return date: Marked coursework will be available for collection from the
Engineering and Informatics School Office on Monday 8th of Jan-
uary 2018.
Assessment: Please answer all three questions. A total of 100 marks are
available. Please note that credit will be given for partially correct
answers. Submissions may be handwritten or produced with word
processing software.
Avoiding misconduct If you do submit work that is not your own you
must explicitly identify the source.
1
1. Consider the following algorithm.
AverageAbove(A, k) :
Inputs: a sequence A = (a1, . . . , an) of reals,
a real k
Output: the average of those values in A that are ≥ k
(1) (total , count)← Total&CountAbove(A, k, n)
(2) return total ÷ count
(a) Give the pseudocode for the algorithm Total&CountAbove that
is used in line (1) of AverageAbove.
*** It is essential that the algorithm you give is recursive. ***
Your algorithm should not contain any loops.
Here is the specification of Total&CountAbove:
Total&CountAbove(A, k, i) :
Inputs: a sequence A = (a1, . . . , an) of reals,
a real k,
an integer i, where 0 ≤ i ≤ n
Output: a pair consisting of
the sum of values in (a1, . . . , ai) that are ≥ k,
the number of values in (a1, . . . , ai) that are ≥ k
Note that, i, the third parameter of Total&CountAbove is needed
to record which part of the sequence A is being considered in a
given recursive call.
Also, note that when i = 0, it is the empty subsequence of A
that is being considered.
[10 marks]
(b) Express the running time, T (n), of the Total&CountAbove algo-
rithm you have given in answer to Question 1a using recur-
rences.
2
Hint: your answer should take the following form:
T (n) =
{
〈expression〉 if 〈expression〉
〈expression〉 otherwise
[10 marks]
(c) Solve the recurrences you have given in answer to Question 1b
to find the running time of both the Total&CountAbove and Av-
erageAbove algorithms. You should show the full details of
how your solved the recurrences.
[10 marks]
3
2. Last month, you had a chat with your friend Amy at a party. She
mentioned that she had recently taken over as one of the trustees
of a charity. As someone who enjoys programming, she has volun-
teered to set up a database containing the details of the several thou-
sand people who are registered as so-called ‘friends’. You talked to
her about some of the exciting things that you were learning in your
Program Analysis module, and offered to help.
Yesterday, Amy called and explained that she had managed to track
down a file on the charity’s ageing computer that contains data that
the charity has about the names and addresses of its friends.
Amy’s problem, and the reason she has called you, is that she hasn’t
been able to work out how to write code that will extract anything
useful from the file. For some strange reason, the file doesn’t con-
tain any non-alphanumeric characters (i.e. the file has absolutely
no punctuation or whitespace characters, just containing letters and
digits) and is entirely lowercase.
Without anything that marks the end of one word (or token) and
the start of another, Amy hasn’t been able to figure out any way of
splitting up the contents so that she can extract the information she
wants from the file.
Here is the start of the file:
“jonathanpsmiththegablesturnersgreensussexjorice5westst…”
The particular thing that she wants your help with is the problem
of separating out each of the tokens (words, numbers, abbreviations,
etc). She is confident that once that has been done she can deal with
working out how to distinguish the names from the addresses and
then populate the database.
Luckily, you were able to help her. You started to tell her how she can
use Dynamic Programming to solve the problem, but you could see
that she was having difficultly understanding what you were get-
ting at. As a result, you both agreed that the best way forward was
for you to send her an email explaining in detail the way that the
problem can be approached. Since she wants to write all of the code
herself, and was keen to learn how these kinds of problems can be
solved, you agree that you would explain what is needed in words,
and would describe the algorithm in pseudocode.
Compose the email that you would send to Amy. Don’t forget that
she has a degree in Maths, so it is fine to present things formally.
4
Your email should cover the following issues:
• You need to explain the role of a string scoring function that
measures how likely a string is to be part of a name or address.
It is fine to leave it to Amy to decide on the details as to how
such a scoring function is to be defined.
• Using the string scoring function, you should give a specifica-
tion of the problem, i.e. the mapping from an input to an output.
• You should explain how, in general, a problem instance can be
decomposed into a collection of sub-problems. This involves
describing the space of subproblems that must be solved, and
how solutions to subproblems are stored in a table. Illustrate
this with an example involving the string “jorice5westst”.
• You should specify the order in which the sub-problems are
solved.
• You should indicate how the simplest sub-problems are solved,
and explain how solutions to the remaining sub-problems are
determined based on the solutions to previously solved sub-
problems.
• You should describe the asymptotic running time of the algo-
rithm.
• Finally, you should explain how an optimal solution is recov-
ered from the table that holds solutions to subproblems.
Comment: You will have noticed that the requirements for this ques-
tion are less specified that usual — this is intentional. You are being
asked to exercise your judgement as to how to go about composing
this email, bearing in mind that there are many good ways to ap-
proach it.
[30 marks]
5
3. We will look at how the Ford-Fulkerson Algorithm operates on the
following network.
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.
s
v1
v2
v3
v4
v5
t
0/16
0/12
0/8
0/8
0/5
0/11
0/4 0/14
0/13
0/2
0/11
0/10
(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 −→x ;←−y .
[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 Question 3a?
[2 marks]
(c) Show the network with the flow that results from augmenting the
flow based on the path (s, v1, v3, v5, t) of the residual graph you have
given in answer to Question 3a.
[3 marks]
(d) Show the residual graph for the network flow given in answer to
Question 3c.
[4 marks]
6
(e) What is the bottleneck edge of the path (s, v3, v4, t) in the residual
graph you have given in answer to Question 3d?
[2 marks]
(f) Show the network with the flow that results from augmenting the
flow based on the path (s, v3, v4, t) of the residual graph you have
given in answer to Question 3d.
[3 marks]
(g) Show the residual graph for the network flow given in answer to
Question 3f.
[4 marks]
(h) What is the bottleneck edge of the path (s, v2, v3, v1, v4, t) in the resid-
ual graph you have given in answer to Question 3g?
[2 marks]
(i) Show the network with the flow that results from augmenting the
flow based on the path (s, v2, v3, v1, v4, t) of the residual graph you
have given in answer to Question 3g.
[3 marks]
(j) Show the residual graph for the network flow given in answer to
Question 3i.
[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 answer to Question 3i, and augments flow along the
edges (s, v1, v3, t) and (s, v2, v5, t).
[4 marks]
(l) Identify a cut of the network that has a cut capacity equal to the max-
imum flow of the network.
[5 marks]
7