INFORMATICS 2: INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES
Inf2-IADS Sample Exam (2 hours)
INSTRUCTIONS TO CANDIDATES
This is an Open Book exam.
You have 2 hours to complete all questions.
1. Answer all five questions in Part A, and two out of three questions in Part B. Each question in Part A is worth 10% of the total exam mark; each question in Part B is worth 25%.
2. Use a single script book for all questions.
3. Calculators may be used in this exam.
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.
3. (a)
PART A:
(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.
(c) Give a Θ-estimate, again in terms of m, for the amount of memory used by MergeSort on lists of length 2m, assuming a version of MergeSort that is as space-efficient as possible. BrieΩy justify your answer.
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 ∈ {1, 2, 3, 4} such that
fi(n) ∈ 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, giving informal justification of fi(n) ∈ O(fj(n)) foreachj̸=i.
(b) There is also exactly one k ∈ {1, 2, 3, 4} such that
fk(n) ∈ Ω(fj(n)) for all j = {1,2,3,4}.
[5 marks ]
[3 marks ]
[2 marks]
(ie, fk is “big-Ω” of all the other fj).
State which function is fk, and rigorously justify fk = Ω(fj) for each j ̸= k.
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:
• a bucket-array hash table of size 2,000, using chaining to resolve colli- sions,
• a red-black tree implementation, storing integers at the internal nodes.
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.
Page 1 of 8
[5 marks ]
[5 marks ]
[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. 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 D[i] ∗ 10i. i=0
The following operation increments the current value of the counter modulo 10n:
Inc(): i=0
while i