Suppose T is a multi-way tree in which each internal node has at least five and at most eight children. For what values of a and b is T a valid (a, b) tree? ANSWER: Since it has to satisfy the condition: 2 ? a ? (b+1)/2, the values are a = 4 and b = 8.

HERE ARE THE QUESTIONS: 1) For what values of d is the tree T of the previous exercise an order -d B-tree? HINT: The definition of an order-d deals with the minimum and maximum number of children an internal node can have.

2) Show each level of recursion in performing a four-way, external-memory merge-sort of the sequence given in the previous exercise. HINT: Draw the memory cache and manually process the requests using a pencil with a good erasure.