Analysis of Algorithms
                           ----------------------
                           Questions on Chapter 2
                           ----------------------


1. Suppose a binary tree is to be scanned level by level. That is the root is
   visited first, then the children of the root, then the grand-children etc.
   What extra data structure is needed in order to design a (non-recursive)
   algorithm for this scan? How long does the scan take?


2. Suppose we have records of employees, each containing a name, an employee
   number and a social security number. Suppose we want to be able to insert
   and delete records, and to find a record for an employee given the name, and
   to find a record given only an employee number, and to find a record given
   only a social security number. What data structure or combination of data
   structures allows these operations to be done fastest? How fast are they?


3. Suppose we want to keep track of a permutation of the numbers 1...n as it
   changes with time. The operations which need to be available are "find the
   i'th number in the permutation", "find the position of number j in the
   permutation", and "change the permutation by swapping the numbers at
   positions i and j". Find a data structure or combination of structures
   which implements these operations in O(1) time.


4. A file contains a large quantity N of numbers (say around 1000000). Design
   an algorithm to extract the n largest numbers from the file (say n is around
   1000). There is room in memory to hold an array a[1]...a[n] of n numbers,
   but there is not room to hold the whole file. The algorithm should scan the
   file sequentially just once.

   What data structure is suitable for use in this algorithm, how does the
   algorithm use it, and how long does the algorithm take to process each
   of the numbers in the file?


5. In an operating system, there is a queue of processes which are ready to run.
   The scheduler frequently removes the highest priority process from the queue
   in order to run it. New processes are occasionally inserted into the queue.

   Given that the queue is usually short and insertions are rare, what is the
   best way to implement the queue? Can it be implemented so that the highest
   priority process can be removed from the queue in O(1) time?


6. Prove that a range-search in a binary search tree takes, on average, time
   O(log(n)+R) where R is the number of entries found within the range.


7. When handling disjoint sets using parent trees as in chapter 2, suppose that
   items and sets have names. Suppose that the algorithm for FIND is given the
   name of an item and must return the name of the set containing it, and that
   the UNION algorithm is given the names of two sets and a new name for the
   union. Show that by using a couple of extra data structures in addition to
   the parent and size arrays, the operations remain efficient. How efficient
   are they now? Can a similar idea be used to implement a new MOVE operation
   efficiently? (MOVE moves an item from one set to another).


8. In simulation packages, one often has to keep track of a large collection
   of known future events. For each event is recorded the "time" at which it
   due to happen, and the action to be taken when it does happen. The events
   have to be processed in order of their recorded "times". When an event is
   processed, the associated action may cause new future events to be created,
   with known "times". These must not be processed until events with earlier
   "times" have been processed. What is a suitable data structure in which to
   hold events, and how efficient is it?


9. Consider the "game of life". This is a simulation in which there is a
   colony of cells on an infinite grid (chessboard). Each square may be
   empty, or may contain a live cell. During the simulation, cells are born
   (appear in empty squares) or die according to precise rules (see Kruse).
   A data structure is needed in which births and deaths can be recorded, and
   in which squares can be examined to see if they are occupied. What is the
   most suitable structure and how long do these three operations take, given
   that the number of live cells at any one time is reasonably small.


10* Another way of producing all permutations of a set of letters (say ABCD)
   is to insert the first letter (A) into all the possible positions of the
   permutations of the remainder (BCD). For example given the permutation CBD,
   the algorithm would produce ACBD, CABD, CBAD and CBDA. The complete list of
   permutations of ABCD produced by this algorithm is:

      ABCD, BACD, BCAD, BCDA, ACBD, CABD, CBAD, CBDA, ACDB, CADB, CDAB, CDBA,
      ABDC, BADC, BDAC, BDCA, ADBC, DABC, DBAC, DBCA, ADCB, DACB, DCAB, DCBA

   Make the algorithm more precise, specifying the data structures used.
   Does the algorithm require dynamic memory allocation (new & dispose)?
   Prove that the algorithm takes O(1) time on average to produce each
   permutation, i.e. O(n!) time in all.