Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSCB63 Assignment 1
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. As we saw with Merge Sort, often see time (or space) complexity written as a recurrence relation (think
of any recursive algorithm). In class to determine the complexity in asymptotic notation of Merge Sort
we solved the recurrence relation as a closed form function. A recurrence relation is a function f(n)
defined in terms of itself. A closed form function f(n) is defined in terms of n. There are two common
ways to do this; repeated back substitution (what we did in class) or apply the Master Theorem.
Solving complexity recurrence relations is an important skill you will need in CSCC73.
We saw back substitution in class. The Master Theorem makes our life easier when the recurrence
relation has a specific format:
Generalized Master Theorem
Let a and b be positive real numbers with a ≥ 1 and b ≥ 2. Let T (n) be defined by
T (n) =
{
aT (dn/be) + f(n) if n > 1
d if n = 1
Then
(a) if f(n) = Θ(nc) where logba < c, then T (n) = Θ(n
c) = Θ(f(n)).
(b) if f(n) = Θ(nc), where logba = c, then T (n) = Θ(n
logb a logb n).
(c) if f(n) = Θ(nc), where logba > c, then T (n) = Θ(n
logb a).
The same results apply with ceilings replaced by floors.
For example, the run time of Merge Sort, T (n), can be expressed as
T (n) = 2T (
n
2
) + n
Applying the Master Theorem produces
T (n) = Θ(nlogb a log n) = Θ(nlog1 1 log n) = Θ(n log n).
Find a closed formula or apply the Master Theorem to determine the Theta complexity for each of the
following recurrences. You may need to be creative for the third one.
(a) A(n) = 3A(n/3) + 3n, where A(0) = 6. You can give your answer in Θ notation.
(b) A(n) = 3A(n/3) + 2n2, where A(0) = 1. You can give your answer in Θ notation.
(c) A(n) = 3 + 13
∑n−1
i=1 A(i), where A(1) = 1.
2. Show that n2 − 5n + 13 ∈ Θ(n2) using the definitions of Ω(·) and O(·) (not using limit laws).
3. Consider inserting the following keys in order into an AVL tree. Use the convention from lecture of
calculating the balance factor = height of left subtree minus height of right subtree. Only show your
tree at the indicated times.
3, 2, 14, 16, 12, 9, 6, 4, 5
1
Show your tree. Now insert
17, 18, 19, 20, 1
Show your tree. Now using the predecessor when needed, delete in order
6, 12, 5, 4, 3, 2, 1
Show your tree.
4. Consider an ADT defined such that an object of this type is a sequence of elements A = A[1], A[2], ..., A[n],
and the following two operations are supported:
• Insert( A, x, i ): Insert element x into the sequence A in position i. If |A| < i− 1, this operation
should put x at the end of the sequence.
• PartialAverage( A, i ): Return the ith partial average of the sequence A. The ith partial
average is defined as 1i
∑i
j=1A[j].
Describe a data structure for this ADT in which all operations work in O(log n) time, where n is the
length of the sequence. Explain why your algorithms are correct, and prove that they achieve the
required running time.
5. (a) In class we saw how to use an interval tree to store a set of intervals. Our interval tree had a search
operation allowing us to search for an interval overlapping a given interval. In this question we
want to produce an algorithm that given an unordered list of n intervals, determines in O(n log n)
worst case time, whether it contains a pair of intervals that overlap. Do not use an interval tree
for this algorithm.
Justify why your algorithm is correct and runs in the required time.
(b)
We now extrapolate our interval problem to a set of
rectangles whose edges are parallel to the x and y axes.
Suppose R1 and R2 are rectangles whose edges are parallel
to the x and y axes. Define what it means for R1 and R2
to overlap in terms of their left and right x coordinates
and top and bottom y coordinates.
(c) Describe an algorithm that, given an unordered list of n rectangles whose edges are parallel to the
x and y axes and which are specified by their left and right x coordinates and top and bottom y
coordinates, decides, in O(n log n) worst case time, whether it contains a pair of rectangles that
overlap.
Justify why your algorithm is correct and runs in the required time.
Hint: Make use of both your answer to (a) and the interval tree we learned in class.
6. Programming question coming soon...but will require you to implement a solution to the following
problem. You should submit your solution with this written assignment but it will not be graded
except to verify correctness and complexity of your code. Your code will be graded for this question.
Consider an ADT consisting of a set S of distinct integers and the following operations:
INSERT(S,x): Insert the element x into the set S. This operation has no effect if x is already in S.
DELETE(S,x): Delete the element x from the set S. This operation has no effect if x is not in S.
QUERY(S,x): Return true if x is in S and return false if x is not in S.
2
CLOSEST-PAIR(S): Return two integers in S which are closest together in value.
In other words, if CLOSEST-PAIR(S) returns the integers a and b, then they must satisfy the
condition
∀x∀y(x 6= y → |a− b| ≤ |x− y|).
It is an error if S contains fewer than two elements.
Describe a data structure to implement this ADT. All operations must be performed in O(log n) time,
where n = |S|. Describe any new information that will be stored. Justify why your algorithms are
correct and why they achieve the required time bound.
3