COS 226 Programming Assignment Checklist: The Markovian Candidate

Goals

Here are the main goals of the assignment.

Frequently Asked Questions

Is it important that my program implements the MarkovModel interface? Yes, we will test this piece independently. It need not print out the k-grams in the given order, e.g., it's fine if you organize the strings of length k and k+1 in the same data structures.

What characters may appear in the input? The input consists of UNICODE text (although we don't plan on feeding you anything outside the ASCII subset of UNICODE). Do not assume it is just white space and lowercase letters.

Do I need to remove punctuation, change characters to lower case, or otherwise modify the text? No. For building and using the Markov models, use the UNICODE text exactly as given. The only processing you should do is to change all white space characters to ordinary spaces whenever you print anything out (but not when building or using the Markov models).

My program does not always predict the correct speaker on this task (for instance, it sometimes predicts that Bush was the speaker on a Kerry quote). Is this okay? Yes, even a correct implementation might not get perfect accuracy using this technique (or any technique).

How do I set the alphabet size S for Laplace smoothing? Use the actual number of distinct characters in the given training file. In reality, it would be better to use the number of distinct characters in the union of the two training files and all of the test files.

How do I handle the beginning of a text block where there are fewer than k characters in the context? Treat the string as if it were a circular string. So if k = 3 and the string is "abcdefg", the context c would be gab.

Can I use ST.java, SET.java, MaxPQ.java, and MinPQ.java from the booksite? Absolutely.

Given a string s, how do I access its i-th character? Use s.charAt(i).

Given a string s, is there an efficient way to get a substring? Use s.substring(i, i+k) to get the k-character substring starting at i, or s.substring(i) for the substring beginning at i and continuing to the end of the string.

Given a string s, how do I easily convert all of its white space characters to ordinary spaces? Use the String library function s.replaceAll("\\s", " ");. The \s matches any sequence of white space characters; the extra \ is needed to "escape" the usual meaning of \ inside strings. You should only do this when printing out, not when creating the Markov model or computing likelihoods.

Am I required to format floating point numbers exactly as in the reference solution? No, this is not a requirement, but if you wish, you can use System.out.printf.

My toString method takes quadratic time. What can I do to make it run in linear time? Strings are immutable. One consequence is that repeated string concatenation is inefficient. Use a java.lang.StringBuilder or java.lang.StringBuffer.

Why do I get slightly different answers when I execute on Windows? It could be the way your operating system separates lines of text. Unix uses "\n"; Windows uses "\r\n". If your alphabet size is one bigger than expected and all your lines have one extra character, this is the reason.

Where can I get documentation on the standard Java classes, including the ones mentioned above? See the documentation for the Java standard platform.

 

Input, Output, and Testing

Input.  Here is a directory containing all of the data from the debates. We are providing data files from the three debates, one file per speaker per debate with text blocks corresponding to the actual responses. These are in the files bush1.txt, kerry1.txt, bush2.txt, etc. The first two debates have also been combined into the files bush1+2.txt and kerry1+2.txt. You should train using the first two debates and test on the third.

To run your program on a large number of inputs, take advantage of the wildcard capabilities of your operating system (Windows, Linux, and OS X).

%java BestModel 2 bush1+2.txt kerry1+2.txt bush3-*

For amusement, you might also see how your Bush/Kerry models do at classifying quotes from John Edwards and Dick Cheney taken from the vice presidential debate. These are in cheney.txt and edwards.txt.  We will test your program using similar, but not necessarily the same data.

Output. To allow automatic testing, your program must use the output format described on the assignment.

You are encouraged to test your program carefully on small files where you can compute the correct outputs by hand.

Submission and program report

The readme.txt file should include:

Possible progress steps

Here are some suggestions of how you might make progress on this assignment.