Return to Analysis of Algorithms Home Page

This page contains a list of interesting problems that we are aware of. You are encouraged to submit new ones by posting directly on the Bulletin Board. Typically 5 to 10 lines of TeX should be best for further editing.

A digest of the main problems will be compiled here periodically by the Problem Editor.

Summer 97

• Problem 1. [ Problem | Solution ] By Conrado Martinez, 11-Jul-97. The depth of the j-th element in a random binary search tree of size n.
• Problem 2. [ Problem ] By Conrado Martinez, 11-Jul-97. Quicksort with median-of-three partitioning and halting on small subfiles.
• Problem 3. [ Problem | Comments ] By Hsien-Kuei Hwang, 23-Jul-97. A limit distribution and zeros of a polynomial.
• Problem 4. [ Problem ] By Wojtek Szpankowski, 25-Jul-97. What is the distribution of node levels and height in digital search trees built on Bernoulli sources?
• Problem 5. [ Problem ] By Ed Coffman, 01-Aug-97. Analyse the waste in First-Fit bin-packing.