This assignment is worth a total of 50 points.
All homework will be submitted electronically, using the curator system. You may submit your homework in any format that can be opened using Microsoft Word (including plain ASCII text). If you submit more than one version of your homework, we will store all submissions, but will actually grade the latest one. Make sure that your file contains at the top your name, your ID number, and your email address.
Where a question number is used, it refers to a question from the textbook.
1. Exercise 6.7
The resulting tree should have the following array structure:
Node: 0 1 2 3
4 5 6 7 8 9 10 11 12 13 14 15
Parent: 4 4 4 4 / 4 4 0 0
4 9 9 9 12 9 /
2. Exercise 6.13
Prove: L = (K-1)*n + 1.
Base case: n=0
Number of leaves in a non-empty tree with 0 internal nodes must be 1, the single
root node.
the number of leaves is (K-1)0+1 = 1. Theorem holds.
Induction hypothesis: Theorem holds for any full K-ary tree T' with
n-1 internals and L' leaves, where n>0:
L' = (K-1)*(n-1) + 1.
Induction step:
Take full K-ary tree T with n internals, and L leaves.
Since n>0 and n is finite, it must have at least 1 internal node p with K
leaves, at the bottom of the tree.
Delete p's K children.
You now have a new tree T' with n-1 internals (because p is now a leaf), and L'
= L-K+1 leaves (because K leaves were deleted, and p became a new leaf).
Or, L = L'+K-1.
Theorem holds for T' by induction hypothesis, so L' = (K-1)*(n-1)+1.
Hence, L = ((K-1)*(n-1)+1) +K-1 = (K-1)*n + 1. Theorem holds.
3. Exercise 7.6, but only for the following algorithms: Insertion Sort, Quicksort, Mergesort, and Radix Sort.
Insertion Sort: Stable. A swap is done only if the lower element's value is LESS.
Quicksort: NOT stable. During the partition process, elements of equal value can change order when swapped to the other side of the pivot. There is no simple way to prevent this in all cases.
Mergesort: can be made Stable. When merging 2 sublists, if 2 equal values are encountered, the value from the lower sublist should be chosen 1st to preserve their order in the merged output.
Radix Sort: Stable. When processing items from left to right, items should be appended to the end of the buckets (using tail pointers), thus preserving order.
4. Exercise 7.8
Here is how I derived a permutation that will give the desired worst case behavior:
a b c 0 d e f g First, put 0 in pivot index (0+7/2),
assign labels to the other positions
a b c g d e f 0 First swap
0 b c g d e f a End of first partition pass
0 b c g 1 e f a Set d = 1, it is in pivot index (1+7/2)
0 b c g a e f 1 First swap
0 1 c g a e f b End of partition pass
0 1 c g 2 e f b Set a = 2, it is in pivot index (2+7/2)
0 1 c g b e f 2 First swap
0 1 2 g b e f c End of partition pass
0 1 2 g b 3 f c Set e = 3, it is in pivot index (3+7/2)
0 1 2 g b c f 3 First swap
0 1 2 3 b c f g End of partition pass
0 1 2 3 b 4 f g Set c = 4, it is in pivot index (4+7/2)
0 1 2 3 b g f 4 First swap
0 1 2 3 4 g f b End of partition pass
0 1 2 3 4 g 5 b Set f = 5, it is in pivot index (5+7/2)
0 1 2 3 4 g b 5 First swap
0 1 2 3 4 5 b g End of partition pass
0 1 2 3 4 5 6 g Set b = 6, it is in pivot index (6+7/2)
0 1 2 3 4 5 g 6 First swap
0 1 2 3 4 5 6 g End of partition pass
0 1 2 3 4 5 6 7 Set g = 7
Plugging the variable assignments into the original permutation yields:
2 6 4 0 1 3 5 7
5. Exercise 8.8, parts (a), (b), and (d)
(a) 10 4 6 8 5
(b) 5 3 8 6 4
(d) 10 4 6 8 5