|Question 1||Optimized algorithms. Given are 10n arrays of varying sizes, each containing a sorted list. We would like to end up with only n sorted arrays (of arbitrary sizes!), while the only operation allowed is the standard merge of two sorted arrays. Write an algorithm for this that minimizes the number of comparisons.|
|Question 2||Followup (hard). If N is the total number of elements, show that the total number of comparisons in the algorithm above is O(N), regardless of how small or large n is.|
|Question 3||Tree algorithms. Give a linear time (in the number of nodes) algorithm to compute for each node in a binary tree the size of its subtree.|
|Question 4||Suffix tries. Show that the space requirement for a suffix trie for a binary file consisting of n bits is Omega (n^2) in the worst case.|
|Question 5||Search trees. Given is a sorted array of n different integers. Give a linear time algorithm for creating a binary search tree of optimal height (floor (log_2 n)).|
Copyright © 2000 Luc Devroye. Email: firstname.lastname@example.org.