Computer Science 111  (Prof. Dobkin)

Problem Set 8:  
Due date: January 7, 2002 at 5PM -- please leave in the box on the
	second floor of the CS building.
--------------------------------
version of December 4.

1.  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.  Draw your
final collection of circles, and explain why it works and how you came up 
with it.

2.  Here is an instance of the Post Correspondence Problem:

	g1 = abab		h1 = baba
	g2 = bb			h2 = bab
	g3 = aa			h3 = aab
	g4 = ba			h4 = aba
	g5 = aab		h5 = aaba
	g6 = baba		h6 = ba
	g7 = abba		h7 = bab

   a) Find a solution.  That is find a set of corresponding strings from the g's
and the h's that yield the same string.  

   b) In class, we learned that the Post Correspondence Problem was undecidable
which we said meant that there was no method for solving it.  How were you 
able to solve this problem?

3.  a) Suggest an algorithm for solving the knapsack problem.  Give the 
pseudocode for your algorithm in sufficient detail for someone else to 
be able to implement it.

    b) Construct a knapsack problem of at least 6 weights and use your 
algorithm to solve it either by finding a set of weights that work or by
ahowing that no set of weights can exist.


Problem for discussion at holiday dinners.
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?