(10 points) Divide and Conquer You have a rare gold coin. You dropped it into a
ID: 3723326 • Letter: #
Question
(10 points) Divide and Conquer You have a rare gold coin. You dropped it into a pile of fake gold coins that look identical. You want to find your real coin and all you know is that it weighs more than the fake coins. You have a scale that you can use to compare the weights of two coins (or two sets of coins). It will tell you which of the two is heavier 1. or if they are equal in weight a) (2 points) Design a brute force algorithm to solve this problem and state how many times your algorithm uses the scale if you have n coins (including the real one b (6 points) Describe a Divide and Conquer algorithm for this problemExplanation / Answer
Solution:
a)
The brute force algorithm is given below:
Algorithm:
In the worst case, the last coin will be the one which was fallen, so the number of times we used the scale will be
= n-1
b)
In divide and conquer approach we will follow the following steps:
The above algorithm will take log n comparisons to find the coin.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.