Markov Chain Programming Assignment—Index

Note: None of the documents can be fully understood until you have read the others. They are all inter-related. That means that you should probably read all of them twice before beginning your design and code.

I suggest that you quickly read this document, then the other documents in the order listed. Then re-read all of them more carefully.

This is a pair programming assignment. You must do your programming as a pair. You may talk with other people about it, of course, and get help as needed.

Your code must not contain any GUI components (such as Frame, JFrame, or JApplet).

Milestones

Milestone 1: After reading the input, your program should produce a correct Markov chain of words (as described in the Markov document). All of the provided JUnit tests for milestone 1 should pass.

Milestone 2: Process the words created by the Markov chain algorithm so that the output contains justified lines of the length specified (as described in the Justification document). All of the provided JUnit test cases for both milestones should pass.

Efficiency

Minor details of efficiency are not a concern here, but the running time should certainly be an asymptotic linear function of the number of input words. If your program takes 20 minutes to run for one of the large files in the texts folder, chances are good that you have an N2 algorithm. The first thing you might look at is how you do the input.

Documents and folders

There are five main documents associated with this assignment:

There is also a folders, multiset. We are providing a MultiSet class for you. The multiset folder contains:

The bytecode, but not source code, for MultiSet is included in the Eclipse template you will use.

Suggested process for getting started on this assignment

Why can't I just do it my way?

Why do you have to use the data structures that I specify, instead of simply writing the program "from scratch"?

During your career some projects will leave more of the design decisions to you, but others will not. It is important to get practice in implementing other people's specifications and designs, and using classes that are provided for you.