Problem 4 (15 + 10 = 25 points) Alice and Bob have different weighted coins of the same shape. Alice is

interested in finding the lightest coin, and Bob wants to find the heaviest coin. They have an

old-fashioned weighing balance (similar to the one in Lecture 1) which they can use for comparing

two coins. Help Alice and Bob with designing an algorithm that finds the lightest and heaviest

coins using at most 1.5 2 comparisons. Your solution should include

A clear pseudocode description of your algorithm.

A clear argument of its correctness. Your argument doesnt need to be overly formal, as long

as its clear and convincing.

An analysis of the number of comparisons.

4.1 Solve the problem for = 2 where is a non-negative integer number (i.e., is a power of

two.)

4.2 Generalize your solution for any > 0.

oblem 4(15+10=25 points) Alice and Bob have n different weighted coins of the same shape. Alice is interested in finding the lightest coin, and Bob wants to find the heaviest coin. They have an old-fashioned weighing balance (similar to the one in Lecture 1) which they can use for comparing two coins. Help Alice and Bob with designing an algorithm that finds the lightest and heaviest coins using at most 1.5n2 comparisons. Your solution should include - A clear pseudocode description of your algorithm. - A clear argument of its correctness. Your argument doesn't need to be overly formal, as long as it's clear and convincing. - An analysis of the number of comparisons. 4.1 Solve the problem for n=2k where k is a non-negative integer number (i.e., n is a power of two.) 4.2 Generalize your solution for any n>0