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