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