CANDIDATE: please

attach Student Support

Unit sticker, if relevant.

THE UNIVERSITY OF SUSSEX

BSc and MComp SECOND YEAR EXAMINATION

PROGRAM ANALYSIS
G6017
You must start this exam at the time published in your Sussex Direct
Timetable, as indicated below.
Once started you will have a set exam duration in which to complete it, if you
have not completed it before the end of the duration the exam will close.

If you have extra time due to Reasonable Adjustments this is additional to the
exam duration below and has been added to your assessment on Canvas.

Date: Friday, 13 January 2023

Exam Start Time: 09:30
Exam Duration: 2.5 hours (including time for scanning, collating, uploading)

Candidates should answer TWO questions out of THREE

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

Each question is worth 50 marks.

Write or type your answers on A4 paper, scan and save as a single PDF file
and upload to Canvas

Please make sure that your submission includes the following:

Your candidate number (Do not put your name on your paper)
The title of the module and the module code

Read Academic Integrity Statement

You MAY access online materials, including lecture notes during this examination.
You must complete this assessment on your own and in your own words. DO
NOT discuss this assessment with others during the exam. By submitting this
assessment you confirm that your assessment includes no instances of academic
misconduct, for example plagiarism or collusion. Any instance of academic
misconduct will be thoroughly investigated in accordance with our academic
misconduct regulations.
G6017 Program Analysis

1.

(a) Precisely specify the conditions under which the following algorithm returns
true, and then discuss, in detail, the running time of the algorithm. If you think
it has different best- and worst-case running times then these should be
considered separately, and you should explain the conditions under which
best and worst-cases arise. You must fully explain your answer and use O, 
and  appropriately to receive full marks.

Algorithm Ex1 �(𝑎𝑎1 , … 𝑎𝑎𝑛𝑛 ), (𝑏𝑏1 , … , 𝑏𝑏𝑛𝑛 )�

𝑘𝑘 ← 0
𝑗𝑗 ← 1
while 𝑗𝑗 ≤ 𝑛𝑛 do
If 𝑎𝑗𝑗 == 𝑏𝑏𝑛𝑛−𝑗𝑗+1
𝑘𝑘 ← 𝑘𝑘 + 1
𝑗𝑗 ← 𝑗𝑗 + 1

return 𝑘𝑘 == 𝑛𝑛

[10 marks]

(b) Precisely specify the conditions under which the following algorithm returns
true, and then discuss, in detail, the running time of the algorithm. If you think
it has different best- and worst-case running times then these should be
considered separately, and you should explain the conditions under which
best and worst-cases arise. You must fully explain your answer and use O, 
and  appropriately to receive full marks.

Algorithm Ex2 �(𝑎𝑎1 , … 𝑎𝑎𝑛𝑛 )�, 𝑠𝑠𝑠𝑠𝑠𝑠ℎ 𝑡 ℎ𝑎𝑎𝑡𝑡 𝑛𝑛 ≥ 3

𝑞𝑞 ← 𝑡𝑡𝑡𝑡𝑠𝑠𝑡𝑡
𝑖𝑖 ← 1
while 𝑖𝑖 ≤ 𝑛𝑛 − 2 and 𝑞𝑞 == 𝑡𝑡𝑡𝑡𝑠𝑠𝑡𝑡 do
𝑠𝑠𝑠𝑠𝑏𝑏𝑠𝑠𝑠𝑠𝑡𝑡𝑎𝑎𝑠𝑠 ← 0

for 𝑗𝑗 ← 0 𝑡𝑡𝑠𝑠 2 do
𝑠𝑠𝑠𝑠𝑏𝑏𝑠𝑠𝑠𝑠𝑡𝑡𝑎𝑎𝑠𝑠 ← 𝑠𝑠𝑠𝑠𝑏𝑏𝑠𝑠𝑠𝑠𝑡𝑡𝑎𝑎𝑠𝑠 + 𝑎𝑎𝑖 +𝑗𝑗

