Homework Assignment #1 Solution

Description

Question 1. (1 marks)

In the following procedure, the input is an array A[1::n] of n arbitrary integers, and \return” means the procedure stops immediately (breaking out of the loop of the procedure). Note that the indices of array A start at 1.

nothing(A)

1 A[1]= 1

• n = A:size

3	for i = 1 to n	// i = 1; 2; : : : ; n (including n)
4	for j = 1 to n 1	// j = 1; 2; : : : ; n 1 (including n 1)

• if A[j] 6= 1 A[j + 1] then return

• if i + j > n 1 then return

7 return

Assume that each assignment, comparison and arithmetic operation takes constant time.

Let T (n) be the worst-case time complexity of calling nothing(A) on an array A of size n 2.

Give a function f(n) such that T (n) is (f(n)).

Justify your answer by explaining why it is O(f(n)), and why it is (f(n)). Any answer without a sound and clear justi cation may receive no credit.

Question 2. (1 marks)

Design an e cient algorithm for the following problem. The algorithm is given an integer m 1, and then a (possibly in nite) sequence of distinct integer keys are input to the algorithm, one at a time. A print operation can occur at any point between keys in the input sequence. When a print occurs, the algorithm must print (in any order) the m smallest keys among all the keys that were input before the print.

For example, suppose m = 3, and the keys and print operations occur in the following order:

20; 15; 31; 6; 13; 24; print; 10; 17; 9; 16; 5; 11; print; 14; : : :

Then the rst print should print 15, 6, 13 (in any order), and the second print should print 6, 9, 5 (in any order).

Assume that at least m keys are input before the rst print occurs and that m does not change during an execution of the algorithm.

Describe a simple algorithm that solves the above problem with the following worst-case time complexity:

O(log m) to process each input key.

O(m) to perform each print operation.

Your algorithm must use a data structure that we learned in class.

State which data structure you are using and describe the items that it contains. Explain your algorithm for each operation clearly and concisely, in English.

Explain why your algorithm achieves the required worst-case time complexity described above. Prove that your algorithm is correct (Hint: use induction. What is your induction hypothesis?)

[The questions below will not be corrected/graded. They are given here as interesting problems that use material that you learned in class.]

Question 3. (0 marks) In class we studied binary heaps, i.e., heaps that store the elements in complete binary trees. This question is about ternary heaps, i.e., heaps that store the elements in complete ternary trees (where each node has at most three children, every level is full except for the bottom level, and all the nodes at the bottom level are as far to the left as possible). Here we focus on MAX heaps, where the priority of each node in the ternary tree is greater or equal to the priority of its children (if any).

1. Explain how to implement a ternary heap as an array A with an associated Heapsize variable (assume that the rst index of the array A is 1). Speci cally, explain how to map each element of the tree into the array, and how to go from a node to its parent and to each of its children (if any).

2. Suppose that the heap contains n elements.

1. • 1. What elements of array A represent internal nodes of the tree? Justify your answer.

1. • 2. What is the height of the tree? Justify your answer.

3. Consider the following operations on a ternary heap represented as an array A.

Insert(A; key): Insert key into A.

Extract MAX(A): Remove a key with highest priority from A.

Update(A; i; key), where 1 i A.Heapsize: Change the priority of A[i] to key and restore the heap ordering property.

Remove(A; i), where 1 i A.Heapsize: Delete A[i] from the heap.

For each one of these four operations, describe an e cient algorithm to implement the operation, and give the worst-case time complexity of your algorithm for a heap of size n. Describe your algorithm using high-level pseudo-code similar to that used in your textbook, with clear explanations in English. Express the worst-case time complexity of your algorithm in terms of and justify your answer.

Question 4. (0 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:heapsize := 1

for i := 2..n do

Max-Heap-Insert(A; A[i])

1. 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.

2. 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 5. (0 marks)

Let I_n 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 I_n and perform the following three operations (where j is any integer in I_n) 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.

1. 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.

2. Explain how the operations Insert(j), Delete(j), and Maximum are executed, and why they take O(log n) time in the worst-case. Be brief and precise.

3. Explain how the operation Member(j) is executed, and why it takes O(1) time in the worst-case. Be brief and precise.

4