You are seated on an electric chair, and there is a two-pan balance before you. A...

  

Transcribed Image Text:

You are seated on an electric chair, and there is a two-pan balance before you. A two-pan balance is something that is used to compare the weight of two objects. It's one of the things Lady justice has. On the right pan, is an object of unknown weight W. The left pan is empty. You are given N tokens and all of these tokens have weight w. Using these N tokens and the two-pan balance, you have to approximate W as efficiently as possible. L.e. Provide an algorithm to find a and b such that and a and b are in terms of w (If W is heavier than Nw, then report that). There is a catch, however. Below the left pan is a switch. If the weight of the tokens in the left pan is greater than W, the switch will be hit, and you will be electrocuted to death. Moreover, each time you wish to change the number of tokens on the left pan, the left pan must be emptied before the desired number of tokens is placed on the left pan. Le. you are not allowed to add or remove tokens from the left pan one by one. Given this scenario, approximate W when: You have one life to spare. You have an unlimited number of lives to spare. (\God I wish I was this person.") You have two lives to spare. Note that in this problem, an algorithm A is said to be more efficient than another algorithm B if and only if the number of steps taken in the worst case scenario for A is smaller than the number of steps taken in the worst case scenario for B. A step here means the act of emptying the left pan and placing a new number of tokens on it. Hint: For this question, you don't need to come up with a pseudo code. You just need to precisely describe your approach for each part in a small paragraph. You are seated on an electric chair, and there is a two-pan balance before you. A two-pan balance is something that is used to compare the weight of two objects. It's one of the things Lady justice has. On the right pan, is an object of unknown weight W. The left pan is empty. You are given N tokens and all of these tokens have weight w. Using these N tokens and the two-pan balance, you have to approximate W as efficiently as possible. L.e. Provide an algorithm to find a and b such that and a and b are in terms of w (If W is heavier than Nw, then report that). There is a catch, however. Below the left pan is a switch. If the weight of the tokens in the left pan is greater than W, the switch will be hit, and you will be electrocuted to death. Moreover, each time you wish to change the number of tokens on the left pan, the left pan must be emptied before the desired number of tokens is placed on the left pan. Le. you are not allowed to add or remove tokens from the left pan one by one. Given this scenario, approximate W when: You have one life to spare. You have an unlimited number of lives to spare. (\God I wish I was this person.") You have two lives to spare. Note that in this problem, an algorithm A is said to be more efficient than another algorithm B if and only if the number of steps taken in the worst case scenario for A is smaller than the number of steps taken in the worst case scenario for B. A step here means the act of emptying the left pan and placing a new number of tokens on it. Hint: For this question, you don't need to come up with a pseudo code. You just need to precisely describe your approach for each part in a small paragraph.