[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

/Discuss this assignment. /Solutions are available.

1. Many meetings

The United Nations wishes to schedule bilateral meetings between all of its member ambassadors, so that every ambassador meets exactly once with each other ambassador. These meetings will proceed in rounds, where in each round n/2 meetings, each involving two of the ambassadors, occur in parallel.

Devise an efficient algorithm for generating the meeting schedule, i.e. the list of which n/2 pairs of ambassadors meet in each round. You may assume that the ambassadors are numbered from 1 through n for convenience, that n is at least 2, and that n is a power of 2. Compute the running time of your algorithm.

2. Insistent select

The insistent select algorithm is a variant of QuickSelect that insists on getting an even split before continuing. The outline of the algorithm is:

  1. Choose a pivot uniformly at random from the n elements of the input array A.
  2. Partition the array into two arrays A1 and A2, where A1 contains all elements less than the pivot and A2 contains all elements greater than the pivot.

  3. If either A1 or A2 has more than cn elements, where c is a fixed constant to be determined below, go back to step 1 and try again.

  4. Otherwise, recurse on whichever of A1 or A2 contains the k-th smallest element, as in QuickSelect.

Insistent select permits a simpler analysis than QuickSelect, because we can compute an upper bound on its expected worst-case running time using the recurrence

where Theta(n) represents the cost of performing steps 1-3 once and S(n) is the expected number of times these steps are executed.

  1. Suppose c = 1/2. What are S(n) and T(n) in this case?
  2. Now let c = 3/4. What are S(n) and T(n) in this case?
  3. Are there any values of c we should avoid, even if we don't care how long the algorithm runs as long as it finishes eventually?

Assume throughout that all elements of A are distinct. You may give S(n) and T(n) in asymptotic form if convenient.

2014-06-17 11:58