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:
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.
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
k2/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
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
k2-k+1, or it could be a Homogeneous sequence
uk=2uk-1+uk-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
uk=-2uk-1-uk-2+1, so the output is:
Recurrent [-3 4 -4 5 -5]Other examples of input and output will be provided in the
samplesdirectory as the project progresses.
The complete program will consist of eight classes. Three of them are provided for you:
Your task is to write, and submit, the remaining five classes:
ArithmeticPredictor.java GeometricPredictor.java QuadraticPredictor.java HomogeneousPredictor.java RecurrentPredictor.javaEach of these must
Predictorclass, and implement the following methods:
public String toString();
public void step( double u );
public boolean canPredict();
public double predict();
toString() method should return
the name of the sequence type, as given in the table above.
step() method will be called
for each item in sequence.
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.
predict() method must predict the next
item in the sequence and return it.
If the next item cannot be predicted, it should return zero.
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
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
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.
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
which minimize the following sum:
SUMk>=2 [ uk - (auk-1 + buk-2 + c)]2
Two bonus marks are available to anyone who can successfully
implement this in a class called
(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.
will be used to test it.
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.
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.