Problem-Set-05 - The 5th homework of Jan Stelovsky\'s class. PDF

Preview

Summary

The 5th homework of Jan Stelovsky's class....

Description

#1. Peer Credit Assignment 1 Point Extra Credit for replying Please list the names of the other members of your peer group for the week of 10/08-10/10 and the number of points you think they deserve for their participation in group work on this day. ● Dal

avid Col

#2. Analysis of d-ary heaps (11 pts) In class you did preliminary analysis of ternary heaps. Here we generalize to d-ary heaps: heaps in which non-leaf nodes (except possibly the right-most one) have d children. a. (3) How would you represent a d-ary heap in an array? Answer this question by: ● Giving an expression for J-th-Child(i,j): the index of the j-th child as a function of the index i of the given node, and the child index j within the given node. J-th-Child(i, j):

d(i - 1) + j + 1

● Giving an expression for D-Ary-Parent(i): the index of the parent of a node as a function of its index i within the array. D-Ary-Parent(i):

floor((i - 1)/d + 1)

● Checking that your solution works by showing that D-Ary-Parent(J-th-Child(i,j)) = i (when you start at node i, and apply your formula to go to a child, and then your other formula to go back to the parent, you must end up back at i). Start by plugging the expressions into the formula D-Ary-Parent(J-th-Child(i,j)): = floor((d(i - 1) + j + 1 - 2)/d + 1) = floor((di - d + j - 1)/d + 1) = floor(i + (j - 1)/d //Taking the floor rounds down = i

b. (2) What is the height of a d-ary heap of n elements as a function of n and d? By what factor does this height differ from that of a binary heap of n elements? The height of a d-ary heap of n elements is h = floor(lgdn), because d-ary heaps use log base d as opposed to binary heaps, which use log base 2. This height differs from that of a binary heap of n elements by a factor of 1/(lg d). c. (3) Give an efficient implementation of Extract-Max in a d-ary max-heap. (Hint: How would you modify the existing code?) Analyze the running time of your implementation in terms of n and d. (Note that d must be part of your Θ expression even if it occurs in a constant term.) HEAP-EXTRACT-MAX (A, n) 1 if A.heap-size < 0 2 error "heap underflow" 3 if n > 1 4 max = A[0] 5 A[0] = A[n] 6 Max-Heapify (A, 0) 7 return max MAX-HEAPIFY (A, l) 1 largest = l 2 for A[i] up to A[d] 3 if A[l] < A[i] 4 exchange A[l] with A[i] 5 MAX-HEAPIFY (A, i) The runtime of this code is Θ(dlgdn); each time MAX-HEAPIFY is called, a new level in the heap is used, and thus the cost to traverse through a heap is lgdn. d represents the maximum number of children, and it will cost d to check each child, which gives us a total runtime of Θ(dlgdn). d. (3) Give an efficient implementation of Insert in a d-ary max-heap. Analyze its running time in terms of n and d. MAX-HEAP-INSERT (A, key) 1 A.heap-size = A.heap-size + 1

2

A[A.heap-size] = -∞

3

HEAP-INCREASE-KEY (A, A.heap-size, key)

HEAP-INCREASE-KEY (A, i, key) 1 if key < A[i] 2 error "new key is smaller than current key" 3 A[i] = key 4 while i > 1 and A[PARENT(i)] < A[i] 5 exchange A[i] with A[PARENT(i)] 6 i = PARENT(i) The runtime is Θ(lgdn) since lgdn is the cost to traverse through a heap.

#3. 3-way Quicksort (14 pts) In class we saw that the runtime of Quicksort on a sequence of n identical items (i.e. all entries of the input array being the same) is O(n2). All items will be equal to the pivot, so n-1 items will be placed to the left. Therefore, the runtime of QuickSort will be determined by the recurrence T(n) = T(n-1) + T(0) + O(n) = O(n2) To avoid this case, we are going to design a new partition algorithm that partitions the array into three parts, those that are strictly less than the pivot, equal to the pivot, and strictly greater than the pivot. a. (6) Develop a new algorithm 3WayPartition    , p, r ) that takes as input array A and two (A indices p and r and returns a pair of indices (e, g). 3WayPartition   should partition the array A around the pivot q = A[r] such that every element of A[p..(e-1)] is strictly smaller than q, every element of A[e..g-1] is equal to q and every element of A[g..r] is strictly greater than q. Hint: modify Partition(A, p, r) presented in the lecture notes and in the textbook, such that it adds the items that are greater than q from the right end of the array and all items that are equal to q to the right of all items that are smaller than q. You will need to keep additional indices that will track the locations in A where the next item should be written. 3WayPartition(A, p, r) 1 pivot = A[r] 2 i = p - 1 3 j = r; 4 for (k = p; k < j; k++) 5 if (A[k] < pivot) 6 i++

7 8 9 10 11 12 13

exchange A[i] with A[k] else if (A[k] > pivot) j-exchange A[j] with A[k] k-exchange A[r] with A[j] return [i + 1, j + 1]

b. (5) Develop a new algorithm 3WayQuicksort which uses 3WayPartition to sort a sequence of n items. Again, 3WayPartition   returns a pair of indices (e, g). 3WayQuicksort (A, p, r) 1 if (p < r) 2 data = 3WayPartition(A, p, r) 2 start = data[0] 3 end = data[1] 4 3WayQuicksort(A, p, start - 1) 5 3WayQuicksort(A, end, r)

c. (3) What is the runtime of 3WayQuicksort   on a sequence of n random items? What is the runtime of 3WayQuicksort on a sequence of n identical items? Justify your answers. The runtime of 3WayQuicksort on a sequence of n random items is O(nlgn); it would be the same as the runtime on a sequence of random items using regular quicksort. The runtime of 3WayQuicksort on a sequence of n identical items would be O(n), since it only goes through each element once and partitions the array once. The partition will return the same minimum and maximum values as the ones it was given....