Due 1:30 PM, Wednesday, 07 February 2007


CPSC 101b  Homework #2  Algorithms and Adversaries

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. (6 points) You are given a collection of six seemingly identical coins.
   Five of the coins actually are identical but one coin is slightly heavier
   or slightly lighter than the others.  You have a digital scale (i.e., NOT a
   pan balance) that can weigh up to six coins at a time.  One algorithm for
   finding the odd coin is to weigh every coin---the odd coin will be heavier
   or lighter than the others and the reading on the scale is accurate enough
   to detect the difference.  This algorithm requires six weighings.  Give an
   algorithm that requires at most four weighings (half-credit for one that
   requires five weighings to do the job).  Your algorithm need not be in the
   form of a decision tree.  Note:  The weight of a true coin is NOT known in
   advance.


2. (5 points) Design a decision tree to identify the second lightest of 4
   distinct (with respect to weight) rocks (A, B, C, and D) using a pan
   balance.  For simplicity you may assume that rock A weighs less than rock B.
   How many "weighings" does your algorithm require in the worst case?  Can you
   also identify the lightest rock with the information you have gained from
   these weighings?

   Note:  To help establish the correctness of your tree, write down everything
   (i.e., all known inequalities) that is known at each decision point and each
   leaf.  Neatness counts!


3. (5 points) Consider the problem of determining the index I of a picture X
   in the collection of N pictures {P[1], ..., P[N]}, or 0 if X is not part of
   the collection.  Give an adversary argument that any algorithm for solving
   this problem must ask at least N questions of the form "Is X = P[K]?" for
   some 1 <= K <= N.  That is, describe a set S of realities and a procedure
   for using S to answer such questions (and to update S as needed) that an
   adversary could use to force any algorithm to ask at least N questions
   before it can solve the problem.  Explain why they have this property.


4. (4 points) Consider the problem of identifying both the smallest and the
   second smallest of a set of four distinct numbers X[1], X[2], X[3], and
   X[4].  Give an adversary argument that any algorithm for solving this
   problem must ask at least four questions of the form "Is X[i] < X[j]?".
   That is, describe a set S of realities and a procedure for using S to answer
   such questions (and to update S as needed) that an adversary could use to
   force the algorithm to ask at least four questions before it can solve the
   problem.  Explain why they have this property.


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


Supplementary Reading:  Kernighan, Chapter 2 (information representation);
  MacCormick, Chapter 7 (data compression)
							       CPSC-101-01/31/18