G5BADS formal coursework 2004-2005
The coursework consists of two parts:
There is no fixed proportion of the mark associated with each of the
two components, because they cannot be marked separately from each other.
- a Java program implementing a simple scheduler (see below)
- an essay (in pdf - other formats will not be marked!)
which explains how the program works, big-Oh complexity analysis
of the insert() and next() methods in the program, and your reasons for choosing
your data structure(s). I expect approximately 2-3 pages, no strict page
Java program: Scheduler
The program to write is a very simplified scheduler.
This scheduler is storing tasks or messages, each with a
time stamp, which arrive in no particular order (so a message
with time stamp 100 may arrive before or after a message with time
stamp 20 due to network delays etc.). On request, the scheduler
produces a task with the earliest time stamp.
The Task class is provided.
The Scheduler class has a constructor:
which creates a Scheduler with no tasks, and public methods:
public void insert(Task x)
// precondition: x is a Task object
// postcondition: x is stored by the Scheduler
public Task next()
// precondition: Scheduler has a non-empty set of tasks
// postcondition: a task with the earliest time stamp t is
// removed from the Scheduler and returned.
If there are several tasks with
the same time stamp t, any of them can be returned.
If the scheduler is empty, return null.
The insert(Task x) and next() operations should be made as fast
as possible; only constant time or logarithmic
solutions will get a mark over 59.
For testing, I also need you to write the following Scheduler method:
public boolean contains(Task x)
// precondition: x is a Task object
// postcondition: true is returned if x is in the Scheduler, otherwise
// false is returned
contains(Task x) method does not have to be implemented efficiently, it just
has to be correct.
You may use Java API classes such as ArrayList in your program, however, for
full marks, you should implement your main data structure yourself. The purpose
of this exercise is to practice implementing a non-trivial ADT in Java.
Cutting and pasting code from the textbook website or elsewhere is not
recommended. I will run JPLag or Moss plagiarism detector tool to check
for similarities between submissions and web-based
material. Strikingly similar submissions will result in deduction of marks.
Programs will be marked by humans, but I will also run correctness and timing
There will be a prize for the best solution (traditionally a bottle of wine, but
it can be replaced by beer or a Java book on request).
How to test your program
It would be best if you write your own testing code following the guidelines from
G51SWT. I wrote a very simple
test harness to get you started and to check that
your method signatures are correct.
If you want to time your program, you need to insert lots of tasks into
the scheduler, on the order of magnitude of a million. On robin, linear
implementation of next() on Scheduler with one million tasks runs in over 2000ms,
while the logarithmic one is still 0 or 1 ms.
If you are getting java.lang.OutOfMemoryError, run your program on Solaris
with -Xmx flag:
java -Xmx400m Tester
400MB should be enough, if not make it 600MB (the upper limit is 2000MB I think).
How to submit
Submissions are due at 5pm on Tuesday the 30th of November and
will be collected electronically from the subdirectory coursework/g5bads of your
Private directory (e.g., if your username is abc03u, then the files
will be collected from the directory /stud/ug/abc03u/Private/coursework/g5bads).Please
ensure that the capitalisation and spelling of your submission
directory is correct, otherwise your submission will not be collected.
All the files in that directory and any subdirectories etc. will be collected.
You will be notified by email when your submission has been
successfully collected. If you don't receive confirmation by the
1st of December, please contact me. Submissions which are not collected due to
incorrect spelling etc. will incur 5% penalty. Submissions which are one working
will be penalised 5%, two working days late 10% and so on (unless your tutor
writes to me supporting a request for extension).
You are reminded of the School's Policy on Plagiarism.