Due 5/4/99

Static search gives an opportunity to do cache conscious algorithm design.  We examined (B+1)-way static search algorithm that organizes its tree in an array using implicit pointers.   We saw that for B = 4, where 4 keys fit exactly into a cache line, we achieved a cache line utilization of 60%. It is interesting to see what the cache line utilization will be should we use a multi-way tree that has either too much or too little branching compared to the cache line size.  Cache line utilization is defined to be the fraction of each cache line that is touched by some reference to that cache line.

1.  Suppose 4 keys fit exactly in a cache line.  Calculate the cache line utilization for a 3-way static search algorithm (2 keys per node) and for a 9-way static search algorithm (8 keys per node).  How do these utilizations compare with the cache line utilization of 60% that we achieved for the perfect fit of the 5-way static search algorithm?

The data in a 5-way static search structure are not sorted but in a special order to make searching easy.

2. Design an algorithm that takes as input an array A and size N with A[0..N-1] in the order defined by the 5-way static search structure and outputs an array B[0..N-1] with the same keys in sorted order. (Hint: recall what an in-order traversal of a binary search tree does.)

3. Design an algorithm that takes a sorted array B[0..N-1] and size N as input and outputs an array A of the same keys in the order defined by the 5-way static search structure.