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
Model Answer: Θ(1)
Term 1, 2015
The algorithm involves a constant number of steps — does not grow with n.
(b) Algorithm Ex2(n):
a←0
for i ← 1 to n do
a←a+i
Model Answer: Θ(n)
There is a single loop that is executed n times and contains a constant num- ber of steps.
(c) Algorithm Ex3(n):
a←0 fori←1ton do
2
a←a+i
Model Answer: Θ(n)
There is a single loop that is executed n times and contains a constant num- ber of steps.
(d) Algorithm Ex4(n):
a←1
for i ← 1 to n do
a←a∗n
Model Answer: Θ(n)
There is a single loop that is executed n times and contains a constant num- ber of steps.
(e) Algorithm Ex5(n):
a←0 fori←1ton2 do
a←a+1
Program Analysis Term 1, 2015 Model Answer: Θ(n2)
There is a single loop that is executed n2 times and contains a constant num- ber of steps.
(f) Algorithm Ex6(n):
a←0
for i ← 1 to n do
forj ←1toido a←a+1
Model Answer: Θ(n2)
The inner loop is executed ∑ni=1 i = (n)(n + 1)/2 times
(g) Algorithm Ex7(n):
a←0
for i ← 1 to n do
forj ←1toido for k ← 1 to j do
a←a+1 Model Answer: Θ(n3)
(h) Algorithm Ex8(n): fori←0ton2 do
forj ←0toido a←i
Model Answer: Θ(n4)
The inner loop is executed ∑n2 i=1
i = n2(n2 + 1)/2 times.
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).
Model Answer: True: it is redundant, because Θ(n3) implies O(n3) which implies O(n4).
(b) For all inputs Algorithm 1 will outperform Algorithm 2.
Model Answer: False: only know worst-case running time of Algorithm 2. There may be some inputs for which the algorithm runs in constant time. In practice, the constant factor hidden by the big-O is also important— 106n2 > n3 for every n < 106.
(c) There is some (possibly very large) input size such that for all inputs that exceed that size Algorithm 1 will outperform Algorithm 2.
Model Answer: False: only know worst-case running time of Algorithm 2. There may be inputs for which the algorithm runs in constant time.
(d) In the worst case the larger the input the greater the extent to which Algo- rithm 1 outperforms Algorithm 2.
Model Answer: True: since the function n3 grows faster than n2.
(e) Sincebothalgorithmssolvethesameproblemtheymusthavethesamebest-
case running times.
Model Answer: False: Obviously silly. You could say that algorithms with quite different best-case running times exist for the sorting problem.
(f) There are some inputs for which Algorithm 1 will outperform Algorithm 2.
Program Analysis Term 1, 2015 Model Answer: True: This is true since there should be some sufficiently
large worst-case inputs that would illustrate it.
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)⟩ Model Answer:
[(a, 55)]
[(a, 55), (b, 13)]
[(c, 72), (b, 13), a(55)]
[(d, 84), (c, 72), (a, 55), (b, 13)]
[(d, 84), (e, 80), (a, 55), (b, 13), (c, 72)]
[(d, 84), (e, 80), (a, 55), (b, 13), (c, 72), (f, 44)]
[(d, 84), (e, 80), (a, 55), (b, 13), (c, 72), (f, 44), (g, 11)]
[(h, 99), (d, 84), (a, 55), (e, 80), (c, 72), (f, 44), (g, 11), (b, 13)]
[(i, 100), (h, 99), (a, 55), (d, 84), (c, 72), (f, 44), (g, 11), (b, 13), (e, 80)]
[(i, 100), (h, 99), (a, 55), (d, 84), (j, 77), (f, 44), (g, 11), (b, 13), (e, 80), (c, 72)]
[(i, 100), (h, 99), (a, 55), (d, 84), (k, 90), (f, 44), (g, 11), (b, 13), (e, 80), (c, 72), (j, 77)]
[(i, 100), (h, 99), (a, 55), (d, 84), (k, 90), (f, 44), (g, 11), (b, 13), (e, 80), (c, 72), (j, 77), (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.
Model Answer: The worse case occurs when values in ascending order of pri- ority since in this case every value has to be moved up to the front (root) of the heap.
The best case occurs when values are in descending order of priority since no exchanging of positions will be needed. There are other inputs that will also lead to best-case running time - in particular, variants of the descending ordering in which elements at the same level of the heap are permuted in any way.
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) ← false for all v ∈ 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
Model Answer:
BFS(G, s) :
let Q be a queue containing just the node s discovered(s) ← true
discovered(v) ← false for all v ∈ V − {s} T ← (V, { })
cycle ← false
while Q is not empty and not cycle
remove v from the front of Q for each edge {v,w} in E
if discovered(w)
if not {v,w} ∈ T then cycle ← true
else
discovered(w) ← true
add w to the back of Q
add edge {v,w} to edges in T
return cycle
A cycle exists in the graph if a vertex w that has been discovered by going through edge v, w can be reached again through a different edge v′, w. In other words, if T holds all edges that have been used during the traversal, at some point as the algorithm proceeds for some vertex w there will exist two distinct edges, { v, w } ∈ T and { v′, w } ∈/ 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) :
Program Analysis
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 Model Answer:
DFS(G, s) :
let S be a stack containing just the node s explored(v) ← false for all v ∈ V
cycle ← false
while S is not empty and not cycle
pop v from the top of S if not explored(v) then
for each edge {v,w} in E if explored(w)
if not parent(v) = w then cycle ← true else
push w onto S
parent(w) ← v explored(v) ← true
return cycle
Term 1, 2015
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 ?
Model Answer: The graph on the left can produce both of the trees on the right. Note that in both cases, traversal begins at v1.
Program Analysis
Term 1, 2015
v1
v2
v3
v2
v3
v4
v1
v2
v3
v4
v1
v4
8. What would be the running time of BFS if the graph is stored using an adjacency matrix rather than an adjacency list representation?
Model Answer: The running time would be Θ(n2) since the entire contents of the adjacency matrix would be examined and it contains Θ(n2) entries. Further- more, this dominates the running time of the algorithm.