Homework Assignment #1 Solution

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.




Procedure nothing(A)



A[1] := 0



A[2] := 1



for i = 3 to A.size do



s := 0



for j = 1 to i-1 do s := s + A[j]



if A[i] is not equal to s then return



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(n2) and justify your answer.

b. (12 marks) State whether T (n) is (n2) and justify your answer.




Any answer without a sound and clear justi cation 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. Speci cally, 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 di erent 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 e cient than Build-by-Inserts.)







Question 3. (20 marks)




Let In be the set of n integers f1; 2; : : : ; ng 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 2 S, otherwise return false.




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 = f1; 2; 6g, and by explaining
this drawing brie y 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