Please explain algorithm in words, give pseudocode, and discuss correctness and running time.

There is a collection of n >= 1 diamonds, consisting of n-1 good diamonds and one bad diamond. All good diamonds have the same weight, while the bad diamond is either lighter or heavier than a good diamond. You have a scale that allows you to compare the weights of any two (disjoint) subsets of the diamonds. Note that if n =1 then the diamond in the set is bad.

a.) Show that if n=3, then we can identify the bad diamond using the scale at most twice.

b.) Design an algorithm that identifies, for any k >= 0, the bad diamond in the collection of 3^k diamonds using the scale at most 2k times.