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