Assignment 13 Lite: Turing Machines Revisited and Algorithms!
Due Thursday, December 11 at the beginning of class

In this written homework assignment (the last one in the course!) you will examine one more problem which, alas, cannot be solved by any computer. Then, you will be analyzing the running time of several algorithms. Please note that the notation n^k means "n raised to the power k".

1. Professor Lai! [20 Points]
   Professor I. Lai claims to have written a program called a "Regularity Checker" which does the following: The Regularity Checker takes as input a program P (where P is a decider program, which just answers "yes" or "no" to its input). Ifthe set of strings accepted by P happens to be a regular language, then the Regularity Checker says "yes". If the set of strings accepted by P is not a regular then the Regularity Checker says "no".

   Why is a Regularity Checker a good thing to have? Well, if it turns out that our program P accepts a regular language, then we know that it can be run on a computer with a finite amount of memory (a DFA)!

   Unfortunately, a Regularity Checker does not exist. Your job is to prove it. You may use diagrams to help explain your proof, but your proof must be clear and precise.

2. Fast Multiplication! [25 Points]
   In this problem we consider the problem of multiplying two n-bit numbers, x and y. (For simplicity, assume that n is a power of 2. This is generally the case anyhow in typical computer architectures, but we could easily relax this assumption similar to the way we fixed mergesort.)
   1. Explain briefly why the running time of the standard algorithm (performing normal multiplication, only in base 2 rather than base 10) for this problem has running time which is asymptotically n^2.
   2. Some fast multiplication circuits use the following clever divide-and-conquer algorithm. Divide x and y in half. Thus, x = a 2^{n/2} + b and y = c 2^{n/2} + d where a, b, c, d are n/2-bit numbers. The product of x and y, call it z, can now be computed by the following steps:

              temp1 = (a+b)(c+d)
              temp2 = ac
              temp3 = bd
              z = temp2 2^{n} + (temp1 - temp2 - temp3) 2^{n/2} + temp3
      	

      Nothing for you to do here! This is just the description of the algorithm.
   3. Explain why z is in fact the product of x and y. This is easy to explain - we did most of the argument in class. Nonetheless, explain it clearly in your own words.
   4. Observe that the terms (a+b) and (c+d) may have either n/2 or n/2 + 1 bits each. For simplicity, assume for now that they each have exactly n/2 bits (the case of n/2 + 1 bits isn't hard to deal with, but let's not worry about it here). Notice that the above algorithm performs 3 multiplications of n/2 bit numbers plus some additions and shifts. (Multiplying a binary number by a number of the form 2^k can be accomplished by simply performing k bit shifts to the left! This takes just k units of time.) Now, just write down the recurrence relation (an expression for T(n), including a base case) for this algorithm.
   5. Find the asymptotic running time of the divide-and-conquer algorithm by setting up the work tree for the recurrence relation and then obtaining a solution. Show your work in detail. Your final answer shoud be O(n^k) where k is some real number.
   6. How does this algorithm's running time compare to the running time of the standard O(n^2) algorithm?

3. Curly, Mo, and Larry's Totally Excellent (?) Sorting Algorithm! [25 Points]
   Professors Curly, Mo, and Larry of the Pasadena Institute of Technology have proposed the following sorting algorithm called Stoogesort: First use recursion to sort the first two-thirds of the elements in the array. Next use recursion to sort the last two thirds of the array. Finally, use recursion to sort the first two thirds again. As we saw in class, this algorithm correctly sorts its input.
   1. Write down the recurrence relation for the running time of Stoogesort. Now, solve the recurrence relation using a work tree. Carefully show all the steps in your analysis. You will find it useful to assume that n (the length of the array to be sorted) is equal to (3/2)^k. Wait a second! (3/2)^k isn't even an integer. As we'll see in class, this is simply not a problem. As long as we determine the running time for consecutive powers of some number greater than 1 (such as 2 or 3/2), then we can sleep well at night knowing that the asymptotic running time that we obtained is, in fact, correct for all values.
   2. Express the running time of Stoogesort as O(n^x) where x is some real number. Give the actual value of x.
   3. How does the running time of this algorithm compare to that of Mergesort? Is it better or worse? Explain your answer carefully.