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 9.4, also show how you derive the running time.
The partition and findpivot functions remain the same as in the book. This routine will modify array A so that the Kth smallest element is in position K, and will return the element value. The rest of the array will not necessarily be sorted.
Elem findK(Elem A[], int i, int j, int K){
if(j<=i) return i; // dont sort 0 or 1 elem
int pivotindex = findpivot(A, i, j);
swap(A, pivotindex, j); // put pivot at end
// k will be the first position in the right subarray
int k = partition(A, i-1, j, A[j]);
swap(A, k, j) // put pivot in place
if(K==k) return(A[k]);
if(K<k) return(findK(A, i, k-1, K));
else return(findK(A, k+1, j, K));
}
The high-level concept is:
findK(array, K)
pick pivot value p
partition around p
if left partition size == K-1, then Kth value is the pivot p,
return p
if left partition size > K-1, then Kth value is in the left
partition, so findK(left partition, K)
else, Kth value is in the right partition, so findK(right
partition, K)
The running time: Notice the key difference between this algorithm and Quicksort is that this algorithm only recurses on ONE of the 2 partition halves (if, else), whereas Quicksort recurses on BOTH halves. The average case analysis assumes that good pivots are chosen that always partition in half.
1st pass takes O(n) to partition the whole array,
2nd recursive pass only partitions 1/2 the array (unlike Quicksort which
recurses on both halves) taking O(n/2),
3rd pass only partitions 1/4 the array (1/2 of the previous 1/2) taking O(n/4),
4th pass only partitions 1/8 the array, (1/2 of the previous 1/4) taking O(n/8),
...
Note, the total # of recursion passes is logn.
Hence, O(n + n/2 + n/4 + n/8 +...) = O(n(1+1/2+1/4+...)) = O(n)
because 1/2+1/4+1/8+... never reaches 1.
2. Exercise 9.13
(a) Not acceptable. if k > n^2 then the result will be out of range of hash table size.
(b) Yes acceptable, but is not good. Worst possible hash function since all values hash to the same location.
(c) Not acceptable. it is not possible to recover the location of the element once it is stored using a random number.
(d) Yes acceptable, and is reasonably good if K is much larger than n and key values are randomly distributed.
3. Exercise 10.14 ("order four" = internal nodes can have at most 4 children)
IMS
------------||||-----------
| |----
---| |
----DG--- --K-- --P-- --U--
| | | | |
| | | |
ABC DE GH IJ KL MNO PR ST UW
4. Exercise 10.15
1: 0 15
2: 16 1500
3: 800 150,000
4: 40,000 15,000,000
5: 2,000,000 1,500,000,000
5. Exercise 13.7, also show how the space is partitioned.
K-d tree:
A(x=30)
\
B(y=85)
/
C(x=98)
\
D(y=52)
/
E(x=110)
The space would look like this:
| | |
| | E
| C |
| | |
| |---D--
| |
|-----B--------
A
|
|