/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 A₁ and A₂, where A₁ contains all elements less than the pivot and A₂ contains all elements greater than the pivot.

3. If either A₁ or A₂ 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 A₁ or A₂ 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

• T(n) <= Theta(n)*S(n) + T(cn)

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.