Description
Question 1. (16 marks)
In the following procedure, the input is an array A[1..n] of arbitrary integers, A.size is a variable containing
the size n of the array A (assume that A contains at least n > 2 elements), and “return” means return
from the procedure call.
0. Procedure nothing(A)
1. A[1] := 0
2. A[2] := 1
3. for i = 3 to A.size do
4. s := 0
5. for j = 1 to i-1 do s := s + A[j]
6. if A[i] is not equal to s then return
7. return
Let T(n) be the worst-case time complexity of executing procedure nothing() on an array A of size n > 2.
Assume that assignments, comparisons and arithmetic operations, like additions, take a constant amount
of time each.
a. (4 marks) State whether T(n) is O(n
2
) and justify your answer.
b. (12 marks) State whether T(n) is Ω(n
2
) and justify your answer.
Any answer without a sound and clear justification will receive no credit.
Question 2. (14 marks) Let A be an array containing n integers. Section 6.3 of our textbook (CLRS)
describes a procedure, called Build-Max-Heap(A), that transforms array A into a max-heap in O(n)
time. That procedure works “bottom-up”, using Max-Heapify repeatedly.
Another way of transforming A into a max-heap is to insert the elements of A into the heap one at a
time. Specifically, the algorithm is as follows:
Build-by-Inserts(A)
A.heap-size := 1
for i := 2..n do
Max-Heap-Insert(A, A[i])
a. (4 marks) Give an example of an input array A for which the two procedures Build-Max-Heap and
Build-by-Inserts produce different outputs. Keep your example as small as possible.
b. (10 marks) Let T(n) be the worst-case time complexity of Build-by-Inserts for an input array A of
size n. Prove that T(n) is Θ(n log n). (Recall that the worst-case time complexity of Build-Max-Heap
is O(n), and therefore Build-Max-Heap is more efficient than Build-by-Inserts.)
Question 3. (20 marks)
Let In be the set of n integers {1, 2, . . . , n} where n is some power of 2.
Note that we can easily use an n-bit vector (i.e., an array of n bits) B[1..n] to maintain a subset S of In
and perform the following three operations (where j is any integer in In) in constant time each:
Insert(j): insert integer j into S.
Delete(j): delete integer j from S.
Member(j): return true if j ∈ S, otherwise return false.
2
Describe a data structure that supports all the above operations and also the following operation
Maximum: return the greatest integer in S
such that:
• The worst-case time complexity of operations Insert(j), Delete(j), and Maximum is O(log n)
each. The worst-case time complexity of Member(j) is O(1).
• The data structure uses only O(n) bits of storage.
Note that the binary representation of an integer i where 1 ≤ i ≤ n takes Θ(log n) bits. Assume that
any pointer also takes Θ(log n) bits.
A solution that does not meet all the above requirements may not get any credit.
Hint: Complete binary trees can be implemented without using pointers.
a. (6 marks) Describe your data structure by drawing it for n = 8 and S = {1, 2, 6}, and by explaining
this drawing briefly and clearly. Your drawing must be very clear.
b. (10 marks) Explain how the operations Insert(j) and Maximum are executed, and why they take
O(log n) time in the worst-case. Be brief and precise.
c. (4 marks) Explain how the operation Member(j) is executed, and why it takes O(1) time in the
worst-case. Be brief and precise.
3
