Analysis of Algorithms
                          ----------------------
                          Questions on Chapter 3
                          ----------------------


1. Use the idea of the quicksort algorithm to design an algorithm to find
   the k'th largest number in an unsorted array of n numbers. Prove that
   the algorithm takes O(n) time.


2. Suppose players A and B are playing a match consisting of a series of games
   in which the first player to win n games wins the match. Player A needs i
   more games to win, and player B needs j more games to win. Also suppose
   that player A has probability p of winning a game, otherwise B wins
   (probability 1-p). The probability P(i,j) that A will win the match
   when i>0 and j>0 is:

      P(i,j) = p*P(i-1,j) + (1-p)*P(i,j-1)

   Show that if P(i,j) is implemented as a recursive procedure, the time taken
   is O(2^n). Design a better procedure and estimate its running time.


3. Suppose we have a large number n of points in the plane, and we want to find
   the closest pair. One approach is to calculate the distance between each
   pair and find the minimum. This involves calculating O(n^2) distances.
   Suggest a divide-and-conquer approach. What difficulty occurs when trying to
   combine the results of subproblems? Assuming that the difficulty can be
   solved in O(n) time, how long does the algorithm take?


4. A company has two factories A and B which produce a and b units of the
   company's product per month respectively. The product is distributed to n
   different destinations numbered 1...n. The cost of distributing x units from
   A to destination i is given by a known function cost(A,i,x) which takes O(1)
   time to compute. Simlarly, the cost of distributing x units from B to i is
   cost(B,i,x). Each destination i has a demand of d[i] units per month (and we
   may assume that the sum of the d[i] is equal to a + b). The problem is to
   determine which factory should supply each destination (in any month) so as
   to minimise total cost. Devise a suitable algorithm for determining the
   minimum cost and estimate its running time. How would you adapt the algorithm
   so that a suitable distribution can be determined, as well as the minimum
   time?


5. Suppose we have two arrays a[1]...a[n] and b[1]...b[n], each sorted into
   increasing order. The problem is to find the median (n'th element) of the
   2n elements in the two arrays. Design an O(log(n)) algorithm to solve this.


6. There are n jobs to be done. For each job 1...n there are three numbers,
   a time t[i] which the job takes, a deadline d[i] by which the job should be
   completed, and a profit p[i] earned only if the job is completed by its
   deadline. The jobs have been sorted so that the deadlines are in increasing
   order, i.e. d[1] < d[2] < ... < d[n]. Let profit(n,x) be the maximum amount
   of profit obtainable from the n jobs within time x. Give a recursive design
   for calculating profit(n,x), turn it into a dynamic programming algorithm,
   and estimate the time it takes.


7. Suppose a method were found for multiplying 3 by 3 matrices using
   22 multiplications rather than 27. What divide-and-conquer method does
   this suggest for multiplying large matrices? Is it faster for very
   large (N by N) matrices than the O(N^log7) = O(N^2.81) method of Strassen?


8* Suppose that in a Travelling Salesperson Problem, length(S, i) is the
   length of a shortest route from node i to node 1 in the network, which
   visits all the nodes in set S once. Note that the solution to the TSP
   has i=1 and S="the set of all nodes". Design a recursive algorithm
   for calculating length(S, i), and show how it can be adapted to use
   dynamic programming. Show that the dynamic programming algorithm takes
   at least O(n^2 * 2^n) time. Is this any faster than the O(n!) direct
   approach? How much space does it use? Is it any use?