Suppose that we have a collection of $n$ silver coins and a selection of $n$ gold coins. All of the

gold coins have a different weight. But for each silver coin, we know that there is a gold coin

that weighs exactly the same amount. Assume we have a device that can compare two coins,

and tell us which is heavier $($or if they weigh the same$).$ This is the only way we can compare

the weights.

a$)$ Give a brute force algorithm that we can use to arrange all of the coins into pairs that have

the same weight. What is the big$-$O efficiency of your algorithm?

b$)$ Prove that any algorithm solving this problem must make $(nlogn)$ comparisons.

c$)$ Give an algorithm $($based on quick sort$)$ that can solve the problem in time $O(nlogn)$ on

average. Explain why it works.