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.