If 𝑠𝑠𝑠𝑠𝑏𝑏𝑠𝑠𝑠𝑠𝑡𝑡𝑎𝑎𝑠𝑠 == 0
𝑞𝑞 ← 𝑓𝑓𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡

𝑖𝑖 ← 𝑖𝑖 + 1
return 𝑞𝑞

[10 marks]

2
G6017 Program Analysis

(c) Precisely specify the conditions under which the following algorithm returns
true, and then discuss, in detail, the running time of the algorithm. If you think
it has different best- and worst-case running times then these should be
considered separately, and you should explain the conditions under which
best and worst-cases arise. You must fully explain your answer and use O, 
and  appropriately to receive full marks.

Algorithm Ex3 (𝑠𝑠, 𝑠𝑠)

𝑠𝑠 is a balanced binary search tree containing integer number values and 𝑠𝑠 is an

integer. Each node in 𝑠𝑠 has two child nodes, either a numeric value or the value
𝑛𝑛𝑠𝑠𝑠𝑠𝑠𝑠 to indicate the lack of a child value.

𝑛𝑛𝑠𝑠𝑛𝑛𝑡𝑡 ← 𝑡𝑡𝑠𝑠𝑠𝑠𝑡𝑡(𝑠𝑠)

while (𝑛𝑛𝑠𝑠𝑛𝑛𝑡𝑡 ! = 𝑛𝑛𝑠𝑠𝑠𝑠𝑠𝑠 )

if 𝑛𝑛𝑠𝑠𝑛𝑛𝑡𝑡. 𝑣𝑣𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡 == 𝑠𝑠
return 𝑡𝑡𝑡𝑡𝑠𝑠𝑡𝑡
else if 𝑠𝑠 < 𝑛𝑛𝑠𝑠𝑛𝑛𝑡𝑡. 𝑣𝑣𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡
𝑛𝑛𝑠𝑠𝑛𝑛𝑡𝑡 = 𝑛𝑛𝑠𝑠𝑛𝑛𝑡𝑡. 𝑠𝑠𝑡𝑡𝑓𝑓𝑡 𝑙𝑙ℎ𝑖𝑖𝑠 𝑛𝑛𝑖𝑖𝑠𝑠𝑛𝑛𝑡𝑡
else
𝑛𝑛𝑠𝑠𝑛𝑛𝑡𝑡 = 𝑛𝑛𝑠𝑠𝑛𝑛𝑡𝑡. 𝑡𝑡𝑖𝑖𝑔𝑔ℎ𝑡𝑡𝑙𝑙ℎ𝑖𝑖𝑠𝑠𝑛𝑛𝑖𝑖𝑠𝑠𝑛𝑛𝑡𝑡

return 𝑓𝑓𝑎𝑎𝑠𝑠𝑠𝑠𝑡𝑡

[10 marks]

(d) A data pattern analyser is to be built that can detect and count up the number
of occurrences of strictly increasing and strictly decreasing sequences of
three numbers in an input sequence. So for the sequence (1,2,3,4) there are
two strictly increasing sequences (1,2,3) and (2,3,4).

