[Here are the answers:]

1. Consider the matrix multiplication of 4-by-4 matrices.
   1. Using the ordinary method of matrix multiplication, how many scalar multiplications are required? Don't just state this number, but calculate the number from the ordinary matrix multiplication algorithm, where each element of the answer is the inner product of a length 4 row times a length 4 column. [Each inner product takes 4 mults, and there are 4*4 = 16 such, so there are 4*4*4 = 64 mults altogether.]

   2. Using the divide-and-conquer approach and Strassen's method of multiplying 2-by-2 matrices, how many scaler multiplications would be required? Again justify your answer. [Regarding the 4-by-4 matrices as 2-by-2 matrices of 2-by-2 matrices, at the top level, Strassen's method would take 7 mults of 2-by-2 matrices, and each of these would take 7 scalar mults, so there would be 7*7 = 49 scalar mults altogether. (A "scalar mult." means a multiplication of actual numbers, rather than matrices.)]

2. Now consider 5-by-5 matrices. Again how many scalar multiplications would be required using ordinary matrix multiplication? (Just a number for the answer.) Suppose one could multiply 5-by-5 matrices using 91 scalar multiplications. Give the recurrence for a divide-and-conquer algorithm based on this supposition. Use the Master Method (or some other approach) so get the asymptotic performance in this case. Would this be an interesting result? [The recurrence in this case would be
   T(n) = 91 * T(n/5) + Θ(n²).

   The Master Method gives performance of

   Θ(n^log₅(91)) = Θ(n^2.8027545).

   Because this is better than Strassen's method at Θ(n^log₂(7)) = Θ(n^2.8073549), it would definitely be of interest. (Notice how close these two are.)]

[It was not necessary to fill out the full tables below, especially if the answer was correct.]

L₁: find the square root of x, where 1/4 <= x <= 1.
L₂: find the square root of x, where 0 < x.

Consider also the two reductions L₁ ≤_p L₂ and L₂ ≤_p L₁.

L₁ ≤_p L₂ means to reduce the problem of solving L₁ to the problem of solving L₂. This means that we start with an instance of L₁ and try to find a corresponding instance of L₂ is such a way that the solution to the L₂ instance gives us the solution to the L₁ instance.

Another way to say this is that assuming we can solve problems in L₂, does that let us solve problems in L₁?

1. One of these reductions is trivial. Which one is "trivial" and why do I use that word.?The direction L₁ ≤_p L₂ is the trivial one, because if we can take the square root of any positive number, we can certainly take the square root of any number in the range 1/4 <= x <= 1. Another way to say this is: given any desired sqrt(x) in the range 1/4 <= x <= 1, we associate it with exactly the same problem in the greater range, x > 0. If we can find sqrt(x) for any x > 0, then certainly we can find sqrt(x) for any 1/4 <= x <= 1.

2. The other is something that we proved. What rough technique did we use to prove it?To prove the other direction: L₂ ≤_p L₁, we start knowing that we can find sqrt(x) in the range 1/4 <= x <= 1. We start with an arbitrary sqrt(x), where x > 0. In this case we normalized the arbitrary case by multiplying or dividing repeately by 4, until our arbitrary problem was in the range 1/4 <= x <= 1. Then take the square root. Finally by dividing or multiplying by 2 to the same power as for normalization, we denormalize and get a solution to original square root.

1. Is any problem in P (polynomial-time problems) also in NP? Yes. Using the "guessing-stage / checking-stage" definition of NP below, we see that a problem in P satisfies this definition without making use of the guessing-stage at all.
2. Is P the same as NP? Can you prove this? Most researchers think now that P is a proper subset of NP, but no one has been able to prove this.
3. Give the "guessing-stage / checking-stage" definition that shows a problem is in NP. NP is the class of problems solvable on a nondeterministic computer. A nondeterministic computer can carry out a nondeterministic algorithm. Such an algorithm can proceed in two stages:
   1. Guessing stage: the algorithm "guesses" a structure S, which either is the answer to the problem or will help compute the answer.
   2. Checking stage: the computer proceeds in a normal deterministic fashion to use S in arriving at a Yes-No answer to the problem. The checking stage must be done in polynomial time. In effect S is the answer and the checking stage verifies in polynomial time that S is the answer.

We want to show that if SS can be solved efficiently, then PART can be solved efficiently. In order to do this, we need to start with an arbitrary problem in PART. Then come up with a way to transform any problem P in PART into a problem P' in SS. Finally show that the answer is "Yes" to P if and only if (exactly when) the answer is "Yes" to P'.

Start with an instance P of PART, that is, start with an array A of positive integers. We assume that we can solve the SS problem. In order to answer "Yes" to P, we need to find a subset A' of A such that sum( a | a in A' ) =  sum( a | a in A - A' ).

So construct an instance P' of SS. The array A in SS will be the same as the one in PART. Let T be the sum of all elements of A: T = sum( a | a in A ). If T is odd, then the answer to P' is immediately "No". Otherwise, use SS to try to find a subset A' such that S = T/2 = sum( a | a in A' ). Then clearly S = T/2 = sum( a | a in A-A' ). There will be such a subset A' given by SS if and only if the same subset A' works to solve P in PART.

Which of the two following facts does this prove:

a. If PART is NP-complete then SS is NP-complete, or
b. If SS is NP-complete then PART is NP-complete.

Part a. was shown above.

In order to prove that a problem P is NP-complete, you need to find a problem P' that you already know is NP-complete, and you need to reduce P' to P, that is, you need to prove that P' ≤_p P. Since P' is known to be NP-complete, by definition,

Q ≤_p P', for all problems Q in NP.

Then

Q ≤_p P' ≤_p P,

so by transivity, we have

Q ≤_p P, for all Q in NP,

which is the definition that P is NP-complete.

 1. move left
 2. if 1 is scanned goto 1
 3. if 0 is scanned goto 4
 4. print 1
 5. move right
 6. if 1 is scanned goto 5
 7. print 1
 8. move right
 9. if 0 is scanned goto 1
10. stop
    (end)

Initial   ...0000000000...
 tape:           |

010
110 1 0
101 0000 1
001
011
110 11111 0
001
011
101 0 1
100
111

Explain carefully what this mystery program does. What is its output and what actions does it go through to produce this output? (This is easier than you might think, although in a sense it's a bit of a trick.)