P1

Look at the description of the memoized 0/1 Knapsack solution from the class notes. Below is shown and input problem and the table created by the memoized algorithm in finding an optimal solution for that problem. Use the table to work backwards and figure out an optimum solution to this problem - i.e. which items actually go in the knapsack. [Note: I'd just print this table out and tape/staple it in so you can write on it.]

10 :   2:3  3:7  4:8  4:9  3:2

n	cap
		0	1	2	3	4	5	6	7	8	9	10
	0	0	0	0	0	0	0	0	0	0	-1	0
	1	0	-1	3	3	3	-1	3	3	-1	-1	3
	2	-1	-1	3	7	-1	-1	10	10	-1	-1	10
	3	-1	-1	-1	7	-1	-1	11	15	-1	-1	18
	4	-1	-1	-1	-1	-1	-1	-1	16	-1	-1	20
	5	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	20

P2

We decided that to compare the difficulty of different problems we need to use as input size the standard of "bit length". This means you need to think about how to write a problem instance down as a string of symbols and, ultimately, to determine how many bits are required to represent that string. Thus, you need to develop the skill of representing objects as strings and determining bounds on the lengths of those strings.

Example: Suppose that I have an array of n non-negative integers, all less than d. How many bits would be required to represent this array? Well, you'd have to write down n and $\lg d$ and then you'd have to write down all n of the array elements. It takes roughly lg(x) bits to write down the number x, so this would require $\lg(n) + \lg \lg(d) + n\lg(d) = \Theta(n \lg(d))$ bits. If you want to be picky, you'll have to be a bit clever to make sure that the person can interpret all the bits correctly. For example:

What input does this represent: 11111011011101011000010100 ?

could be:                       111    11  011 011 101 011 000 010 100
                                n=7 lg(d)=3 3   3   5   3   0   2   4


could be:                       11   111    0110111 0101100 0010100
                                n=3 lg(d)=7   55      44      20

Fortunately, we don't need to worry too much about this. With even a really silly plan, we could encode this without doing worse than, say, quadrupling the number of bits used. Thus, we could still encode our problem in Θ(n lg(d)) bits.

Just this once, I want you to worry about precisely what I said you didn't need to worry about in the above example. I want you to describe a scheme with which you could encode an array of n non-negative integers, all of which are less than d, as a string of bits. From your description I should be able to easily figure out how to encode any such array, without any limits whatsoever on n and d ... even if n and d were *HUGE*. This scheme must be unambiguous, in other words there can't be two different possible interpretations, like what I did above. Your solution must include:

1. a description of your encoding scheme,
2. an example n, d and array encoded according to your scheme, and
3. an analysis of how many bits your method requires as a function of n and d.

Other study problems (not to turn in)

1. Consider the problem of deciding whether or not there is a cycle in an unweighted, directed graph G with n vertices and e edges. The input for such a problem is simply G. Describe a scheme for encoding G as a sequence of bits and give the bit-length of a problem encoding as a function of n and e.
2. Suppose you want to encode a list of non-negative integers, and their sizes can vary wildly. It's tough to encode so that you know where one integer stops and the next starts. One scheme is to encode a number n by first giving the number of bits in n in unary notation, then giving the number itself in binary: for example to encode 5:

         .--------- terminates the unary field width
         |
         V
   1 1 1 0 1 0 1  ←  represents the number 5
   -----   -----
   Tells   3-bit
   me n    representation
   takes   of the number 5.
   3 bits
   

   What is the list of numbers reprsented by:

   1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 0 1 0
   

3. Using the above scheme, write an expression for the number of bits required to represent the list of numbers n1, n2, n3, ..., nk?
4. Which of the following expressions is a polynomial: n^2 - 3*n + 1, n^n + 1, n*k + k^2, n*lg(k), sqrt(n) + 2*n.
5. Give the following information on the worst case running times of algorithms A, B, C, and D, which algorithms are "polynomial time"?

   T_A(n) = n^2 - 3*n + 1,
   T_B(n,k) = n^n + 1, n*k + k^2,
   T_C(n,k) = n*lg(k),
   T_D(n) = sqrt(n) + 2*n.

6. If algorithm A runs in time O(n^3/2), and s, the number of bits required to write down a "size n" problem, is n⁴, what is the running time of A in terms of s rather than n?

P3

The "Partition Problem" is this: Given a set S of numbers, partition S into sets A and B such that sums of their elements are as close as possible. [Note: "partition into A and B" means that each element of S has to be assigned to either A or B, but not both.]

 Example: S = { 9, 18, 7, 6, 3 }
Solution: A = { 3, 18 }, B = { 6,7,9 }
      

1. This is not a decision problem. Describe a decision problem variant of the Partition Problem. Note: This means you must clearly specify what is input to the problem, and what the output is supposed to be. (Alternately, you may prefer to think of it what is given, and what is required.)
2. Prove that your decision problem variant of the Partition Problem is in NP. Follow the "Proof Outline" example from below.

P4

A Combinational Circuit is a directed acyclic graph (DAG) with sink vertices labeled with distinct variables $x_1,\ldots,x_k$ and a single sink vertex labeled $z$. The remaining vertices are labeled NOT if there is a single incoming edge, and AND, OR, or XOR otherwise.

Example of a combinational circuit

The CIRCUIT-SAT problem is simply this: given a circuit, is there an assignment of values to the circuit's variables for which the circuit outputs true?

Your problem: prove that CIRCUIT-SAT is in NP.