Markov Chain Programming Assignment Overview

Assignment Constraints

You may talk with others about the ideas in this assignment, but you must write all code independently (or with your partner, if allowed to pair-program). If you need specific help with your code, please get help from the instructor or one of the student assistants. You may get help from other students during the debugging phase.

Objectives

You should

Your Task

Your task is to implement two different algorithms, which will be performed in sequence.

The first is the Markov Chain algorithm. (Follow the link for an in-depth description.) It takes as input some sequence of "words" and generates as output a constrained random sequence composed from some or all of the original "words". The new sequence has similar statistical properties to the original sequence.

The second algorithm is a Text Justification algorithm. (Follow the link for an in-depth description.) This algorithm should take as input some intermediate data representation from the Markov Chain algorithm and print that data to the console so that it is both left and right justified.

General Program Specification

You are to write a Java application in a class named Markov. The constructor to Markov should take 4 parameters (in the following order):

For example, the command

Markov markov = new Markov("Oz.txt", 3, 400, 75);

generates random text based on the contents of the file Oz.txt with Markov Chains of length 3. It generates text until the Markov Chain algorithm naturally terminates or until 400 words are generated, whichever comes first. It justifies the output so that each output line occupies exactly 75 characters (except the last line).

Note that the above command-line example implies that the Markov class is in the default package, and that the Oz.txt file is in the same directory as Markov.class.

A "word" shall be defined as any sequence of non-whitespace characters, so you will not need to treat punctuation or capitalization in any special way. Thus the following will be considered four different words:

Data Structures Specification

You are required to use the data structures specified in this document for pedagogical reasons. Later in this course and in life you will have a chance to choose the data structures you think best fit the problem or implement your own, but at this point it is important to make sure you can figure out how to use those specified here.

Note that this section will not make much sense if you have not yet read the in-depth descriptions of the Markov Chain and Text Justification algorithms.

Efficiency and Memory Use

If the number of output words is small compared to the text from which the output is constructed, we would expect that most of the program's time would be spent building the data structures, and not much time producing the output.

It is possible that the default amount of memory allocated by the Java interpreter will not be enough. To increase to 50 (or substitute your own number) megabytes, use the -Xmx option when you invoke the interpreter: "java -Xmx50m Markov last-of-the-mohicans.txt 3 300 60". This -Xmx50m option will be used when we test your program.

Sample Data Files

Before you begin testing your program, you should create your own small data file, designed to produce a relatively small data structure that still provides choices for the random sequence generator. The words in the file do not have to make sense. Once you are confident that your program is working, you will want to try it on larger files that provide interesting random text.

Some large texts on which you may test your program are collected in the texts folder, part of this assignment on ANGEL. Due to memory requirements, you may not be able to process the longer ones with prefix-lengths greater than two, but a prefix length of two gives fairly interesting results.

If you have a text that produces particularly interesting random sentences, please send it to me, and I will add it to the directory.

Milestones

This assignment may be graded in two parts. The first part must generate appropriate Markov chained output, but need not be justified. Grading for the first part will treat any amount of white space in the output as a delimiter. The program should take the four arguments specified above, but may ignore the last argument, justification width.

The second part is the completed program, Markov and justification. Turnin is identical to milestone 1.

Running Your Program for Grading Purposes

I will delete all .class files and use javac *.java to compile your code. Then I will execute it using command-line arguments as in the example. All output must be written to System.out. No header lines, debugging information, or other extra characters should be added to the output. A program will check to make sure that your output really is a justified Markov Chain, and extra output will confuse it.

Questions and Answers

These questions and answers will probably not make much sense if you have not yet read the Markov Chain and Text Justification algorithm descriptions. I have given a variation on this assignment before, and these questions come from my archive of email and newsgroup questions from that term.

QuestionsAnswers
How can we choose a random suffix from a MultiSet? Generate a random number, k, between 0 and size(), then use the findKth method from the MultiSet class.
Can we assume that the length of the line being outputted is longer than the length of the prefix? I presume you mean "the first prefix". Since that prefix contains only one word, the answer is yes. You may assume that no input word is longer than the line length.
It is OK to not align the last line of output or is this mandatory? It would look pretty ugly if you did! The last line should be left-justified, of course, but not right-justified.
Can we assume that the command line arguments will be of the correct type and in the right order (the order given in the example)? Yes. You do not need to do any input error checking. Getting correct output for correct input is quite enough for you to do in ten days.
Also, will the text file name given at the command prompt include the ".txt"? Yes. Whatever the full filename is, it should be included on the command line. If it's in a different directory than Markov.class, a pathname must be given, of course.
Do you really mean that there should be two spaces after every period, question mark, etc? No. Only if the period or whatever ends a word (defined for this assignment as a sequence of non-whitespace characters).
How do I know whether a character is a whitespace character? One approach is to use the Character.isWhiteSpace method. It would be very nice to set up a StringTokenizer object that considers all whitespace characters as delimiters. This would be difficult if you wanted all Unicode whitespace characters; perhaps it is easier if you restrict your attention to ASCII whitespace characters, which you are allowed to do. Also see examples.html for an explanation of a String's split method.
Are we ever supposed to call the hashCode() method that we must write? No. The HashMap methods will call it when needed.
What if I can't get the Markov algorithm working at all? Can I still do the justification part and get some credit? Definitely. I suggest working on the two parts "in parallel". If you are working on the justification part, you can write a very simple main() program to test it. All that this program must do is (like Markov) feed the output routine a word at a time, so that the output routine can justify and print out the words whenever a line gets filled. So your final program should simply justify the first part of the original text, to demonstrate the justification part.
What's the worst behavior my program can exhibit (this question came from me, not from a student)? An infinite loop. You should make sure that your program always terminates and gives some kind of output to show what it is doing, even if that output is not correct.
What is the point of Markov, besides the DataStructures practice? Most of our programs up to this point could have some use in the real world. I am just not sure what, if anything, Markov can be used for. A very good question. Let me give you an analogy. At one point, I started taking piano lessons. Something I had always planned to do "when life slows down a bit." (I finally decided that it never will, and that if I don't do it now, I'll never get around to it). Then life got REALLY busy and I gave it up, but I WILL get back to it someday! No, really :)
What did my teacher have me spend most of my time doing? Scales and warm-up exercises. I could ask "Will I ever use this in the real world?" What concert pianist or even bar room pianist would ever play a scale or a warm-up exercise for an audience?
My reaction could be to say that I shouldn't have to spend time practicing scales, etc. because they are not "practical." But fortunately I did not do that, and I can already see how practicing those boring pieces with no real-world application has made me more agile at playing in general, so that I can play the (quite simple, so far) "real" pieces better than if I had never practiced the scales.
This course is a prerequisite for many other CSSE courses. Mostly, it its the CSSE equivalent of scales and warm-ups. Hopefully by the time you are done this course, you will be able to run up and own the scales at a rapid speed, so that later when you do applications (in Operating Systems and other courses, and presumably after graduation), you will be able to concentrate on the problems you are solving, because grinding out the code will now be easy. By the end of this course I want you to be able to use data structures almost as effortlessly as a concert pianist plays an D major scale . If that process allows you to do some interesting programs with immediate applications along the way, that's a bonus. But it's not the only point of the programming part of this course.