Ex Bibliotheca

The life and times of Zack Weinberg.

Tuesday, 10 August 2004

# 1:20 PM

another math problem

Really an algorithmics problem, I suppose. Some definitions: for any set s with ns elements, which are totally ordered:

  • The median index ms is the number ⌊ns/2⌋;
  • The median Ms is the ms-th element;
  • The left half L(s) is the subset consisting of the elements numbered 1 … ms-1;
  • The right half R(s) is the subset consisting of the elements numbered ms+1 … ns.

Given a base set S with n totally ordered elements, find an algorithm which emits a list of medians, of the following sets in order:

  1. S
  2. L(S)
  3. R(S)
  4. L(L(S))
  5. R(L(S))
  6. L(R(S))
  7. R(R(S))
  8. …

and so on until all elements of the original set S have been emitted. In other words, the set is organized into a binary tree, each of whose subtrees corresponds to a subset of the original set, and is headed by the median element of that set; and then the tree is walked in breadth-first order.

The preferred solution is a nonrecursive algorithm with O(1) space requirement.