Consider the following scenario and then develop an algorithm that uses divide and conquer to solve it
Question:
Consider the following scenario and then develop an algorithm that uses divide and conquer to solve it
(a) Suppose you have 9 coins and one of them is heavier than others. Other 8 coins weight equally. You are also given a balance. Develop and algorithm to determine the heavy coin using only two measurements with the help of the balance. Clearly write your algorithm in the form of a pseudocode using the similar notation that we have used in the class to represent sorting algorithms
(b) Now, suppose you have n coins and one of them is heavier. You can assume that n is a power of 3. Generalize the algorithm you have developed in part (a) above for this case. Clearly write your algorithm in the form of a pseudocode using the similar notation that we have used in the class to represent sorting algorithms Determine the running time of your algorithm? Clearly show how you have arrived at the solution.
Fundamentals of Corporate Finance
ISBN: 978-0077861629
8th edition
Authors: Richard Brealey, Stewart Myers, Alan Marcus