Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
PART A:
1. (a) Illustrate the application of MergeSort to the list [3,9,8,2,4,1,6,5], by means
of a diagram showing the recursive call structure. You should show both
the argument passed to MergeSort on each call and the result returned by
each call as the lists are recombined. [5 marks]
(b) Suppose we restrict our use of MergeSort to lists of length 2m for various
natural numbers m.Give ⇥-estimates in terms of m for the best-case, worst-
case and average-case number of comparisons performed by MergeSort on
such lists. You need not justify your answers. [3 marks]
(c) Give a ⇥-estimate, again in terms of m,fortheamountofmemoryusedby
MergeSort on lists of length 2m,assumingaversionofMergeSortthatisas
space-e”cient as possible. Briefly justify your answer. [2 marks]
2. Consider functions f1(n) = (lg(n))lg(n)
, f2(n)= nlg(n)
, f3(n)= n2
and f4(n)= n.
(a) There is exactly one i 2 {1, 2, 3, 4} such that
fi(n) 2 O(fj (n)) for all j = {1, 2, 3, 4}.
(ie, fi is “big-O” of all the other fj ).
State which function is fi,givinginformaljustificationof fi(n) 2 O(fj (n))
for each j = i.[5 marks]
(b) There is also exactly one k 2 {1, 2, 3, 4} such that
fk(n) 2 ⌦(fj (n)) for all j = {1, 2, 3, 4}.
(ie, fk is “big-⌦” of all the other fj ).
State which function is fk,andrigorouslyjustify fk = ⌦(fj )foreach j = k.[5 marks]
3. (a) Suppose you require a data structure for storing sets of up to 10,000 integers,
supporting membership testing and insertion. You are trying to decide
between two implementation schemes:
• abucket-arrayhashtableofsize2,000,usingchainingtoresolvecolli-
sions,
• ared-blacktreeimplementation,storingintegersattheinternalnodes.
Discuss the relative advantages and disadvantages of each scheme. Your
discussion should be as specific as possible, including rough numerical es-
timates of relevant quantities based on your understanding of these data
structures. [6 marks]
(b) The following red-black tree is a possible representation of the set {2, 3, 4}.
The letters R and B show whether nodes are red or black. We have omitted
the trivial leaf nodes.
With the help of diagrams, explain the steps that occur when the new ele-
ment 1 is inserted into this set. [4 marks]
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 Pn!1
i=0 D[i] ⇤ 10i
.
The following operation increments the current value of the counter modulo 10n:
Inc():
i=0
while i<nandD[i]==9
D[i] = 0
i=i+1
if i<n
D[i] = D[i]+1
(a) Give a ⇥-estimate for best case runtime of Inc. Give an example, parametric
in n, illustrating best-case behaviour (you need not prove that it does so). [2 marks]
(b) Give a ⇥-estimate for worst case runtime of Inc. Give an example, para-
metric in n,illustratingworst-casebehaviour(againwithoutproof).
(c) Suppose now that we apply the Inc operation 10n times (so that the counter
returns to its starting state). Give a ⇥-estimate for the total runtime for
this sequence of operations, and one for the amortized average cost per Inc
operation. Justify your answer by means of a mathematical analysis of the
total runtime.