## Description

1. Josephus figured out where to stand in the vicious circle and survived. He also saved his

friend, the penultimate winner.

(a) For some small values of n, write down the position of the penultimate winner, I(n).

You may extend the following table as much as you like.

n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

I(n)

(b) Give a recurrence relation for I(n).

2. Give an O(n log k)-time algorithm that merges k sorted lists with a total of n elements into

one sorted list.

3. There are many duplications in the input sequence of n numbers, such that only O(log n)

numbers are distinct. Give an O(n log log n) worst-case time algorithm to sort such a sequence.

4. Design an O(n log n) worst-case time algorithm that counts the number of inversions in an

array of n numbers. Hint: Modify mergesort.

5. The k-th quantiles of a set of n numbers are the k − 1 numbers that divide the sorted set into

k equal-sized sets (to within 1). For example, if the set is {1, 2, 3, . . . , 99}, the 10-th quantiles

are 10, 20, . . . , 90. Design an O(n log k) time algorithm to find the k-th quantiles of a set.

Hint: Use median of medians.