```                          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?
```