CS 456/656 Assignment 6

Due date: April 21, 2005

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
  1. Work Exercise 7.9 on page 272 of your textbook.
  2. Work Problem 7.11 on page 272 of your textbook.
  3. Let L be the language over unary alphabet {1} consisting of all strings whose length is a perfect square. For example, the empty string, 1, 1111, 111111111, and 1111111111111111 are in L. Construct a general grammar that generates L. Answer.
  4. In class, I told you that the knapsack problem is NP-complete. But that is if the numbers are integers written in decimal notation. Starting with the knowledge that the decimal numeral knapsack problem is NP-complete, prove:
    1. The binary numeral knapsack problem, i.e., the knapsack problem where the numbers are integers written in binary notation, is NP-complete. (This is not very hard. You do it by reduction, starting from the known fact the the decimal version is NP-complete.)
    2. The unary numeral knapsack problem, i.e., the knapsack problem where the numbers are integers written in unary (caveman) notation, is polynomial. (This is hard. See hint.)

      3. At this point you are probably asking yourself, "What difference does it make how the numbers are written, isn't it the same problem?" The answer is yes, it's the same problem, but the length of the input is far larger if the numbers are written in unary rather than decimal or binary, and the class P is defined in terms of the length (number of symbols) of the input, not the number of numbers in the input.

Back to Course Page