Suppose we have n devices with various size holes and n connectors with various

Question

Suppose we have n devices with various size holes and n connectors with various size pins such that each device fits exactly pin. Your only means of comparing these holes and pins is with

TEST(x;y): x is a hole and y is a pin; returns either hole is too big," hole is too small," or its hole perfectly."

(a) Devise an O(n2) worst-case divide-and-conquer algorithm for matching theholes and pins. (Hint: think QuickSort) (b) Prove the correctness of your algorithm (c) Prove that your algorithm runs in required time

Explanation / Answer

a)

Yes it can be done in O(n2) in worst case scenario using divide and conquer approach.

        Pick one pin from the lot given to you.
        Now use this pin to test all the holes given to you. (requires N trials)
            This partitions all holes into one of three cases:
                The hole is bigger than the pin used. (A).
                The hole is the same size as the pin used (B).
                The hole is smaller than the pin used. (C).
        Now reverse the process i.e use the pin which has the same size (the pin from set B) to test through all pins. (requires N trials)
            This partitions all pins into one of three cases:
                The pin is bigger than the hole tested (D).
                The pin is the same size as the hole tested (E).
                The pin is smaller than the hole tested (F).
            Result:
                Any hole picked from B will fit any pin picked from E. This will be the "Pivot" of the partition for your quick sort.
               They do not require any further testing and can easily be paired together.
                The holes in set A and the pins in set D have diameters wider than the pivot. The holes in set C and the pins in set F have diameters narrower than the pivot.
                Thus, we successfully partitioned the initial problem into two smaller problems.

Analysis

    Average case: O(N log N)
    Worst case: O(N^2) because we do not know the rank of the pivot until we have finished partitioning the set using the pivot. Same analysis as QuickSort.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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