Describe an efficient algorithm to determine the depth of a comparison network with given representation.

Mr. Johnson draws an n-input comparison network with m comparators
according to the following conventions. The lines of the network go
left-to-right, and comparators are drawn vertically to connect two
lines. The network is drawn on an underlying grid, so that each
comparator occupies one of at most m columns. Comparators can share
columns, but they do not overlap. An example of such a drawing is given
below for a 4-input sorting networks.

1 2 3 4







































Mr. Johnson represents a given drawing as a list L of triples, in which
each triple (x, y, c) represents a comparator connecting line x to line
y in column c. For example, a representation of the sorting network
above might be the list L = ( (2,4,3), (1,3,2), (1,2,1), (2,3,4), (3, 4,
1)(. Describe an efficient algorithm to determine the depth of a
comparison network, where the input is Mr. Johnson’s representation of
a drawing of the network. Analyze your algorithm in terms of m and n.

1

2

3

4