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.


        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

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

        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.


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