Program Analysis Assessed Coursework 2

Program Analysis Term 1, 2015

Assessed Coursework 2
Due date: Submit to Engineering and Informatics School Office by 4pm

on Wednesday 9th of December 2015.

Return date: Marked coursework will be available for collection from the Engineering and Informatics School Office on Monday 11th of Jan- uary 2016.

Assessment: Please answer all questions. A total of 100 marks are avail- able. Please note that credit will be given for partially correct an- swers. Submissions may be handwritten or produced with word processing software.

Avoiding misconduct Do not discuss these questions with anyone other than me or one of the other course tutors. If you do not understand the question then ask me or another course tutor for clarification. If you do submit work that is not your own you must explicitly identify the source.

Program Analysis Term 1, 2015 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. (1)  (total , count ) ← Total&CountAbove(A, k, n)
2. (2)  return total ÷ count

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

2. (b)  Express the running time, T (n), of the Total&CountAbove algo- rithm you have given in answer to Question 1a using recur- rences.

Program Analysis Term 1, 2015 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]

Program Analysis Term 1, 2015

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.

Program Analysis Term 1, 2015 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]

Program Analysis Term 1, 2015 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.

v 0/8 v 14

0/5

0/13

s v3 t

0/16

0/8

0/11

0/2

0/12

0/4

v2

0/14

v5

0/10

0/11

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

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

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

4. (d)  Show the residual graph for the network flow given in answer to Question 3c.

   [4 marks]

Program Analysis Term 1, 2015

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

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

7. (g)  Show the residual graph for the network flow given in answer to Question 3f.

   [4 marks]

8. (h)  Whatisthebottleneckedgeofthepath(s,v2,v3,v1,v4,t)intheresid- ual graph you have given in answer to Question 3g?

   [2 marks]

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

10. (j)  Show the residual graph for the network flow given in answer to Question 3i.

    [4 marks]

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

12. (l)  Identifyacutofthenetworkthathasacutcapacityequaltothemax- imum flow of the network.

    [5 marks]