Due 1:00 PM, Wednesday, 18 April 2018


CPSC 101b  Homework #9  Concurrency and Parallelism

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. (4 points) The last American Association for Artificial Intelligence meeting
   featured a workshop on robot building.  Each of the 10 participants received
   a bag of parts and a set of directions for assembling a robot.  Certain
   steps in the process require a fooble or a barble (specialized tools used
   only in robot assembly).  Moreover, left-handers must pick up and use the
   fooble before using the barble, while right-handers must pick up and use the
   barble before the fooble; and once construction has begun it is not possible
   to put down a tool until the robot is completed.

   As it happened, exactly half of the participants were left-handed and there
   were only 5 foobles and 5 barbles available for the workshop.  Thus after
   each participant had picked up her/his first tool and began building, no
   more tools were available and no one was able to proceed.  Deadlock!

   But suppose that some of the participants were Minskians and the rest were
   Schankians and that everyone knew to which school of artificial intelligence
   everyone belonged.  Give a modification of the directions subject to the
   constraints given above to avoid this deadlock without introducing more
   foobles or barbles into the system.  Show that each participant will
   eventually be able to construct a robot if s/he follows the new directions.


2. (6 points) (A Gossip Problem) An army has nine observation posts.  The
   commanding officer is stationed at Post A and needs to send the 6000-
   character orders of the day to each of the other eight posts.

   The posts are connected by a 3 x 3 toroidal grid of secure      A---B---C
   telephone lines; i.e., a 3 x 3 grid where each post in the      |   |   |
   topmost row is also connected to the corresponding post in      D---E---F
   the bottommost row, and each post in the leftmost column in     |   |   |
   also connected to the corresponding post in the rightmost       G---H---I
   column.  The four phone lines at each post are completely
   independent, and any can be used to send an N-character message to the post
   at the other end of the line in N seconds (the encryption is very good but
   very slow).

   Assume that actions not associated with sending individual characters are
   instantaneous.  Show how the orders of the day can be propagated to all
   posts in at most 6000 seconds.  Two-thirds credit for an algorithm that
   requires more time but at most 12000 seconds; one-third credit for a slower
   one.

   Hints:  You need not send the entire message at once.  Different lines can
   be used in parallel, although each line can only be used to send messages in
   one direction at a time.


3. (6 points) (Another Coin Problem) Suppose that you have 15 sacks of 100
   coins, where the coins in each sack are identical to each other, but those
   in different sacks have different weights.  To find the sack with the
   lightest coins, you have 6 assistants with pan balances.  Each pan balance
   can compare two coins at a time, but these very delicate instruments must
   be calibrated before each use so that each comparison takes an hour.  Give
   an algorithm for finding the sack with the lightest coins in 3 hours
   (i.e., using 3 sets of simultaneous comparisons).  Two-thirds credit for an
   algorithm that takes 4 hours; one-third credit for one that takes 5 hours.

   Hint:  If there were three sacks (A, B, and C) and three pan balances, then
   you could simultaneously compare
     - a coin from A with a coin from B
     - a coin from A with a coin from C
     - a coin from B with a coin from C
   and immediately deduce which sack contains the lightest coins.

   Note:  You may weigh coins from the same sack on different scales during the
   same round.


4. (1 point) How many hours did it take you complete the first three problems?


Reading:  MacCormick, Chapter 10 (What Is Computable)
							     CPSC-101b-04/09/18