G5BADS formal coursework 2004-2005

Scheduler

The coursework consists of two parts:
  1. a Java program implementing a simple scheduler (see below)
  2. 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 limit.
There is no fixed proportion of the mark associated with each of the two components, because they cannot be marked separately from each other.

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: 
Scheduler()
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 tests.

Prize

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 day late 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.