THE UNIVERSITY OF HONG KONG

FACULTY OF ENGINEERING

DEPARTMENT OF COMPUTER SCIENCE

COMP2119 Introduction to Data Structures and Algorithms

Date: 16 Dec, 2019 Time: 9:30am - 12:30pm

Write Your University Number here: ___________ _

Please read the following before you begin.

1. Only approved calculators as announced by the Examinations Secretary can be used in this

examination. It is your responsibility to ensure that your calculator operates satisfactorily,

and you must record the name and type of the calculator used in the first page of your

answer script, or here:

2. You are advised to spend around 5 minutes to go through all the questions before you begin

writing. Allocate the time for each part of the question carefully.

3. If you have a printer or plan to annotate the given PDF file, you may write your answer in

the designated space. Alternatively, if you are going to first write your answer on blank pieces

of paper, the designated space will give you an idea of the length of the solution.

4. Attempt ALL questions. The full mark for the exam is 100 points.

For marking use:

Question 1

Question 2

Question 3

Question 4

Question 5

Page 1 of 13

1 Asymptotic Notation (20 points)

( a) (12 pt) Solve the following recurrence relations and give the simplest expression using Big-Theta

notation. You do not need to give a full proof.

(i) T(n) = T(lfoJ) + logn, T(O) = T(l) = 1.

(ii) T(n) = T(n - 3) + n2 , T(O) = T(l) = T(2) = 1.

(iii) T(n) = T(lfoJ) + 1, T(l) = 1.

(iv) T(n) =T(liJ)+T(liJ)+T(l�j)+n, T(O) =0.

Page 2 of 13

(b) (8 pt) For each of the following statements, state whether it is true or false.

(i) n2 = O(n).

(iii) n logn = 0(1).

Page 3 of 13

2 Dictionary Abstract Datatype (15 points)

Recall that the dictionary abstract data type stores a collection of keys, and supports the operations

insert, delete, and search. If the keys are totally ordered, then it can also support FindMin and

FindMax. Each key can be stored using 0(1) space.

In each of the following scenarios, describe briefly how the specifications can be achieved, or explain

why it is not possible.

(a) (3 pt) Suppose all the elements are given at the beginning, and there is no insertion or deletion

afterwards. Only the search operation will be used later, and a good guarantee on the worst

case search time is required.

(b) ( 3 pt) Elements will be inserted and deleted frequently. The average running time for insert,

delete and search is O ( 1).

(c) (3 pt) All operations insert, delete and search are used frequently. A guarantee on the worst

case running time is needed.

Page 4 of 13

(d) (3 pt) Insertions will be done frequently. However, only FindMin (i.e. returning the element

with minimum key) and DeleteMin (i.e., deleting the element with minimum key) are needed.

Moreover, only average 0(1) time is needed for each operation.

(e) (3 pt) Each key has value in {1,2, . . . ,n}. Each insertion or deletion has worst-case 0(1)

time. Moreover, FindRange[a .. b] needs to return all elements whose keys are in [a .. b], where

the running time is proportional to the number of elements returned.

Page 5 of 13

3 Binary Search Tree (15 points)

(a) (2 pt) What is the property that needs to be satisfied by a binary search tree?

(b) (2 pt) In addition to being a binary search tree, what property needs to be maintained for an

AVL tree?

(c) (6 pt) Suppose in a binary tree with n nodes, at every node, the difference of heights of the left

and the right sub-tree is at most b, where b is some parameter that is at least 1. Prove that

the height of the tree is at most O(blogn).

Page 6 of 13

( d) ( 5 pt) Recall that in a binary search tree, each node is defined as follows.

struct node {

int key;

}

node *left;

node *right;

node *parent;

Write a procedure in a C-like language that takes a pointer to the root of a binary tree, and

returns true if and only if it is a binary search tree that also satisfies the AVL property;

otherwise, it returns false.

Page 7 of 13

4 Sorting ( 30 points)

For each of the following scenarios, describe a method (briefly in words) to satisfy the specifications.

Please provide brief explanation. You may use pseudo code too, if you prefer.

(a) (6 pt) Suppose the elements are given in an array of length n, where each key is an arbitrary

number. Only 0(1) extra space should be used, and elements in the array should be rearranged

into a sorted order. Worst-case running time should be 0( n log n).

(b) ( 6 pt) Suppose the elements are given in a singly-linked list, where only the pointer to the head

is available to the algorithm. The algorithm should return the sorted elements in a singly-linked

list, by restructuring the links of the list without creating or destroying nodes. Moreover, extra

memory used should be as little as possible. If n is the number of elements in the list, the

algorithm should run in 0( n log n) time.

Page 8 of 13

(c) (6 pt) Suppose you are given a collection of n elements, each of which is an integer in the range

{l, 2, . . . , n }. Give an algorithm with optimal asymptotic running time that returns the set of

elements that appears at least once in the collection in sorted order.

(d) (6 pt) Suppose you are given an array of n elements, where each element is an integer in

{l, 2, 3, . . . , nk} for some small constant k 2: 2. The task is to sort the elements with asymptotic

running time strictly better than O(n logn). (You may use extra O(n) space.)

Page 9 of 13

(e) (6 pt) Suppose the elements are given in an array of length n, where each key is an arbitrary

number. However, you are guaranteed that for each element, its initial index position and

its final index position in sorted order differ by at most B. The value B is known to the

algorithm. The task is to rearrange the elements in the array into sorted order, with running

time O(n log B). You may use O(B) extra space.

(In the next question, we describe a data structure to solve this problem using only 0(1) extra

space.)

Page 10 of 13

5 Shifting Wrapped-Around Heap (20 points)

Recall that an array H[l. .K] can be used to represent a binary tree, where the children of H[i] are

H[2i] and H[2i + 1]. For K = 6, below is an example of a min-heap, where the root contains the

minimum value.

I �[i] I � I � I � I : I � I � I

(a) (3 pt) Draw the binary tree represented in the above example.

(b) In order to solve question 4(e) using only 0(1) extra space, we need to design a heap data

structure that is "shifting" within some other array A[O .. n -1], where K :S n. We assume that

the size K of the heap does not change. There are two variables s and r with the following

invariants.

• The elements of the heap are stored in A[s .. s + K -1].

• The heap elements are "wrapped around" such that the root of the heap is stored at A[r].

Study the following example carefully, where the above heap H is stored inside A with s = 2

and r = 4.

(3 pt) In terms of i, s, r and K, define an expression h(i) such that the element at H[i] is

stored at A[h(i)]. In the above example, h(l) = 4 and h(6) = 3.

Page 11 of 13

( c) ( 4 pt) Implement the operation ShiftHeap () that is called when s + K < n. The operation

overwrites the entry A[s + K] with A[s] . To avoid losing data, the operation should return the

original value of A[s + K] . After calling Shift O to the above example, the result is as follows.

(d) (4 pt) Suppose the root of the heap A[r] is overwritten with some potentially large value that

might cause the heap property to be violated. Write an operation FixRoot () to maintain the

heap property again. (You may use h(i) from above.)

Page 12 of 13

(e) (6 pt) Write an algorithm to solve 4(e) using only 0(1) extra space. In addition to the above

subroutines, you may assume the following subroutines are already defined for you.

• BuildHeap O: It constructs a heap from elements in A[O .. K -1] and sets s = r = O; the

running time is O(K), using 0(1) extra space.

• SortHeap O: It rearranges the elements in A[s .. s + K - 1] into sorted order in time

O(K log K) using 0(1) extra space.

END OF PAPER

Page 13 of 13