CS2011 hw1

COMP 2011/2711 Data Organisation, Semester 1, 2006

Assignment 1

Due: Thursday 30 March, 6:00 pm
Marks: 10% of final assessment

This assignment will involve writing a program which can recognize and Predict sequences of numbers belonging to one or more of the following types:

Type Formula
Constant u_k = a

Arithmetic u_k = u_k-1+b

Geometric u_k = ru_k-1

Quadratic u_k = ak² + bk + c

Homogeneous u_k = au_k-1 + bu_k-2

Recurrent u_k = au_k-1 + bu_k-2 + c

Type	Formula
Constant	`u_k = a`
Arithmetic	`u_k = u_k-1+b`
Geometric	`u_k = ru_k-1`
Quadratic	`u_k = ak² + bk + c`
Homogeneous	`u_k = au_k-1 + bu_k-2`
Recurrent	`u_k = au_k-1 + bu_k-2 + c`

Our aim is to write a program which will read a sequence of numbers from standard input, determine which type(s) of sequence these numbers could belong to, and in each case predict the next five numbers in the sequence.

Examples

Let us suppose the input to our program is

[1 2 4]

A sequence beginning with the numbers "1", "2" and "4" cannot be a Constant or Arithmetic sequence, but it could be a Geometric sequence with r = 2, in which case the next five numbers would be 8, 16, 32, 64 and 128; it could alternatively be a Quadratic sequence k²/2+k/2+1, in which case the next five numbers would be 7, 11, 16, 22 and 29. There is insufficient information to make a sensible prediction in the case of a Homogeneous or Recurrent sequence (since three items are not enough to determine the constants a, b and c). Therefore, the output of the program will be as follows:

Geometric [8 16 32 64 128]
Quadratic [7 11 16 22 29]

To take another example, let's suppose the input is

[1 1 3 7]

This cannot be a Constant, Arithmetic or Geometric sequence, but it could be a Quadratic sequence k²-k+1, or it could be a Homogeneous sequence u_k=2u_k-1+u_k-2. So the output is:

Quadratic [13 21 31 43 57]
Homogeneous [17 41 99 239 577]

Finally, consider the input

[1 -1 2 -2 3]

This input could only be produced by a Recurrent sequence u_k=-2u_k-1-u_k-2+1, so the output is:

Recurrent [-3 4 -4 5 -5]

Other examples of input and output will be provided in the samples directory as the project progresses.

Implementation

The complete program will consist of eight classes. Three of them are provided for you:

hw1.class
Predictor.java
ConstantPredictor.java

Your task is to write, and submit, the remaining five classes:

ArithmeticPredictor.java
GeometricPredictor.java
QuadraticPredictor.java
HomogeneousPredictor.java
RecurrentPredictor.java

Each of these must extend the Predictor class, and implement the following methods:

public String toString();
public void step( double u );
public boolean canPredict();
public double predict();

The toString() method should return the name of the sequence type, as given in the table above.

the step() method will be called for each item in sequence.

The canPredict() method should return true if the next item in the sequence can be predicted; it should return false if the items provided are inconsistent with the type of sequence under consideration, or if there are not enough of them to uniquely determine the next item in the sequence.

The predict() method must predict the next item in the sequence and return it. If the next item cannot be predicted, it should return zero.

Submission

Once submissions are open, you should submit by typing

give cs2011 hw1 *.java

You can submit as many times as you like - later submissions will overwrite earlier ones.

Remember that you should not edit the files hw1.class, Predictor.java or ConstantPredictor.java. If you attempt to submit one of these files, your submitted version will be ignored and the standard version will be used instead.

The submission deadline is Thursday 30 March, 6:00 pm.
15% penalty will be applied to the (maximum) mark for every 24 hours late after the deadline.

Additional information may be found in the FAQ and will be considered as part of the specification for the project.

If you have a question that has not already been answered on the FAQ, you can email it to cs2011.hw1@cse.unsw.edu.au

Assessment

This particular project will be assessed on functionality in the first instance. Approximately two marks will be assigned for each of the five classes to be submitted. Programs failing most of the auto-testing will be examined by a human and may pick up a few marks for style, provided they are clearly written.

Programs that generate compilation errors will receive a very low mark, no matter what other virtues they may have. In general, a program that attempts a substantial part of the job but does that part correctly will receive more marks than one attempting to do the entire job but with many errors.

Bonus Challenge

In some situations the specified items will not belong to any of the above types of sequences, so the output of the program would be empty. However, we may be able to find an Approximate solution, by choosing values for the parameters a, b and c which minimize the following sum:

SUM_k>=2 [ u_k - (au_k-1 + bu_k-2 + c)]²

Two bonus marks are available to anyone who can successfully implement this in a class called ApproximatePredictor.java (Note: it can be done using a constant amount of memory, i.e. without using any arrays). This class, if attempted, should be submitted along with the other classes. The program hw1bonus.class will be used to test it.

Plagiarism Policy

Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism detection software will be used to compare all submissions pairwise. These checks may be run after the automarking and release of marks, so the released marks are not necessarily final.

First detection: negative mark for the assignment
Second detection: failure of the course
Third detection: faculty disciplinary action (including possible expulsion from the university)

DO NOT COPY FROM OTHERS; DO NOT ALLOW ANYONE TO SEE YOUR CODE

Please refer to the Yellow Form, or to section on Originality of Assignment Submissions in the Unix Primer, if you require further clarification on this matter.

Good luck!