Program Analysis Problem Sheet 3
1. Specify the running time of each of the following algorithms.
(a) Algorithm Ex1(n):
a←n
for i ← 1 to 5 do
a←a+n
(b) Algorithm Ex2(n):
a←0
for i ← 1 to n do
a←a+i
(c) Algorithm Ex3(n):
a←0 fori←1ton do
2
a←a+i
(d) Algorithm Ex4(n):
a←1
for i ← 1 to n do
a←a∗n
(e) Algorithm Ex5(n):
a←0 fori←1ton2 do
a←a+1
(f) Algorithm Ex6(n):
a←0
for i ← 1 to n do
for j ← 1 to i do a←a+1
(g) Algorithm Ex7(n):
a←0
for i ← 1 to n do
for j ← 1 to i do for k ← 1 to j do
a←a+1
(h) Algorithm Ex8(n): fori←0ton2 do
forj ←0toido a←i
Term 1, 2015
Program Analysis Term 1, 2015
2. Consider two algorithms: Algorithm 1 and Algorithm 2 that solve the same prob-
lem. Suppose you know that:
• the worst-case running time of Algorithm 1 is O(n2);
• the worst-case running time of Algorithm 2 is Θ(n3); and • the worst-case running time of Algorithm 2 is O(n4)
For each of the following statements, indicate whether you have sufficient infor- mation about the algorithms to justify the claim being made. Fully explain your answers.
(a) It is redundant to be told that the worst-case running time of Algorithm 2 is O(n4) given that it is known to be Θ(n3).
(b) For all inputs Algorithm 1 will outperform Algorithm 2.
(c) There is some (possibly very large) input size such that for all inputs that
exceed that size Algorithm 1 will outperform Algorithm 2.
(d) In the worst case the larger the input the greater the extent to which Algo-
rithm 1 outperforms Algorithm 2.
(e) Sincebothalgorithmssolvethesameproblemtheymusthavethesamebest-
case running times.
(f) There are some inputs for which Algorithm 1 will outperform Algorithm 2.
3. Show how a heap is built from the following sequence of (value, priority) pairs. Assume that elements are inserted into the heap in the order that they appear in this sequence.
⟨(a, 55), (b, 13), (c, 72), (d, 84), (e, 80), (f, 44), (g, 11), (h, 99), (i, 100), (j, 77), (k, 90), (l, 30)⟩
4. Give a general characterisation of input that will lead to the worse-case and best- case running times when building a heap from scratch.
Program Analysis Term 1, 2015
5. How can the following BFS algorithm be modified so that it detects whether or
not the graph being traversed contains a cycle?
BFS(G, s) :
let Q be a queue containing just the node s discovered(s) ← true discovered(v)←falseforallv∈V −{s} T ← (V, { })
while Q is not empty
remove v from the front of Q
for each edge { v, w } in E where not discovered(w)
discovered(w) ← true
add w to the back of Q
add edge {v,w} to edges in T
6. How can the following DFS algorithm be modified so that it detects whether or not the graph being traversed contains a cycle?
DFS(G, s) :
let S be a stack containing just the node s explored(v) ← false for all v ∈ V
while S is not empty
pop v from the top of S if not explored(v) then
for each edge { v, w } in E where not explored(w) push w onto S
parent(w) ← v
explored(v) ← true
7. The order in which vertices are considered is somewhat under-specified in the BFS algorithm. Given this, is it possible that there could be more than one breadth- first search tree produced by the BFS algorithm using a graph G = (V,E) and starting the search with some particular vertex v ∈ V ?
8. What would be the running time of BFS if the graph is stored using an adjacency matrix rather than an adjacency list representation?