Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Inf2-IADS Sample Exam
PART A:
1. (a) The diagram is essentially
[3,9,8,2,4,1,6,5]
[3,9,8,2] [4,1,6,5]
[3,9] [8,2] [4,1] [6,5]
[3] [9] [8] [2] [4] [1] [6] [5]
[3,9] [2,8] [1,4] [5,6]
[2,3,8,9] [1,4,5,6]
[1,2,3,4,5,6,8,9]
with the obvious arrows added.
[5 marks; roughly 2 for the splittings and 3 for the mergings.]
(b) Best, worst and average case times are all Θ(m ∗ 2m).
[1 mark each.]
(c) To mergesort a list of length 2m we only need an array of size 2 ∗ 2m (proof
is an easy induction). So space needed is Θ(2m).
[1 mark for the answer; 1 mark for any reasonable supporting point.]
2. This is the question about the different fi; we have f1(n) = (lg(n))
lg(n), f2(n) =
nlg(n), f3(n) = n
2 and f4(n) = n.
note: this is an example of where it’s important to know the “rules of logs”.
(a) We are asked to identify the i ∈ {1, 2, 3, 4} such that
fi(n) ∈ O(fj(n)) for all j = {1, 2, 3, 4}.
Basically we want the fi that is “asymptotically slowest”.
This function is f4 = n.
The (informal) justification for this . . .
• n certainly grows slower than f3 = n2.
• Also n certainly grows slower than f2 = nlgn (lg n ≥ 2 for every n ≥ 4)
• To consider relative growth of f4 against f1, we will take the lg of
both functions: then lg(f1(n)) = lg(lg(n)
lg(n)) which is equal to lg(n) ·
lg lg(n) by “rules of logs” and lg(f4(n)) = lg(n). Hence lg(f1(n)) =
lg(n) · lg(f4(n)) so lg(f1(n))) grows asymptotically faster than lg(f4(n)),
and f1(n) grows much much faster than f4(n). Hence f4 = O(f1).
[5 marks: 2 for identifying the correct i as 4, 1 mark each for the justification
wrt each j 6= 4].
Page 1 of 9
(b) We have to identify the k ∈ {1, 2, 3, 4} such that
fk(n) ∈ Ω(fj(n)) for all j = {1, 2, 3, 4},
and formally justify this.
The function fk is f2 = n
lg(n).
To prove the fk = Ω(fj) for another j we need to find a n0 ∈ N, c ∈ R>0
such that nlg(n) ≥ c · fj for all n ≥ n0.
• For j = 1, we can set c = 1, n0 = 2, then n ≥ lg(n) for n ≥ 2 and
hence nlg(n) ≥ lg(n)lg(n) (as the exponent lg(n) is a positive value > 1
for n ≥ 2)
• For j = 3, we set c = 1, n0 = 4, then for n ≥ 4 we have lg(n) ≥ 2 and
hence f3(n) = n
lg(n) ≥ n2.
• For j = 3, we set c = 1, n0 = 2, then for n ≥ 2 we have lg(n) ≥ 1 and
hence f3(n) = n
lg(n) ≥ n.
[5 marks: 2 for identifying the correct i as 4, 1 mark each for the formal
justification wrt each j 6= 4].
3. (a) The hash table will have better average case performance. If 10,000 integers
are stored, the average bucket size will be 5, so on average, 5 key comparisons
will be required for an insertion or unsuccessful lookup, and fewer for a
successful lookup. A binary tree storing 10,000 integers, even if perfectly
balanced, will have depth around lg 10, 000 ' 13, so a lookup will involve
12 comparisons on average.
However, the hash table has terrible worst case performance: if all 10,000
integers hash to the same value, a lookup might require 10,000 comparisons.
For red-black trees, the depth (hence the number of comparisons) will be
bounded by something around 2 lg 10, 000 ' 26.
[3 marks for discussion of average case, 3 marks for worst case. Ballpark
figures are acceptable, as in the above answer. Any other reasonable points
are acceptable.]
(b) The 1 is first added as the left child of 2, and initially coloured R [1 mark].
We then apply the ‘red uncle’ rule, turning 2 and 4 B and 3 R [2 marks].
Finally, since 3 is the root, we turn it B [1 mark]. So in the end, 2,3,4 are
B and 1 is R.
4. A decimal counter of length n consists of an array D indexed by 0, . . . , n− 1, in
which each cell contains one of the decimal digits 0, . . . , 9. The value v(D) of
such a counter is the sum
∑n−1
i=0 D[i] ∗ 10i.
The following operation increments the current value of the counter modulo 10n:
Page 2 of 9
Inc():
i = 0
while iD[i] = 0
i = i+1
if iD[i] = D[i]+1
(a) Best case time is Θ(1) [1 mark]. This is illustrated by any scenario where
D[0] 6= 9 [1 mark].
(b) Worst case time is Θ(n) [1 mark]. Illustrated by the case where D[i] = 9 for
all i [1 mark].
(c) Suppose we gauge runtime cost by the number of times the while-test is
evaluated (the total number of line executions will be within a factor of 6
of this). Each of the 10n Inc’s will do this test at least once; a tenth of
them will do it at least twice; a hundredth at least three times, etc. So total
runtime cost will be
10n(1 +
1
10
+
1
100
+ · · ·+ 1
10n
) < 10n ∗
∞∑
i=0
10−i = 10n ∗ 1.1111 · · ·
Thus total cost is between 10n and 10n ∗ 10/9, and so is Θ(n). Amortized
average cost per operation is thus between 1 and 10/9, hence Θ(1). [1 mark
for each of the answers; 4 marks for the justification.]
5. Trying to reduce Independent Set to 3-SAT.
(a) Given C = (`1 ∨ `2), we can replicate the exact conditions under which C is
true by introducing any logical variable xC and replacing C by the con-
junction of the following two 3-CNF clauses: C ′ = (`1 ∨ `2 ∨ xC) and
C ′′ = (`1 ∨ `2 ∨ ¬xC)
[2 marks for the correct construction]
(b) For a k-literal clause C = (`1 ∨ . . . ∨ `k) for k ≥ 4, we define k − 2 vari-
ables xC,2, . . . , xC,k−2 and replace C by the conjunction of the following
clauses:
C(2) = (`1 ∨ `2 ∨ ¬xC,2)
C(3) = (xC,2 ∨ `3 ∨ ¬xC,3)
. . . . . . . . . . . . . . .
C(k − 1) = (xC,k−2 ∨ `k−1 ∨ `k)
[2 marks for the correct construction]
Page 3 of 9
(c) The graph G = (V,E) (n = |V |,m = |E|) will have an Independent Set
of size ≥ 4 if and only if for every subset V ′ ⊆ V, |I| = n − 3, V ′ has at
least one vertex in I. Using the boolean variable xv to indicate “v is in I”
(xv = 1 in this case), we can represent “V
′ has at least one vertex in I” as
the length-(n− 3) clause ∨v∈V ′ xv.
We need to consider every subset of size (n − 3), so we have (n
3
)
of these
length-(n−3) clauses, joined by a ∧. By (b) we know any one of the length-
(n− 3) clauses can be re-cast as (n− 5) 3-CNF clauses. Doing this for each
of the big clauses gives a 3-CNF Φ which has (n− 5)(n
3
)
clauses in total.
To ensure adjacent vertices can’t belong to I, we add (¬xu ∨¬xv) for every
e = (u, v) ∈ E. By (a), these can be coded as 2 3-CNF clauses, giving 2m
extra clauses.
[4 marks - 1 for the length-(n−3) clause, 1 for the characterisation as 3-CNF,
1 for the counting of all big clauses, 1 for the “non-adjacent” clauses.]
(d) If we consider generalising the reduction in (c) to the case where we were
interested in an Independent Set of size ≥ h, for an arbitrary h, we would
find ourselves considering taking
(
n
h−1
)
different subsets of V , and adding a
“big clause” (eventually realised as the ∧ of a number of 3-CNF clauses) for
each of these. If h is variable, then the number of “big clauses” is no longer
polynomially-sized. So no, this approach doesn’t work.
[2 marks for a decent explanation.]
Page 4 of 9
FOR PART B:
1. (a) After the first Heap-Extract-Max, the array has 18, 11, 8, 1, 6, 5.
After calling Max-Heap-Insert(17), the array then has 18, 11, 17, 1, 6, 5, 8
After calling Heap-Extract-Max again, the array then has 17, 11, 8, 1, 6, 5
After calling Max-Heap-Insert(7), the array then has 17, 11, 8, 1, 6, 5, 7
After calling Max-Heap-Insert(19), the array then has 19, 17, 8, 11, 6, 5, 7, 1
[5 marks for the right answer]
(b) We are considering the implementation of ExtendedQueue.
i. There is not really any intelligent way to implement findElement on a
Heap. If we try to search from the root, then whenever we are exploring
a node v, if we find that v.key < k, we are allowed to ignore all nodes
below v. However, if v.key > k then we must search in both of the
subtrees below v, since the Heap structure does not tell us anything
more about where k might be.
We can however implement an algorithm which does a traversal of the
Heap, and which stops exploring when v.key < k. In the worst-case
this has a running time of Θ(n). Consider the case where k lies is the
lowest level of the Heap... In this case k is no more likely to be in any
spot (on this level) than another. However the lowest level of the Heap
may contain n/2 elements in total (if the total size of the Heap is n).
[3 marks for a correct findElement and 2 marks for justifying the Θ(n)
(1 for each of O(n) and Ω(n)).]
ii. To implement maxElement on a Red-Black tree, we observe that the
element with the Maximum key in a R-B tree is the rightmost “near-
leaf”, giving the following algorithm for maxElement:
I. Start at the root of the R-B tree and keep walking to the right-hand
child of the current node, until the next right child is a trivial leaf.
II. Return the element stored in this position.
This little algorithm has worst-case running-time Θ(h) = Θ(lg(n)),
given what we know about the height of R-B trees.
For removeMax, we initially perform the same steps as for maxElement.
Then we delete the node we arrived at - this will potentially require
the re-colouring of nodes up to the root of the tree (in the case that
we deleted a previously-black node). There are a number of cases to
patch-up the tree, but all can be executed in time proportional to the
height which is Θ(lg(n)).
[1 mark for removeMax and 1 for its running time, 2 marks for remove-
Max and 1 for its running time.]
iii. The operations removeMax and insertItem both have worst-case running
time Θ(lg(n)) on a Heap, and on a R-B tree. The operations findElement
and maxElement have different asymptotics on the different structures.
Page 5 of 9
If we are implementing an Extended Queue on a Heap, then the Θ(n)
running-time of findElement on a Heap might be prohibitive. If we
expect findElement to be used relatively frequently for a particular ap-
plication of ExtendedQueue, then we should use the Red-Black imple-
mentation.
However, the R-B implementation of maxElement is less efficient than
the Θ(1) implementation of the Heap. So if findElement calls are infre-
quent, we might choose to work with the Heap implementation.
[5 marks, awarded based on the quality of the arguments.]
(c) To implement UpdateKey(o, k′), we assume that o is a direct reference to
the object o = (e, k), so we don’t need to carry out findElement. We want
to update the key value of o to become k′, but doing this may violate the
Max-Heap property. There are two cases:
• If k′ > k, then k′ may be larger than the parent of o.
This scenario is very similar to the situation in Max-Heap-Insert after the
new key gets inserted at the available leaf - the solution is to “swap with
the parent” until o sits at a position where k′ is less than the parent’s
key. This is O(h) = O(lg(n)) time.