Programming Assignment Checklist: Theory of Computation Exercises

Goals

Here are the main goals of the assignment.

• Use regular expressions or DFAs.
• Program a Turing machine.
• Learn about reductions.
• Learn about binary search.

Is this really how doctor's diagnose Huntington's disease. Yes.

What technique should I use for the HD diagnoser? We recommend using regular expressions, although there are other perfectly viable approaches, e.g., using DFAs.

How do I match any whitespace character with Java regular expressions? The predefined character class \s matches any whitespace character. To embed \s in a string, use \\s because \ is a special character.

Should I use StdIn or In to diagnose Huntington's disease? Use In because it has a readAll method. You can try using StdIn.readString - this helps when dealing with whitespace, but unless you're very careful, it will make the running time go quadratic!

Do I need to use a halt state? No, your program should end in a yes state (labeled Y) or a no state (labeled N). The Turing machine for binary addition uses a halt state (labeled H) since it's purpose is to leave a result on the tape instead of answering a yes/no question.

Does my Turing machine have to clean up after itself and leave an empty tape? No. The only thing that is required is that it end up in the right yes or no state.

Once I've created my Turing machine input file, how do I test it? Use the Turing machine simulator from lecture. To read in your data file, use File -> Load Machine.

How do I launch the Turing machine simulator? Double-click the icon for turing.jar. Or, to aunch it from the command line, type java -jar turing.jar.

Can I change hasFactor? No, you must treat it as a black-box. Otherwise, you will not be reducing from factorize to hasFactor.

If I'm using 64-bit long integers, doesn't this imply that the problem size can't grow beyond N = 64? Yes. When we say that your algorithm should run in polynomial time, we mean this with respect to N-bit integers. The Java library BigInteger supports arbitrary precision integers, and in prinicple you could rewrite your code using these instead of long integers. We don't ask that you do this, but we do expect that your algorithm takes time polynomial in the number of bits N in the binary representation of x.

Input, Output, and Testing

Input.   Here are a number of additional sample input files. You may find it useful to create additional test inputs to check that your programs work in all cases.

Submission

Submission. Submit Huntingtons.java, comparator.tur, and Reduction.java. We will supply In.java.

readme.txt. Use the following readme file template.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps. First download the theory directory from the ftp site.

1. Huntington's diagnoser.

   • Use Grep.java to find and print all lines in the input that contain CAG. No coding necessary.

   • Use Harvester.java to find and print out all CAG repeats. For now, don't worry about whitespace. No coding necessary.

   • Write a customized program (perhaps based on Harvester.java) that finds the longest CAG repeat, prints its number of its constituent CAG triplets, and prints an appropriate diagnostic message. Don't forget to disregard whitespace.

2. Turing machine.

   • Make sure you understand how the Turing machine described in binaryadder.tur works. Also make sure you understand the data file format.

   • Think about how you would compare two binary numbers. Don't worry about making your computation efficient - the brute force approach taken in binaryadder.tur is perfectly acceptable.

3. Reduction.

   • Implement factorize(x) by repeatedly calling hasFactor(x, 2), hasFactor(x, 3), hasFactor(x, 4), etc., until you can deduce the smallest prime factor p of x. Print it out to standard output. Now, find the smallest prime factor of x / p. Repeat until you have you printed out the full prime factorization.

   • Once you can print out the factors, figure out how to store them in an array since the final function must return the factors in an array. This will require making an array that is at least as big as the number of factors. (How big must you make it?) Fill up this temporary array with the factors as you compute them (instead of printing them out to the screen). At the very end, create a second array of exactly the right size, copy the factors from the temporary array, and return the resulting array.

   • The previous suggestions leads to a correct algorithm, but it can take exponential time, e.g., if x is the product of two large primes. Instead of brute force, use binary search to isolate the smallest factor.