Analysis of Algorithms
                          Questions on Chapter 4

1. The following is a sparse representation of a network, in which each
   edge out of a node has its label and its destination node recorded.

      node      edges out
      ----      ---------
       A         7B, 4D
       B         5C, 5D
       C         1D, 1E, 3Z
       D         7E
       E         1B, 8Z

   Draw the network and write down its label matrix (with zeros for
   non-existent edges). Treating it as a flow network, find the
   maximum flow in it using the standard algorithm in which flow-
   augmenting paths are sought in order of maximum flow-increase.
   For each flow augmenting path, show how the contents of the
   priority queue change during the search for the path (give the
   queue contents as a list of nodes with priorities). Note -
   you should only need 4 paths to reach a max flow of 11.

2. In what sense can the algorithm for finding the shortest path from
   A to Z in a network be classed as a dynamic programming algorithm?

3. Both depth first and breadth first search can be done without recursion
   using a list of nodes remaining to be dealt with. Depth first search
   organises the list as a stack, while breadth first search organises it
   as a queue. Both take about the same time, but the space required for
   the list may be very different. Give an example of a type of network
   (sparse representation) in which a depth first stack reaches a size
   O(n) at some time during the search, whereas a breadth first queue
   remains always at size O(1). Also give an example where a breadth first
   queue reaches size O(n), whereas a depth first stack remains O(1).

4. The MINIMUM SPANNING TREE problem is as follows. Suppose we have a
   network of undirected edges representing a collection of cities (nodes)
   and distances between them (edge labels). Suppose we need to build a
   minimum length railway system joining all the cities, consisting of a
   number of two-way inter-city links. For example the network:

          A  B  C  D  E  F  G
       A  0  1  0  0  0  2  6
       B  1  0  1  2  4  0  0
       C  0  1  0  0  4  0  0
       D  0  2  0  0  2  1  0
       E  0  4  4  2  0  2  1
       F  2  0  0  1  2  0  0
       G  6  0  0  0  1  0  0

   has a minimum length railway consisting of links AB, BC, BD, DE, DF
   with total length 8. Such a railway system will have no cycles, since
   one link in the cycle could be removed, without destroying the ability
   to get from any city to any other. Hence the name "min. spanning tree".
   The problem can be solved by building the railway system link by link,
   adding at each stage the shortest edge from the partial system to the
   remaining nodes. Show that this can be achieved with a suitable
   network scanning algorithm. How long does the algorithm take for dense
   or sparse representations?

5. There is an algorithm for the above problem which does not use network
   search. Instead, the set of all edges is considered in order of increasing
   length. Each edge is added to the system if it does not form a cycle with
   the partial system so far, and otherwise is discarded. The links added so
   far divide the nodes into groups with mutual connections, and the addition
   of a new edge conbines two groups into one. Assuming that this approach
   works, what data structure should the edges be held in, what data structure
   should the nodes be held in, how long does the algorithm take, and how does
   it compare to the above one?

6. In critical path analysis, there are a number of jobs to be done to
   complete a project such as building a house. It is known how long each job
   takes, and in addition there are a number of constraints of the form "Job A
   must be completed before job B can start", e.g. the walls must be built
   before the roof can be added. The problem is to find the minimum time
   in which the project can be completed, and to find a "critical path",
   i.e.  a sequence of jobs which forces the project to take that long.
   Show how to represent the problem as an acyclic network (DAG), and show
   how to solve the problem using the longest path algorithm.

7. Build (by hand) a network to represent the regular expression:
   (a + b)(a*b + b*a) and illustrate way in which the network can be used
   to match strings against the pattern, using the strings "aaab" and "baba".

8* This question has nothing to do with networks, but is interesting.
   Suppose there are n numbers a[1]...a[n] of n bits each, i.e. in the range
   0...2^n-1, and you have to find the maximum value among them using only
   questions of the form "is a[i] < k?". Find an algorithm using only O(n)
   questions even in the worst case.