Programming Assignment Checklist: Theory of Computation Exercises

Sorry, no pairs programming on this assignment.

Frequently Asked Questions: Huntington's Disease

What are the goals of this assignment? To use regular expressions and to program a Turing machine.

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 name of the input file is specified as a command line argument, so you must read directly from the file (instead of using standard input).

I get an OutOfMemoryException. 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

What technique should I use for the HD diagnoser? Use regular expressions, i.e., Pattern and Matcher.

Where can I see all available String library methods? Here is the String API. Though, you should only need the ones introduced in lecture.

Where can I see the Pattern class and its library methods? Here is the Pattern API. Though, you should only need the ones introduced in lecture.

Where can I see the pattern Matcher class and its library methods? Here is the Matcher API. Though, you should only need the ones introduced in lecture.

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. For reference, here is more documentation on 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.

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.

Remember to answer the questions in the readme.txt file about how you tested your programs.

Submission

Submission. Submit Huntingtons.java and comparator.tur. 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 the 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.

   • Make test data for your 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