Due 1:30 PM, Wednesday, 31 January 2018 CPSC 101b Homework #1 Algorithms and Complexity Q: What does Bill Clinton play on the saxophone? A: An Al Gore rhythm! -- Anonymous Note: The assignment is due IN CLASS on the date above. REMINDER: When discussing an assignment with other students, you may write on a board or a piece of paper, but you may not retain any written or electronic record of the discussion. Moreover, you must engage in a full hour of mind- numbing activity (e.g., watching back-to-back episodes of Gilligan's Island) before you work on the assignment again. This ensures that you can reconstruct what you learned from the discussion, by yourself, using your own brain. The same rule applies to nonstudents and on-line sources. 1. a. (4 points) [Tartaglia, 15??] Three intensely jealous husbands and their beautiful wives need to cross a river using a small boat that can carry no more than two people at a time. Give an algorithm (*) to accomplish this task in such a way that none of the women is ever in the company of any of the men unless her husband is also present. How many crossings does your algorithm require? Do you think that there is an algorithm that requires fewer crossings? Why do you think so? Clarification: At the end of each crossing everyone in the boat must get out onto the river bank before the boat can be used again. No woman may ever be in the company of a man on the same bank of the river or in the boat crossing the river unless her husband is also present. b. (2 points) There is no solution for four couples unless there is an island in the middle of the river. Give an algorithm(*) for this case. Further Clarification: If a man is in the boat, he _could_ land anywhere, not just the intended destination. Should he do so, he must not encounter a woman whose husband is not present. Hint: Use the island to reduce the problem to that for three couples. (*) Your algorithm should specify where everyone is after each crossing. 2. (4 points) You have a beaker containing 12 ounces of an unknown liquid, and three empty, ungraduated beakers that can hold 7, 5, and 2 ounces, respectively. Give an algorithm for dividing the liquid into three equal parts, where the only operation permitted is pouring liquid from one beaker to another until either the first is empty or the second is full. How many pourings does your algorithm require? Do you think that there is an algorithm that requires fewer pourings? Why do you think so? Your algorithm should specify how much is in each beaker after each pouring. 3. (5 points) The digits in a digital clock are formed by turning on between one and seven of the lines in a grid with two adjacent squares: -- -- -- -- -- -- -- AA | | | | | | | | | | | | | | B C -- -- -- -- -- -- -- DD | | | | | | | | | | | | | E F -- -- -- -- -- -- GG Let the lines be labeled AA, B, C, DD, E, F, GG as shown above. Give a decision tree that determines which digit is displayed by testing one line at a time (i.e., only use questions like "Is line DD on?"). You may assume that one of the ten digits is displayed (i.e., that all the answers to your questions are correct for one of the ten digits). How many questions must your algorithm ask in the worst case? Do you think that there is an algorithm that asks fewer questions? Why do you think so? Your decision tree should show which numbers are possible at each node. 4. a. (2 points) You are given a collection of 8 seemingly identical coins and told that one might be lighter than the others (which all have the same weight). Give a decision tree for determining which (if any) is the light coin using only two weighings on a pan balance. b. (2 points) Now suppose that you must specify the entire sequence of weighings in advance before knowing the result of the first weighing. Give a decision tree for determining which is the light coin using only two weighings on a pan balance. (If your your decision tree for Part (a) has this property, then just say so rather than repeat it.) 5. (5 points) Give an algorithm to add two _signed_ 2-digit numbers +AB and -CD (which may have leading zeroes) using only addition/subtraction/comparison operations on individual digits (i.e., no multiplication or division). For simplicity assume that AB and CD are such that the sum of +AB and -CD is a signed 2-digit number +XY or -XY possibly with a leading zero. Note: +AB stands for a nonnegative two-digit number such as +12 or +01 or even +00. Note that the last two have leading zeroes. -CD stands for a nonpositive two-digit number such as -98 or -09 or even -00. Your task is to describe an algorithm (the one you learned in second grade, before you learned multiplication and division) to add +AB to -CD. By assumption the result will be a number between -99 and +99 and thus could be +12 or -09. Note the leading zero in the latter. 6. (1 point) How many hours did it take you complete the first five problems? 7. (Extra Credit Problem; 1 point) The outcomes of the first four games in Group C of the 2010 World Cup were England 1, United States 1 Slovenia 1, Algeria 0 Slovenia 2, United States 2 Algeria 0, England 0 so that the standings were . W D L P GF GA GD Slovenia 1 1 0 4 3 2 1 United States 0 2 0 2 3 3 0 England 0 2 0 2 1 1 0 Algeria 0 1 1 1 0 1 -1 where W = #wins, D = #draws, L = #losses, P = #points, GF = #goals scored, GA = #goals against, and GD = GF - GA = goal differential. Give an algorithm to decide which two teams advance from the group stage based on the outcomes of the two remaining games, England vs. Slovenia and Algeria vs. United States. Note that wins give 3 points to the winner and none to the loser; ties give 1 point to each team; and FIFA uses the following criteria to rank teams: * greatest number of points in all matches; * goal difference in all matches; * greatest number of goals scored in all matches; * greatest number of points in matches between tied teams; * goal difference in matches between tied teams; * greatest number of goals scored in matches between tied teams; * drawing of lots by the FIFA Organising Committee. Supplementary Reading: Kernighan, Introduction and Chapter 4 (algorithms); MacCormick, Chapter 1 (algorithms) CPSC-101b-01/16/18