2023年11月25日

数据结构代写 | INFORMATICS 2: INTRODUCTION TO ALGORITHMS AND DATA STRUCTURES

本次美国代写主要为数据结构与算法限时测试

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]

FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
(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]