You don't have to completely answer the question. This one is difficult. I just need to get started, that's all. Please feel free to ask questions!Thank you.

3 Putting comparator networks into parallel form [40 points] Points: 15 for public tests, 10 for private tests, 15 for code review. In a comparison network, comparisons (x,y) and (a,b) may be done in parallel when the set {x,y} is disjoint from {a,b}. In that case, the two comparisons are working on separate pairs of wires, so they could execute simultaneously. We can represent a comparator network in parallel form as a list of lists. Each element list shows comparisons that can happen in parallel. For example, a parallel form for sort1.txt is the list of lists: [[(1,2),(3,4)],[(1,3),(2,4)],[(2,3)]] The command line for this part is Parallel filename Here, filename is again the name of a file containing a comparator network, like sort1.txt. Your code should write the parallel form to a file parallel.txt, in this format (for the above example): 12,34 13,24 23 On each line, please order the comparators by first wire number. So it would not be legal to have 34,12 because the first wire number (3) of the first comparison is greater than the first wire number (1) of the second. Please use the same spacing as above so that your output can be easily compared with expected output. This problem is actually the trickiest one in this assignment (hence 40 points instead of 30 ). I am not giving you an exact algorithm for finding the parallel form, but here is the basic idea. You are trying to break your network into levels that can run in parallel. So suppose you have some current level L that you are trying to fill. Then you want to pull comparators to the left, from the part of the input list (call it I) that you are processing. A comparator will get stuck iff it conflicts with a comparator to its left in I (i.e., shares a wire with that comparator), or with a comparator in L. If a comparator can be pulled all the way to the front of I, and it does not conflict with L, then it can be added to L : it is safe to run it in parallel with L