CS5800-Homework 2 Solved

1           Problem 1
Pseudocode 1 MergeSort(non-recursive)
 
Input: Divide array A into twohalves A-left, A-right.

right[b2..e2]

Output: Sorted array

1: function MergeSort(A,b1,b2,e1,e2)

2:                  i ← 0
First subarray is A-left[b1..e1], second subarray is A-
3:
temp ← [ ]
 
4:
while b1 ≤ e1 and b2 ≤ e2 do
 
5:
if A[b1] ≤ A[b2] then
 
6:
temp[i] ← A[b1]
 
7:
i ← i + 1
 
8:
b1 ← b1 + 1
 
9:
else
 
10:
temp[i] ← A[b2]
 
11:
i ← i + 1
 
12:
b2 ← b2 + 1
 
13:
end if
 
14:
end while
 
15:
while b1 ≤ e1 do
 
16:
temp[i] ← A[b1]
 
17:
i ← i + 1
 
18:
b1 ← b1 + 1
 
19:
end while
 
20:
while b2 ≤ e2 do
 
21:
temp[i] ← A[b2]
 
22:
i ← i + 1
 
23:
b2 ← b2 + 1
 
24:
end while
 
25:                return temp

26: end function
 
2           Problem 2
Since the max-heap float down,the node by consecutively swapping it with higher node below it, the smallest element must be in the leaf node. If we assume that node x contains the smallest element but it is not a leaf, and y is a child node of x, the value of x is greater than to the value of y by the max- heap property. However, this assumption is contradictory. Thus, the smallest element must be in a leaf node.

3           Problem 3
 

Figure 1: Problem 3

No, it is not. Represent the array as binary tree illustration (shows in figure 1), we can see that the leaf node which contains 7 in position 9 has parent’s node which contains 6 in position 4. According to the max-heap property, the value of parent’s node should be greater than the value of their children. Thus, this array is not a max-heap.

4           Problem 4
 

Figure 2: Step 1

 

Figure 3: Step 2

 

Figure 4: Step 3

5           Problem 5
 

Figure 5: Step 1

 

Figure 6: Step 2

 

Figure 7: Step 3

 

Figure 8: Step 4

 

Figure 9: Step 5

 

Figure 10: Step 6

 

Figure 11: Step 7

6           Problem 6
6.1         a. How would you represent a d-ary heap in an array?

Assuming 0 based indexing of array, an array represent a d-ary heap such that for any node we consider:

Parent of the node at index i (except root node) is located at index  

Children of the node at index i are at indices (d ∗ i) + 1,(d ∗ i) + 2,...,(d ∗ i) + d

6.2            b. What is the height of a d-ary heap of n elements in term of n and d?

logd n

6.3 c. Give an efficient implementation of Extract-Max in a d-ary max-heap. Analyze its running time in terms of d and n.

 

Pseudocode 2 Extract-Max

 

1: function Extract-Max(A)

2:                  max ← A[0]

3:                   A[0] ← A[n − 1]

4:                   n ← n − 1

5:                        d-ary Max-heap(A, n, d)

6: end function

 

A d-ary max-heap stores the largest element in its root. The Extract-Max returns the root node, so we copies the last node to the first and calls d-ary Max-heap to maintain the heap property. The number of times this recursively calls itself is bounded by the height if the d-ary heap. Therefore the running time is O(d ∗ logdn)

6.4 d. Give an efficient implementation of Insert in a d-ary max-heap. Analyze its running time in terms of d and n.

 

Pseudocode 3 Insertion

 

1: function Insert(A,n,element)

2:                   A[n] ← element

3:                   n ← n + 1

4:                       while n > 1 and A[parent(n)] < A[n] do

5:                             exchange A[n] with A[parent(n)]

6:                              n ← Parent(n)

7:                  end while

8: end function

 

The running time is O(logdn) because the while loop runs at most as many times as the height of the d-ary array.

6.5 e. Give an efficient implementation of Increase-Key, which flags an error if k < A[i], but otherwise sets A[i] = k and then updates the d-ary max-heap structure appropriately. Analyze its running time in terms of d and n.

 

Pseudocode 4 Increase-Key

 

1: function Increase-Key(A,i,k)

2:                     if k < A[i] then

3:                             error”k is smaller than A[i]”

4:                  end if

5:                  A[i] ← k

6:                       while i > 1 and A[parent(i)] < A[i] do

7:                             exchange A[i] with A[parent(i)]

8:                              i ← Parent(i)

9:                  end while

10: end function

 

The running time is O(logdn) because the while loop runs at most as many times as the height of the d-ary array.

