I\'ve read the solution for the next question, but I have a question regarding t

Question

I've read the solution for the next question, but I have a question regarding the solution.

The question:
Suppose that in additionto the standard kind of comparator, we introduce an"upside-down"comparator that produces its minimum output on thebottom wire and its maximum output on the top wire. Show how toconvert any sorting network that uses a total ofc standard and upside-down comparators to one thatuses cstandard ones. Prove that yourconversion method is correct.

The solution:
We iterate over all the comparatorsin order. At a comparator (iq, jq), ifiq < jq, it is regular comparator we donnot perform any action and continue with next comparator.If iq > jq, it is and upside-down comparator then we need to standardize the comparator by changing it to (jq, iq).
· Now theoutput that used to be on iq is on jq and vice versa. Thus we also need to reverse iq and jq in all subsequent comparators. That is tosay, we consider all comparators (iq+k, jq+k)for 1 <= k <= r-q. If iq+k = iq then we change the comparator to be (jq, jq+k). Ifiq+k = jq, then change the comparator to be(iq, jq+k). we perform similar actions forjq+k= iq and jq+k = jq.We then repeat to the next comparator.
The proof of correctness is just asimple induction argument over the number of comparators iteratedover. To be equivalent, we simply need that after flipping the qthcomparator, all inputs to the (q+k)th comparators areconsistent with those of the original network. As for running time,we iterate over all r comparators and at each comparator weconsider it indeed outputs a network that uses only regularcomparators, it always terminate, and the output network isequivalent to the input network ?(r2).

The question:
If the same regular comparator C is subsequent comparator of 2 upside-down comparator Ax and By, when x < y. So when we go over comparator Ax and convert it to regular operator and perform the additional actions on operator C ( as described above) and create the new comparator D.

The question is:
Will comparator C be changed according to operator By, when we will iterate over subsequent comparators of By or after iterating over subsequent comparators of Ax, the comparator C will be moved from the all next stage?

Thanks

Explanation / Answer

Thoughtful answer

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.