I have a question in my homework document, and I'm having hard to time to visualize and understand the question. Question is the following:
We can represent an n-input comparison network with c comparators as a list of c pairs of integers in the range from 1 to n. If two pairs contain an integer in common, the order of the corresponding comparators in the network is determined by the order of the pairs in the list. Given this representation, describe an O(n + c)-time (serial) algorithm for determining the depth of a comparison network.
What does it mean to have pairs of integers in the context of comparison networks? Normally we used the notation below for denoting a comparison network where each horizontal line represents a number.
It means that if you have a pair (1, 2), that's one of those vertical lines, namely the one that connects horizontal lines 1 and 2.
So the top left part of this picture would be represented as (1, 2) (3, 4) (1, 3) (2, 4).
The depth of just that part is 2.