7           Problem 7
According to the definition of Θ notation, there exists some positive constants c1,c2 so that the Θ(n) term is between c1n and c2n.

Solution: we guess that T(n) ≤ O(n2)

          T(n) ≤ c1(n − 1)2 + Θ(n)                                                               T(n) ≥ c2(n − 1)2 + Θ(n)

≤ c1(n − 1)2 + c0n                                                                                    ≥ c2(n − 1)2 + c3n

≤ c1(n2− 2n + 1) + c0n                                                                            ≥ c2(n2− 2n + 1) + c3n

≤ c1n2− 2c1n + c1 + c0n                                                                            ≥ c2n2− 2c2n + c2 + c3n

≤ c1n2− (2c1− c0)n + c1                                                                                                                  ≥ c2n2− (2c2− c3)n + c2

≤ c1n2 for n ≥ 1 and 2c1 ≥ c0                                                                                                     ≥ c2n2 for n ≥ 1 and 2c2 ≥ c3

Therefore, T(n) = Θ(n2)

8           Problem 8
 

Pseudocode 5 QuickSort

 

1: function QuickSort(A,p,r)

2:                    if p < r then

3:                                   q = Partition(A,p,r)

4:                                  QuickSort(A,p,q − 1)

5:                                   QuickSort(A,q + 1,r)

6:                  end if

7: end function

8:

9: function Partition(A,p,r)

10:               x ← A[r]

11:                i ← p − 1

12:                   for j = p to r − 1 do

13:                            if A[j] ≤ x then

14:                                    i ← i + 1

15:                                    exchange A[i] with A[j]

16:                         end if

17:               end for

18:                exchange A[i + 1] with A[r]

19:                return i + 1

20: end function

 

If all elements in the array have the same value, Partition(A,q,r) returns r which means the partition will always occur at the last position of the array. Since the execution time of the partition process only depends on n, Tpartition(n) = Θ(n)

T(n) = T(n − 1) + T(0) + Tpartition(n)

= T(n − 1) + Θ(n)

= T(n − 2) + 2Θ(n)

= T(n − 3) + 3Θ(n)

...

= T(n − n) + nΘ(n) = Θ(n2)

Therefore, the running time is Θ(n2)

9           Problem 9
According to the pseudo-code of QuickSort in last question, we could know that if the array is sorted in decreasing order, then the pivot element is leaa than all the other elements. We’ve already know

Tpartition = Θ(n) and T(n) = T(n−1)+T(0)+Tpartition(n) = Θ(n2) in last question. Therefore, the running time still is Θ(n2)

10          Problem 10
We guess that T(n) ≤ cn2 for some positive constant c, substituting this guess into recurrence, we obtain:

                                                                       T(n) ≤ max           (cq2 + c(n − q − 1)2) + Θ(n)

0≤q≤n−1

                                                                          = c ∗ max          (q2 + (n − q − 1)2) + Θ(n)

0≤q≤n−1

The expression q2 +(n−q−1)2 achieves a maximum over the parameter’s range 0 ≤ q ≤ n−1 at either endpoint. To verify this claim, note that the second derivative of the expression with respect to q is positive. This observation give us the bound max0≤q≤n−1 (cq2 + c(n − q − 1)2) ≤ (n − 1)2 = n2− 2n + 1. Continuing with our bounding of T(n), we obtain:

T(n) ≤ cn2− c(2n − 1) + Θ(n)

≤ cn2

Since we can pick the constant c large enough so that that c(2n − 1) term dominates the Θ(n) term.

Thus, T(n) = O(n2). Since T(n) = Ω(n2), the final answer is T(n) = Θ(n2)

11          Problem 11
In the most even possible split, Partition function produces two sub-problems, each of size no more than  , since one is size   and one of size  . In this case, QuickSort running time is:

 

According to the simple Master Theorem, a = 2,b = 2,c = 1,logb a = log22 = 1.c = logb a so case 2.

This recurrence has the solution T(n) = Θ(nlgn) which also is bounded by Ω(nlgn)

12          Problem 12
f(q) = q2 + (n − q − 1)2 f0(q) = 2q + 2(n − q − 1) ∗ (−1) = 4q − 2n + 2

f00(q) = 4 > 0

The second derivative is greater than 0 which means that f0(q) is negative left of f0(q) = 0 and positive right of it, which means that this is a local minimal. In

 

In this case, f(q) is decreasing in the beginnings of the interval and increasing in the end, which means that the maximal value must only be the endpoints. The endpoints are q = 0 and q = n − 1 which can make the expression achieves maximum.