Problem Set 8: Solution

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.

Answer:

If you compare this graph to the graph for OR gate, you'll see that they are quite similar. Actually, the only difference
is at the toppest two circles. In the graph for OR gate, the Green (True) circle is on the left side and the Red (False)
circle is on the right side.
Notice the following facts:
* the output circle has the opposit value of circle k: since k, output and the Yellow circle are connect to each other,
they must have different colors. When k is T(rue), output is F(alse). When k is F(alse), output is T(rue).
* if a is T(rue), k is F(alse); if a is F(alse), k is T(rue).
* if j is T(rue), k is F(alse); if j is F(alse), k is T(rue).
* if X = Y, then a = X = Y: since a,b,c are connected to each other, they must have different colors. if X = Y, neither
b or c can have the same value as X (Y), so a must have the value as X (Y).
* if X <> Y (i.e. X and Y have different values), then
* circle i must be Yellow: i is connect to T (Green circle), so i cann't be T(rue); and i is connected to both X
and Y. if  X <> Y, either X or Y is F(alse), so i cann't be F(alse). So circle i must be Yellow.
* circle j must be F(alse): since i, j, T (Green circle) are connected to each other, they must have different
colors

Given the facts above, it's not difficult to see why the graph above works as an AND gate.

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.
Answer 1:  3 4 6                            a a | b  a | b a  b a
a a   b | a  b a | b a

Answer 2:  3 2 7 4 6                      a a | b  b | a b  b a | b  a | b a  b a
a a   b | b  a b | b a  b | a  b a | b a

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?
Answer:
Note that the starting strings must start with the same letter, that gives: 2, 3, 5, 6
and the ending strings must end with the same letter, that gives: 2, 4, 6
other than that, you'll have to do some boring guessing and checking work.

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.
Answer:

basic idea:
We consider each item in turn. For each item, we have 2 choices: either take it or not take it. For N items, that's 2^N
combinations in total. We use a recursive procedure to try each of the combinations.

algorithm:

Input:     number of items N, weights of the N items in array Weight[1...N], capacity C
we use the array Solution[1...N] to store the combinations of items that totals to C
to start: KNAPSACK( 1, C )

procedure KNAPSACK( ItemID, LeftCapacity)
{
if ( ItemID > N ) {     # have checked all the items
if (LetfCapacity == 0)     # the items selected totals the required capacity
print out the items selected in Solution[1...N]
}
else {     # check the current item
Solution[ ItemID] = 0;                     # choice 1: we do not select this item
KNAPSACK( ItemID+1, LeftCapacity)    # continue with the next time, Leftcapacity remains the same

if (Weight[ ItemID ] <= Leftcapacity)        # the current item weights less than the capacity left
Solution[ ItemID ] = 1;               # choice 2: we take this item
KNAPSACK( ItemID+1, LeftCapacity - Weight[ ItemID]);
#continue with the next item, decrease LeftCapacity by Weight[ ItemID ]
}
}

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.
Answer:
e.g. N = 6 items, Weight[1..6] = { 17, 9, 24, 11, 36, 8 }, capacity C = 19

KNAPSACK( 1, 19 ) -->
Solution[1] = 0, KNAPSACK (2, 19) -->
Solution[2] = 0, KNAPSACK (3, 19) -->
Solution[3] = 0, KNAPSACK (4, 19) -->
Solution[4] = 0, KNAPSACK (5, 19) -->
Solution[5] = 0, KNAPSACK (6, 19) -->
Solution[6] = 0, KNAPSACK (7, 19) -->
7 > N, 19 > 0, no solution, return
Solution[6] = 1, 19 - Weight[6] = 11, KNAPSACK (7, 11) -->
7 > N, 11 > 0, no solution, return
have tried both choices of item 6, return
Weight[5] = 36 > 19, cann't take item 5, return
Solution[4] = 1, 19 - Weight[4] = 8, KNAPSACK (5, 8) -->
Solution[5] = 0, KNAPSACK (6, 8) -->
Solution[6] = 0, KNAPSACK (7, 8) -->
7 > N, 8 > 0, no solution, return
Solution[6] = 1, 8 - Weight[6] = 0, KNAPSACK (7, 0) -->
7 > N, LeftCapacity == 0, print out solution, return
...............................

Comments? Questions? ---------- Contact us at cs111@CS.Princeton.EDU