Markov Chain Programming Assignment Index

CSSE220

Markov documents: index overview markov justification turnin-instructions code examples partners importing classes MultiSet Documentation

You can get a zip file of this whole folder, including the starting code, here.
To view the folder's entire contents on-line, click here.

Note: None of the documents for this assignment can be completely 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 coding. I suggest that you quickly read this document, then the other documents in the order listed below. Then re-read all of them more carefully.

This is a pair-programming assignment. You may talk with other people about it, of course, and get help as needed, but you and your partner must do the assignment yourself and submit it (to your turnin folder on AFS). Even though you won't use SVN to submit the program, I will provide an SVN repository that you and your partner can use if you wish

Unlike some of the recent programming assignments, 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.html document). Line spacing does not matter, and one word per line will be fine for your output.

Milestone 2: Process the words created by the Markov chain algorithm so that the output contains justified lines of the length specified by the command line.

We will grade the program according to this checklist.

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 N² algorithm. The first thing you might look at is how you do the input. (Note: recall the analysis of the stringCopy method from class..)

Documents and folders

There are five main additional documents associated with this assignment:

overview.html describes the goals of the assignment, the four required command-line arguments, the data structures to be used, and the submission instructions.

markov.html describes the Markov Chain algorithm that you are to use to generate semi-random text.

justification.html describes the algorithm for producing text that is left and right justified.

examples.html gives examples of using some of the data structures and methods that are used in this assignment.

turnin-instructions.html tells you how to submit your program

importingEclipseClasses.html tells how to get Eclipse to recognize the two .class files that we are providing for you (should only need if you change a setting by accident).

There are also two folders:

multiset. We are providing a MultiSet class for you. The multiset folder contains several useful flies:

Multiset.html provides javadoc for the Multiset class.
MultiSet.class is the actual class file that you should use in your project. You should copy it to the place where your Eclipse project puts its .class files.
MultiSet$entry.class is the class file for a nested class that MultiSet uses. You should copy it to the place where your Eclipse project puts its .class files.
TestMultiSet.java should help you to understand how the MultiSet class works.

The texts folder contains a collection of text files that you can use as input to your program. You may want to copy it into your project folder.

Getting Started

Your have been provided starting code in your repository. You can find your partner's name and repository name here.

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"?

Some of the later assignments in the Fundamentals classes 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.

Planning and scheduling your work

Completing this assignment on time will require starting early. assignment has a tighter schedule than most. It is important that you start early. For each of the two Milestones, it will take you a little while to understand what it is all about and what you should do. Then you will probably need some planning time before you begin coding. For Milestone I, you should do the understanding and planning parts on the day it is assigned, so you can begin coding in earnest the next day.

Milestone 1 is due on Day 22 (Tuesday April 29, at 8:05 AM), but you should aim to complete it by Friday, so that if you run into trouble you will have extra time to make up for it. Regardless, you should begin work on Milestone 2 before Day 22, if you are to complete it before it is due. Most of the work for Milestone 2 can be done independently of Milestone 1. Milestone 2 is due Friday, May 2, at 5:00 pm. There will not be another weekend before Milestone 2 is due.