CSC 344
Homework 4

Assigned Apr. 2, due Apr. 16

• You have n coins, all identical except that one is a counterfeit, and weighs a little less than the rest. Your mission is to figure out which one is counterfeit. Your only tool is a balance scale: you can pile as many coins as you like on each side, and it'll tell you either "the two sides balance", "the left side is heavier", or "the right side is heavier".
  

  1. Find an efficient sequential algorithm to do this. Analyze its time complexity.
  2. Find an efficient PRAM algorithm to do this (using a bunch of friends who each have their own balance scales). Analyze the number of processors (friends) necessary, and the amount of time involved.
  3. Does your algorithm correspond to the EREW PRAM model, or CREW, or CRCW? If one of the latter, convert it to an algorithm for the EREW PRAM model and re-analyze.
  4. Convert your algorithm to work for a 2-dimensional mesh. Analyze the size of mesh you need, and the amount of time necessary.

• An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison the king's wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately, they don't know which one. The poison works slowly: it takes a full month for the person to die.

  The king doesn't want to throw away all that good wine, so he has his food-tasters test it. But how many tasters does he need? How many bottles should each taster taste, and when? How many months does it take to find the poisoned bottle, and how many tasters will die in the process? If the king has to pay tasters by the month, how much money will it cost him?

  Try to come up with several algorithms with various combinations of number of tasters, number of deaths, and time. It's easy to get an algorithm that takes n tasters and 1 month, or 1 taster and n months; both of these cost the king $O(n). With a little more thinking, you can find an algorithm that takes O(sqrt(n)) tasters and O(1) time (costing $O(sqrt(n))), or lg(n) tasters and lg(n) time (costing $O(lg²(n))). For full credit, find an algorithm that takes lg(n) tasters and only 1 month, costing $O(lg(n)).

• Induction proofs on natural numbers: problems 7.2, 7.6, and 7.9 from the textbook
• Induction proofs on sets: problem 7.7 from the textbook
• Induction about binary trees: problem 7.13 from the textbook
• Recurrence relations: problems 7.22 and 7.23 from the textbook