Computer Science 111
Due Wed April 20, 5pm
Problem Set 9



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

   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?

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

    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.

  
3. Let us go back to the "Hello" assignment in the lecture. As you
probably remember, we claimed that it is impossible to write a program
that grades this assignment automatically. That is, no program can
decide if its input is a program that output "Hello world!" and nothing
else. After proving that the halting problem is undecidable, we are
ready to substantiate that claim.     Suppose that someone gives you a
"black box" program called HelloGrader, and claims that the HelloGrader
program automatically grades the "Hello" assignment. Using HelloGrader
as a building block, describe informally how you can build a program
that solves the Halting Problem.  Can a program like HelloGrader exist?
Using your answer to (1), argue that its existence would lead to a
contradiction.
       

4. a) Come up with an algorithm that solves the partition problem. The
input of your algorithm should be a list of integers, representing
weights. The output should be "yes" if the list can be partitioned into
two sets of equal weight, and "no" otherwise.  Describe your algorithm
informally, but in detail. Hint: Don't try any smart tricks! Just try
the first, most brute-force algorithm that comes to mind. 

b) Now suppose that your computer needs 1ns to add two integers, and assume
that all other instructions in your program take negligible time. How
much time would your algorithm need to give an answer for a list of 10
weights? What about 100, 1,000, or 1,000,000 weights? Hint: The time
your algorithm takes does not depend only on the input size; it also
depends on the specific input values. You can answer the above question
either by estimating the average time for each input, or by calculating
how long the algorithm takes in the "worst case". Notice how fast the
time grows with the input size! A friend of yours argues that your
algorithm is inefficient, and that a much more efficient algorithm
should exist. What would your answer be?