Tutorial 4--CS251--Winter 2000

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.