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.