Computer Science 111
Due Wed April 13, 5pm
Problem Set 8


1. (Coloring Circuits and Factoring)  

[Part A] In class we saw an example of a collection of connected circles
that behaves like an OR gate (we also saw a simpler example that gives a
NOT gate) with regard to coloring.  Using what we learned in class and
what we learned in the beginning of the semester, come up with a
collection of circles that behaves like an AND gate.  Hint: Be sure to
think about what you learned in the first few weeks of class!  Draw your
final collection of circles, and explain why it works and how you came up 
with it.

[Part B] We believe that factoring large numbers is hard.  In this
problem, you'll be asked to show that if you had a computer program which
could solve Coloring quickly, then it could factor numbers, too.  Suppose
that someone gave you a small circuit (using OR, AND, and NOT gates) for
multiplying two n-bit-long binary numbers.  Say that you also had a
program which took as input a collection of connected circles (some of
which may already be colored), and provided as output a valid coloring of
the uncolored circles using just three colors.  Describe how you could use
the program to factor (n+1)-bit numbers of the form N=pq, where p and q
are prime numbers larger than 3.  Describe each step and explain why it
works.

[Part C] Suppose you only have a program which tells you IF a certain
collection of circles (some of which may already be colored) could be
colored using only 3 colors.  How could you use this program to actually
find a valid coloring of a given collection of connected uncolored circles
using only 3 colors?  (You will need to run the program many times.)

[Part D] What if you had to do part C with a program that takes as input
only a collection of *uncolored* connected circles, and outputs whether a
valid coloring exists which uses only 3 colors.  Can you use this program
to find a valid coloring of a given collection of connected uncolored
circles using only 3 colors?  If you can't solve this problem completely,
explain where you are stuck and why your proposed solution might fail.  
You will get extra credit for a totally correct and complete solution.

2. (Puzzles inspired by the undecidability proof)  

[Puzzle A] Suppose a small-town barber who always tells the truth claims,
"I cut the hair of every person who lives in my town, except I don't cut
the hair of anyone who cuts their own hair."  What are the barber's
possible hairstyles?

[Puzzle B] You've been captured by the frumious bandersnatch, and placed
in a cave.  There are two exit doors: one has a hungry tiger behind it;
the other leads to freedom.  Before you stand two brothers -- one always
tells the truth, one always says the exact opposite of the truth.  They
both know which door leads to freedom.  You don't know which one is the
truth teller.  They allow you to ask any one of them only one Yes or No
question.  What do you ask? (Again, try to solve this on your own.  If you
get help from some outside source, acknowledge this on your solutions.)

Extra credit:  In a nearby cave, another hapless adventurer faces the two
brothers' three sisters: one always lies, one always tells the truth, and
one says whatever she wants (sometimes lies, sometimes tells the truth).  
Again there are two doors, and only one leads to freedom.  Each of the
sisters knows which door is which.  What is the smallest number of Yes/No
questions needed be able to always arrive at the correct answer?  Can you
do it with only two questions?