HW9 SAMPLE ANSWERS 1. (a) 96 / \ 74 61 / \ / \ 32 47 50 36 / \ / 19 28 13 (b) If there are missing nodes at any level, these cells would have to marked in some way to indicate this. Also, a tree with only one node per level would require a very large array since most cells would be marked as "empty". (For example, if the binary tree has 10 nodes, 1 per level, the array would need to be as large as 2^10 cells. (c) Original heap: 96 47 61 32 13 50 36 19 28 96 / \ 47 61 / \ / \ 32 13 50 36 / \ 19 28 After first pass: 61 47 50 32 13 28 36 19 | 96 61 / \ 47 50 / \ / \ 32 13 28 36 / 19 After second pass: 50 47 36 32 13 28 19 | 61 96 50 / \ 47 36 / \ / \ 32 13 28 19 After third pass: 47 32 36 19 13 28 | 50 61 96 47 / \ 32 36 / \ / 19 13 28 After fourth pass: 36 32 28 19 13 | 47 50 61 96 36 / \ 32 28 / \ 19 13 After fifth pass: 32 19 28 13 | 36 47 50 61 96 32 / \ 19 28 / 13 After sixth pass: 28 19 13 | 32 36 47 50 61 96 28 / \ 19 13 After seventh pass: 19 13 | 28 32 36 47 50 61 96 19 / 13 After eighth pass: 13 | 19 28 32 36 47 50 61 96 13 Done: 13 19 28 32 36 47 50 61 96 2. public void insert(int item) { if (numElements == 1000) return; numElements++; data[numElements] = item; fixHeapUp(numElements); } private void fixHeapUp(int i) { // i = index of inserted element if (i > 0 && data[i] < data[i/2]) { swap(i, i/2); fixHeapUp(i/2); } } public int remove() { if (numElements == 0) throw new NoSuchElementException(); int min = data[1]; data[1] = data[numElements]; numElements--; fixHeapDown(1); return min; } private void fixHeapDown(int i) { // i is index of moved element if (i*2 <= numElements) { int j = i*2; // j is index of smaller child // assume left child is smaller first if (j+1 <= numElements && data[j+1] < data[j]) j++; // right is smaller instead if (data[i] <= data[j]) return; // heap is now fixed swap(i, j); fixHeapDown(j); } } 3. (a) Note that 3-nodes (nodes that have 2 data values inside) have two possible conversions when converted for a red-black tree. So the following answer is one of 16 possible solutions. R=red B=black 60B / \ 20R 91B / \ / \ 12B 43B 74R 94B / \ / \ / \ 8R 17R 28B 56B 71B 80B / \ / \ \ / \ 5B 11B 16B 19B 31R 75R 89R / 13R (b) [12 20 60] / / \ \ [8] [17] [43] [74 91] / \ / \ / \ / | \ [5] [9 11] [13 16] [19] [28 31] [56] [71] [75 80 89] [94] (As you traverse the tree, you encounter a 4-node [8 12 17] which splits, sending 12 up one level so the root now has 4 children. Continuing down the tree, 9 is inserted into the node with 11 in it.) 4. (a) public static > void sort(T[] table, int a, int b) { if (b - a > 0) { sort(table, a, (a+b)/2); sort(table, (a+b)/2 + 1, b); if (table[(a+b)/2] >= table[(a+b)/2 + 1]) merge(table, a, b); } } (After the sort steps, if the last element of the first half is less than the first element of the second half, no merge is needed.) (b) In the best case, the last merge step is never done (i.e. when the array is already completely sorted). In this case, each "merge" step take O(1) time, so merging arrays of size 1 into size 2 takes n/2 steps (since there are n/2 of these), merging arrays of size 2 into size 4 takes n/4 steps, etc. The total number of computational steps is n/2 + n/4 + ... + 2 + 1 = n - 1 = O(n). (c) Merge sort is stable only if the merge step merges the element from the left half first if there is a tie. 5. (a) Select three positions between a and b (inclusive) and determine which value is not the minimum or maximum of the three, assuming no duplicates. Swap this value into position a (to use it as the pivot) and then proceed. (b) O(n^2) since the pivot could be the minimum (or maximum), leaving a partition of n-1 elements. This can repeat, leaving a partition of n-2 elements. Thus the total number of operations in the partition step is n-1 + n-2 + ... + 1 = O(n^2). (In this case, QuickSort turns into Selection Sort effectively.) (c) It is not stable since it is possible that values that tie are both on the wrong side of the array and when they are swapped, their relative order will change. 6. (a) RAID COKE TIDE DOVE NIKE DOLE SURF WISK DAWN GAIN OREO LAYS LUVS ZEST RAGU TWIX AJAX CHEX OLAY AJAX OLAY TIDE OREO CHEX RAGU RAID GAIN TWIX COKE NIKE DOLE SURF WISK ZEST DOVE LUVS DAWN LAYS RAGU RAID GAIN DAWN LAYS ZEST CHEX TIDE NIKE WISK AJAX OLAY COKE DOLE DOVE OREO SURF LUVS TWIX AJAX CHEX COKE DAWN DOLE DOVE GAIN LAYS LUVS NIKE OLAY OREO RAGU RAID SURF TIDE TWIX WISK ZEST (b) O(nd): The k loops are constant loops (always running 26 times). The j loop runs in O(n) time, and it is run once for each iteration of the i loop which runs in O(d) time. (c) Radix sort is most like bucket sort since radix sort puts the strings into 26 different buckets depending on the current letter being analyzed. (d) Radix sort does NOT sort in place since it requires additional ArrayLists to do the sorting. The data is not sorted in the table array itself. 7. Sorting Algorithm 1: Merge Sort (note the first half is sorted and the next two quarters are sorted) Sorting Algorithm 2: Insertion Sort Sorting Algorithm 3: Selection Sort Sorting Algorithm 4: Quick Sort (with the value 7 as the pivot)