Exercises 1.2 1. Old World puzzle A peasant finds himself on a riverbank with a wolf, a goat. and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Solve this problem for the peasant or prove it has no solution. (Note: The peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage to help him solve the problem. And it goes without saying that the wolf is a protected species.) 2. New World puzzle There are four people who want to cross a rickety bridge: they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person's pace. (Note: According to a rumor on the Internet, interviewers at a well-known software company located near Seattle have given this problem to interviewees.) 3. Which of the following formulas can be considered an algorithm for comput- ing the area of a triangle whose side lengths are given positive numbers a, b, and c? a. S = P(p-a)(p-b)cp -c), where p= (a + b + c)/2 b. S = the sin A, where A is the angle between sides bande c. S = jah, where he is the height to base a 4. Write pseudocode for an algorithm for finding real roots of equation ar? + bx+c=0 for arbitrary real coefficients a, b, and c. (You may assume the availability of the square root function sert(x).) 5. Describe the standard algorithm for finding the binary representation of a positive decimal integer a. in English b. in pseudocode 6. Describe the algorithm used by your favorite ATM machine in dispensing cash. (You may give your description in either English or pseudocode, which- ever you find more convenient.) 7. a. Can the problem of computing the number be solved exactly? b. How many instances does this problem have? e. Look up an algorithm for this problem on the Internet