Computer Science 111
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