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.