IntroductiontoAlgorithms3rdEdSolutions

Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. ...

Let X{1..n] and Y[1..n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the med...

Describe an O(n)-time algorithm that, given a set S of n distinct numbers and a positive integer $k \leq n$, determines the k numbers in...

The kth quantiles of an n-element set are the k 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Gi...

Suppose that you have a “black-box” worst-case linear-time median subroutine. Give a simple, linear-time algorithm that solves the selecti...

Suppose that an algorithm uses only comparisons to find the i th smallest element in a set of n elements. Show that it can also find the...

Show how quicksort can be made to run in O(n lg n) time in the worst case, assuming that all elements are distinct. The worst case for...