The analyser should stop if it encounters 0 in the input sequence and return
the number of occurrences found up to that point in the form of a 2-tuple
(#𝑖𝑖𝑛𝑛𝑠𝑠𝑡𝑡𝑡𝑡𝑎𝑎𝑠𝑠𝑖𝑖𝑛𝑛𝑔𝑔, #𝑛𝑛𝑡𝑡𝑠𝑠𝑡𝑡𝑡𝑡𝑎𝑎𝑠𝑠𝑖𝑖𝑛𝑛𝑔𝑔).

So, for example:

3
G6017 Program Analysis

Input sequence Increasing sequences Decreasing

found sequences found
(1,2,3) 1 0
(1,2,2) 0 0
(3,2,1) 0 1
(3,2,2) 0 0
(1,2,3,4) 2 0
(1,0,1,2,3) 0 0
(1,2,3,4,3,2,1) 2 2

Produce a formal statement of this problem, and then write an algorithm to

solve the problem using a pseudo code style similar to the one shown in parts
(a) to (c). State the bounds on the best and worst case performance of your
algorithms using O,  and  appropriately to receive full marks.

[10 marks]

(e) A file is protected by a random password consisting of 𝑛𝑛 binary bits. All

password combinations are equally probable. To access the file we need the
correct password. The process of applying the password to the file takes
20ms regardless of the value of 𝑛𝑛. Brute force attack is always a viable basic
strategy for guessing a password.

To ensure that the file remains sufficiently secure, we need to ensure that
there is no more than a 2% chance over 30 days that the password is
guessed by a hacker program utilizing brute force working 24 hours a day, 7
days a week. How many bits should be specified for the password?

[10 marks]

4
G6017 Program Analysis

2.

(a) A student has been asked to put some parcels on a shelf. The parcels all
weigh different amounts, and the shelf has a maximum safe loading weight
capacity of 100 Kg. The weight of parcels are as follows (in Kg):

𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑𝒑 𝒘𝒘𝒑𝒑𝒘𝒘𝒘𝒘𝒘𝒘𝒘𝒘
(𝑲𝑲𝒘𝒘)
1 10
2 5
3 2
4 42
5 50
6 25
7 1

The student has been asked to load the maximum weight possible parcels on
the shelf subject to the maximum safe loading weight.

State two possible approaches for a greedy algorithm solution to solve this
problem. In each case, state clearly the result you would get from applying
that approach to this problem, stating whether the solution is optimal or not. If
your answer does not produce an optimal solution, what algorithm could be
employed to find one?
[10 marks]

(b) One example of a greedy algorithm is the Kruskal algorithm for finding a
Minimum Spanning Tree. The algorithm is shown below.

Kruskal(G,w)

Let 𝑄𝑄 be the edges in 𝐸𝐸 order ordered by increasing weight

Initialise 𝐸𝐸’ 𝑡 o the empty set
For each vertex 𝑣𝑣 ∈ 𝑉𝑉
Let 𝑙𝑙(𝑣𝑣) be the singleton set containing 𝑣𝑣
While |𝐸𝐸 ′ | < |𝑉𝑉 | − 1
Remove edge {𝑠𝑠, 𝑣𝑣} from 𝑄𝑄
If 𝑙𝑙 (𝑠𝑠 ) ≠ 𝑙𝑙(𝑣𝑣) then
Include {𝑠𝑠, 𝑣𝑣} in 𝐸𝐸’
𝑙𝑙 (𝑠𝑠 ) ← 𝑙𝑙 (𝑣𝑣 ) ← 𝑙𝑙 (𝑠𝑠 ) ∪ 𝑙𝑙(𝑣𝑣)

5
G6017 Program Analysis

Consider the graph below with a set 𝑉𝑉 of 8 vertices and a set of weighted
edges 𝐸𝐸:

At the outset, each graph vertex is assigned to its own cluster, so each cluster
is distinct and has exactly one element. So initially vertex 𝑣𝑣1 is assigned to
cluster 𝐴𝐴, 𝑣𝑣2 to cluster 𝐵𝐵 and so on.

Complete the table below showing which vertices belong to which clusters at
each point in the algorithm where clusters are joined. You should assume that
when a union of two clusters is formed, the new cluster takes the earliest
letter applicable. For example, if cluster 𝐹𝐹 = {𝑣𝑣6 } i.e. 𝑙𝑙(𝑣𝑣6 ) = 𝐹𝐹, and cluster
𝐺𝐺 = {𝑣𝑣7} i.e. 𝑙𝑙(𝑣𝑣7) = 𝐺𝐺, then the union of clusters 𝐹𝐹 and 𝐺𝐺 would become
cluster 𝐹𝐹 = {𝑣𝑣6, 𝑣𝑣7} and thus 𝑙𝑙(𝑣𝑣6) = 𝐹𝐹 and 𝑙𝑙(𝑣𝑣7) = 𝐹𝐹. This is shown in the
second row completed below.

𝒗𝒗𝟏𝟏 𝒗𝒗𝟐𝟐 𝒗𝒗𝟑𝟑 𝒗𝒗𝟒𝟒 𝒗𝒗𝟓𝟓 𝒗𝒗𝟔𝟔 𝒗𝒗𝟕𝟕 𝒗𝒗𝟖𝟖

A B C D E F G H
A B C D E F F H

[10 marks]

6
G6017 Program Analysis

(c) A message of length 𝑥𝑥 symbols is made from a set of 8 symbols drawn from
a vocabulary shown below, with each symbol being coded using 3 binary bits:

Symbol 3-bit coding Relative

element frequency
A 0 0 0 0.2
B 0 0 1 0.06
C 0 1 0 0.05
D 0 1 1 0.08
E 1 0 0 0.3
F 1 0 1 0.12
G 1 1 0 0.04
H 1 1 1 0.15

So, the message BADGE (x = 5) would be coded as 001, 000, 011, 110,100.
This message requires a constant 3 bits/symbol. Analysis shows that in
general usage, the symbols appear with the relative frequency as shown also
in the table.

(i) Construct a Huffman coding tree to determine the most efficient

alternative coding for the symbols so as to minimise the number of
bits/symbol to code a message.
[10 marks]

(ii) Determine the average number of bits/symbol required to code a

message using this more efficient alternative coding.
[5 marks]

(d) A recursive algorithm is applied to some data 𝐴𝐴 = (𝑎𝑎1 , … , 𝑎𝑎𝑚𝑚 ) where 𝑚𝑚

≥ 3 and 𝑚𝑚 is divisible by 3. The running time 𝑠𝑠 is characterised using
the following recurrence equations:

𝑠𝑠(3) = 𝑠𝑠 when the size of 𝐴𝐴 is 3

𝑠𝑠 (𝑚𝑚 ) = 𝑠𝑠(𝑚𝑚 − 3) + 𝑠𝑠 otherwise

Determine the running time complexity of this algorithm. Note that 𝑚𝑚

is divisible by 3 and the problem size reduces by 3 for each recursion.
[10 marks]

(e) A student wishes to solve the Minimum Spanning Tree problem using a new
algorithm they have devised. They decide to test their new algorithm against
the well-known Kruskal and Prim algorithms. Discuss whether the new
algorithm is guaranteed to produce an identical tree output as the Kruskal
algorithm when provided with the same input graph.
{5 marks]

7
G6017 Program Analysis

3.

(a) The subset sum problem can be reliably solved optimally using the dynamic
programming algorithm shown below:

SubsetSum(𝑛𝑛, 𝑊𝑊)

Let 𝐵𝐵(0, 𝑤𝑤) = 0 for each 𝑤𝑤 ∈ {0, … , 𝑊𝑊}

for 𝑖𝑖 ← 1 𝑡𝑡𝑠𝑠 𝑛𝑛
for 𝑤𝑤 ← 0 𝑡𝑡𝑠𝑠 𝑊𝑊
if 𝑤𝑤 < 𝑤𝑤𝑖 then
𝐵𝐵 (𝑖 , 𝑤𝑤 ) ← 𝐵𝐵 (𝑖 − 1, 𝑤𝑤 )
else
𝐵𝐵(𝑖𝑖 , 𝑤𝑤) ← max (𝑤𝑤𝑖 + 𝐵𝐵 (𝑖 − 1, 𝑤𝑤 − 𝑤𝑤𝑖 ), 𝐵𝐵 (𝑖 − 1, 𝑤𝑤 ))

where 𝑛𝑛 is the number of requests, 𝑊𝑊 is the maximum weight constraint, 𝑤𝑤𝑖 is

the weight associated with request 𝑖 , and 𝐵𝐵 is the solution space.

You are given a set of requests and their corresponding weights. The
maximum weight constraint 𝑊𝑊 is 12.

𝒘𝒘 𝒘𝒘𝒘𝒘
1 2
2 1
3 6
4 7
5 1
6 10

Complete the solution space table to determine the optimal subset sum.

𝒘𝒘
0 1 2 3 4 5 6 7 8 9 10 11 12

6
5
4
3
𝒘𝒘 2
1
0

[10 marks]

8
G6017 Program Analysis

(b) A recursive algorithm has been developed as shown below:

Input: List 𝐴𝐴 = (𝑎𝑎1 , … , 𝑎𝑎𝑁𝑁 ) such that 𝑖𝑖 ≥ 1

Output: value 𝑥𝑥

𝑓𝑓𝑠𝑠𝑠𝑠(𝐴𝐴)

if length(𝐴𝐴) == 1
return 𝑎𝑎1

𝐴𝐴′ = (𝑎𝑎1 , … , 𝑎𝑎𝑁𝑁−1 )

𝑞𝑞 = 𝑓𝑓𝑠𝑠𝑠𝑠(𝐴𝐴′ )
if (𝑞𝑞 > 𝑎𝑎𝑁𝑁 )
return q
else
return 𝑎𝑎𝑁𝑁

State what problem this algorithm solves and write down the two recurrence
equations that characterise this recursive algorithm.
[10 marks]

(c) Define what is meant by the term “topological sort” when applied to a Directed
Acyclic Graph (DAG).
[5 marks]
.

(d) Enumerate all possible topological sorts for the DAG shown below.

[5 marks]

9
G6017 Program Analysis

(e) The Ford-Fulkerson algorithm is used to determine network flow. The diagram
below represents a data network that connects a Data Service Provider (DSP)
connected to 𝑣𝑣1 (s) to a customer connected to 𝑣𝑣6 (t). Each edge represents a
single data transmission link.

The notation 𝑝𝑝/𝑞𝑞 indicates a current actual forwards flow 𝑝𝑝 measured in Gb/s in a
cable with a maximum capacity of 𝑞𝑞 also measured in Gb/s.

At the outset no data is being sent by the DSP to the customer.

i. Show the residual graph that will be created from the initial empty flow. When
drawing the residual graph, show a forward edge with capacity 𝑥𝑥 and a
backward edge with flow 𝑦𝑦 by annotating the edge
�𝑥
�⃗ ;
�𝑦
�⃖ .
[2 marks]

i. What is the bottleneck edge of the path (𝑠𝑠, 𝑣𝑣3 , 𝑣𝑣2 , 𝑣𝑣5 , 𝑡 ) in the residual graph
you have given in answer to part (i) ?
[2 marks]

ii. Show the residual graph after incorporating the simple path (𝑠𝑠, 𝑣𝑣3 , 𝑣𝑣2 , 𝑣𝑣5 , 𝑡 )
that results from augmenting the flow based on the residual graph you have
given in answer to part (i).

[4 marks]

iv. Repeat the process outlined above incorporating additionally the simple paths
(𝑠𝑠, 𝑣𝑣3 , 𝑣𝑣4 , 𝑣𝑣5 , 𝑡 ) , (𝑠𝑠, 𝑣𝑣3 , 𝑣𝑣4 , 𝑣𝑣2, , 𝑣𝑣5 𝑡 ), (𝑠𝑠, 𝑣𝑣2 , 𝑣𝑣4 , 𝑡 ) and (𝑠𝑠, 𝑣𝑣3 , 𝑣𝑣4 , 𝑡 ) showing each residual
graph, to determine the maximum flow between 𝑠𝑠 and 𝑡 , and thus the
maximum data bandwidth that can be achieved between the DSP and the
customer. Remember to check whether you are following a forwards or
backwards edge in the residual graph.

[12 marks]
10
G6017 Program Analysis

End of paper

11