# 程序代写代做代考 algorithm /Users/davidw/Documents/teach/exams/PA/16/.texpadtmp/exam.dvi

/Users/davidw/Documents/teach/exams/PA/16/.texpadtmp/exam.dvi

Candidate Number

G6017

THE UNIVERSITY OF SUSSEX

BSc SECOND YEAR EXAMINATION

January 2016 (A1)

PROGRAM ANALYSIS

Assessment Period: January 2016 (A1)

DO NOT TURN OVER UNTIL INSTRUCTED TO

BY THE CHIEF INVIGILATOR

Candidates should answer TWO questions out of THREE. If all three

questions are attempted only the first two answers will be marked.

The time allowed is ONE AND A HALF hours.

Each question is worth 50 marks.

At the end of the examination the question paper and/or answer book,

used or unused, will be collected from you before you leave the

examination room.

G6017 PROGRAM ANALYSIS

1. (a) Consider the following algorithm.

Algorithm Alg1(X):

Input: a list of reals X = (x1, . . . , xn) where n ≥ 1

Output: a real

1: t← 0

2: p← 1

3: for i← 1 to n do

4: t← t+ xi

5: j ← i

6: while j ≤ n and xj 6= 0 do

7: p← p× xj

8: j ← j + 1

9: return p÷ t

i. When Alg1 is given an input of length n, how many times is line 4

executed? Justify your answer, and consider whether the answer

depends on the values within the sequence X. [5 marks]

ii. When Alg1 is given an input of length n, how many times is line 7

executed? Justify your answer, and consider whether the answer

depends on the values in X. [5 marks]

iii. What can you say about the asymptotic running time of Alg1?

[5 marks]

(b) Suppose that you have been told that AlgorithmA has an asymptotic

running time that is Ω(n3).

i. Precisely what do you know about AlgorithmA? [10 marks]

ii. Is it possible that the asymptotic running time of AlgorithmA is also

θ(n4)? [10 marks]

PROGRAM ANALYSIS G6017

(c) Given a list of n reals X = (x1, . . . , xn), let the mean x̄, and standard

deviation s of the values in X be given by the following formula.

x̄ =

1

n

n

∑

i=1

xi

s =

√

√

√

√

1

n− 1

n

∑

i=1

(xi − x̄)2

i. Complete the algorithm in pseudo-code that solves the problem of

calculating the standard deviation of a list X of n reals.

Algorithm StandardDeviation(X) : real

Input: a list of reals X = (x1, . . . , xn) where n ≥ 1

Output: the standard deviation of the values in X

[10 marks]

ii. Discuss the asymptotic running time of your algorithm. [5 marks]

G6017 PROGRAM ANALYSIS

2. You are a supervisor at a children’s summer camp which runs a variety of

activities each day, some of which run in parallel. Each evening the children

sign up for a selection of the activities on offer the following day. Thus, each

morning you know which activities are running that day, how many children

are taking part, and when each activity will start and end.

Your pay for each day is the total of what you earn from each of the activities

you supervise. You receive £10 for each activity irrespective of how long it is,

or how many children have signed up.

Fortunately, you have the first opportunity to select the activities you will

supervise each day. Your only constraint is that you can only look after one

group of children at a time. The lengths of activities can vary considerably,

so making a good selection of activities can make a substantial difference

to your income. This question concerns the problem of determining the best

choice of activities for you to supervise each day.

(a) Describe a greedy method that could be applied to this problem, but

which is not guaranteed to always produce an optimal solution. Give an

example of a problem instance where the greedy method you describe

would not produce an optimal solution. [10 marks]

(b) Describe a greedy method that could be applied to this problem that is

guaranteed to always produce an optimal solution. [5 marks]

(c) Discuss the asymptotic running time of an algorithm that is based on

the greedy method that you have described in answer to Question 2b.

[10 marks]

(d) Suppose that we changed the scenario, so that the amount you are paid

for running an activity is determined by the size of the group and the

length of the session. In particular, the value in pounds for an activity

is the number of hours that the activity lasts multiplied by the number of

children taking part. So for a two hour session involving eight children

you would be paid £16.

Show that the greedy method that you used in the algorithm given in

answer to Question 2b would not produce an optimal solution to this

revised problem. [10 marks]

(e) Describe in words an algorithm that would find the optimal solution to

the problem that arises in the revised scenario described in Question 2d.

[10 marks]

(f) Discuss the asymptotic running time of the algorithm that you have given

in answer to Question 2e. [5 marks]

PROGRAM ANALYSIS G6017

3. Consider the following network and flow rate. Note that an edge labelled

x/y indicates the rate of flow along the edge is x units of flow, and that the

capacity of the edge is y units of flow. For example, the edge from s to v1 has

a capacity of 10 and a flow rate of 4.

s

v1

v2

v3

v4

v5

t

4/10

6/8

1/3

3/9

4/5

2/4

1/5

6/7

2/9

8/12

source sink

(a) Describe a simple method that can be used to determine the amount

of flow that runs from the source to the sink in a network, and use this

method to determine the flow shown in the above network. [5 marks]

(b) Draw the residual graph that is produced from the above network and

flow rate. Make sure that you clearly distinguish between forward and

backwards edges. [10 marks]

(c) Consider the path (s, v1, v3, v2, v5, t) in the residual graph you have given

in answer to Question 3b. This path includes one backward edge which

runs from v3 to v2. Explain why backward edges are included in residual

graphs. [5 marks]

(d) What is the significance of the bottleneck edge of a path in a residual

graph? In the residual graph you have given in answer to Question 3b

what is the bottleneck edge of the path (s, v1, v3, v2, v5, t)? [5 marks]

(e) Show the network and flow that results from augmenting the flow of the

network using the path (s, v1, v3, v2, v5, t) in the residual graph you have

given in answer to Quesiton 3b. [10 marks]

G6017 PROGRAM ANALYSIS

(f) Residual graphs can have more than one source to sink path. Discuss

whether the decision as to which order these paths are chosen for flow

augmentation can have an impact either on the maximum flow rate that

is ultimately established, or on the length of time that the algorithm takes

to run. [10 marks]

(g) Explain why an algorithm that solves the network flow problem might

be useful for graph clustering. Graph clustering involves grouping the

vertices in a weighted graph, where weights on edges correspond to a

measure of how closely vertices are associated. The goal is to find a

way to cluster the vertices into groups of vertices such that vertices in

the same group are closely associated. [5 marks]

End of Paper