CSCB63 Assignment 1 - Winter 2020

Due 11.59pm, Feb. 2nd, 2020

Only a subset of the questions will be graded however you are responsible for all the material on this
assignment. Read the guidelines for plagiarism on the course website.

1. For the following subquestions, prove using the definition ofO(g), Ω(g) and Θ(g) (i.e., not using limits).

(a) (log 2 n)n∈O(nnlog^2 n)
(b) Show that log(n!)∈Θ(nlogn).

2. Basic red-black tree operations.

(a) Insert the following keys (in the given order) into an empty red black tree. Show
your final tree.

20 , 5 , 25 , 10 , 9 , 8 , 11 , 15 , 6 , 4 , 2 , 1 , 7 , 12 , 35

(b) Delete the following keys (in order) from the red black tree below.

5 , 28 , 31 , 32

Draw only your final tree.

3. The following question will explore the possibility of taking two red-black trees with a special property and merging them together into one red- black tree. (a) Explain how we can store the black height, bh(x), of an rb-tree in the rootx. Explain how we can maintain this extra field at no extra cost.

(b) Given two red black trees,T 1 andT 2 such that every key inT 1 is less than every key inT 2 , give an algorithm to mergeT 1 andT 2 into one tree. Make sure you also explain your time complexity in addition to the algorithm. You should first give an overview of your algorithm and then pseudocode that explains more completely. 4. Suppose that we wish to keep track of apoint of maximum overlapin a set of intervals - a point that has the largest number of intervals in the database overlapping it.

(a) Show that there will always be a point of maximum overlap which is an endpoint
of one of the segments.

1

(b) Design a data structure that efficiently supports the operations INTERVAL- IN-
SERT, INTERVAL-DELETE, and FIND-POM, which returns a point of maximum
overlap. (Hint: Keep a red-black tree of all the endpoints. Associate a value of
+1 with each left endpoint, and associate a value of -1 with each right endpoint.
Augment each node of the tree with some extra information to maintain the point
of maximum overlap.)

5.Programming questionwarm up. To enable you to solve the programming ques- tion answer the following question first. It willnot be gradedbut will make coding much easier.

Consider an ADT consisting of a setSof distinct integers and the following operations:

INSERT(S,x):Insert the elementxinto the setS. This operation has no effect ifx
is already inS.
DELETE(S,x):Delete the elementxfrom the setS. This operation has no effect if
xis not inS.
QUERY(S,x):Return true ifxis inSand return false ifxis not inS.
CLOSEST-PAIR(S):Return two integers inSwhich are closest together in value.
In other words, if CLOSEST-PAIR(S) returns the integersaandb, then they must
satisfy the condition

∀x∀y(x 6 =y→|a−b|≤|x−y|).

It is an error ifScontains fewer than two elements.

Describe a data structure to implement this ADT. All the usual operations of IN-
SERT, DELETE and QUERY must be performed inO(logn) time, wheren=|S|and
CLOSEST-PAIR must be in performed inO(1).

Describe any new information that will be stored. Justify why your algorithms are
correct and why they achieve the required time bound.

6. Implementation details of Q5 with starter code will be posted soon. The implementation of Q5 starter code is on MarkUs - you can find it here: https://markus.utsc.utoronto.ca/cscb63w

2