| 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: luc@cs.mcgill.ca.