Programming Assignment Checklist: Theory of Computation Exercises


Sorry, no pairs programming on this assignment.


Frequently Asked Questions: Huntington's Disease

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

How should I read in the data to diagnose Huntington's disease? Use the readAll() method in the In data type. The names of the input files are specified as a command-line argument, so you must read directly from the file (instead of using standard input).

I get an OutOfMemoryException on large input files. How do I tell Java to use more of my computer's memory? Depending on your operating system, you may have to ask the Java Virtual Machine for more main memory beyond the 64MB default.

java -Xmx120m Huntingtons chromosome4-hd.txt
The 120m means 120MB, and you should adjust this number depending on the size of the input text.

I get a StackOverflowError on large input files. How can I fix this? Use the character set notation [ACTGN] to match a single character instead of (A|C|T|G|N). Java deals with this construct much more efficiently.

Where can I see the String API? Here is the String API.

Where can I see the Pattern API? Here is the Pattern API.

Where can I see the Matcher API? Here is the Matcher API.

How do I match any whitespace character with Java regular expressions? One way is to use the predefined character class \s matches any whitespace character. To embed \s in a string, use \\s because \ has a special meaning within a string. The Pattern API provides documentation on the syntax for creating regular expressions in Java.

What's the difference between the String methods replace(from, to) and replaceAll(from, to)? Both return a new string with all occurrences of from replaced with the string to. The former treats from as a string; the latter treats from as a regular expression. This is a lesson in how not to design an API.

Why doesn't s.replaceAll("a", "x") change the string s? Reread Section 3.1. Pay special attention to the distinction between mutable and immutable data types.

Frequently Asked Questions: Turing machine

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.

Can I assume that the binary input numbers will both have the same number of bits? No. Do not assume that the input numbers are of the same length.

Should my Turing machine work if one (or both) of the inputs have leadings 0s? Yes.

My Turing machine behaves correctly using the Turing machine simulator. However, when I click the "Check All Submitted Files" button, it exceeds the limit on the number of steps. What am I doing wrong? The assignment specifies that the tape head must start on the leftmost nonblank character. You may encounter this problem if your Turing machine relies on the tape head starting somewhere else.

Do I need to worry about negative integers represented using two's complement notation? No, treat all binary integers as either zero or strictly positive.

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? You can download turing.jar and launch it by typing java -jar turing.jar from the command line. Alternatively, depending on your system, you may be able to download the Turing machine simulator and launch by clicking the .jnlp file that appears on your desktop. (If you try to use the .jnlp file, please indicate in your readme what computer and operating system you are using and whether or not it worked.)

I get the error that my Turing machine is nondeterministic. What does that mean? You have two (or more) edges leaving a state with the same symbol. As a result, there's more than one action a Turing machine can take in a given situation. A (deterministic) Turing machine must have exactly one action in a given situation.

Input, Output, and Testing

Huntingtons 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.

Turing Machine Input.   The tapes section of your comparator.tur file should show the test data you used to check out your comparator Turing machine.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

  1. Download the theory directory from the ftp site. It contains Grep.java, Harvester.java, and In.java as well as several sample inputs for the Huntington's disease diagnoser. There is also the example Turing Machine file, binaryadder.tur.

  2. Huntington's diagnoser.

  3. Turing machine.

Enrichment

Listen to the Huntington Disease Protein where each amino acid is assigned a note on the musical scale [mp3]. Reference.

Huntington's protein