Due: Thursday April 4th by 11:55pm

Revisions History:
- Created Mar. 11rd, 2013
- Revised Mar 18th, 2013 text

Assignment Goals:

1. Practice designing a new data structure to solve a given problem.
2. Practice with data structure augmentation analysis.
3. Practice experimentally evaluating data structure performance.

Introduction

The Global Computational GRID accepts compute jobs and answers a number of queries. When a job is submitted it is given a unique id number, an estimate of the jobs length in minutes and a priority number between 1 and 1000 where 1000 has the highest priority and 1 the lowest. The Global Computational GRID maintains all jobs in a data structure that can perform the following operations:

1. insert(id, length, priority, data): Insert a new job consisting of an unique id, a job length estimate  (0..10,000), a priority number (0..1000), and up to 2K of binary data.
2. delete(id): Given a job id number, delete the job and return its id if successful or -1 if it can not be found.
3. next(): Determine the next job to be worked on (i.e. of the jobs with highest priority the one that was inserted earliest one of the jobs having highest priority). Return the id of the next job to be worked on or -1 if the data structure is empty.
4. estimate(id): Estimate for a job how long until it is finished. That is, under the assumption that no more jobs come in or are deleted, the sum of the estimates for all jobs to be done before the job with the specified id  . Return -1 if the job does not exist.

Steps

1)      Design a data structure and a set of operations for The Global Computational GRID. The task here is to describe in words and pictures a data structure that is asymptotically as fast as you can make it under the assumption that all operations are equally likely. You may make several proposals but be sure to indicate which you feel will work best and why. Submit your write up as a MSWord or .pdf file. This is a design exercise in which you will be marked on the clarity and efficiency of your solution. You may design a composite data structure that uses other data structures as helpers. In your analysis you should focus on worst case performance.

2)      Implement one of your data structures for solving the Global Computational GRID problem. You may use code from the text or other sources but you must be sure to credit the original source. Be sure to define an appropriate interface. Marking will take into account both the complexity of your implementation and its quality.

3)      Test your data structure code thoroughly.

4)      Evaluate your data structure by running timing experiments. Your evaluation method should read an input file and produce an output file as follows. 

i <integer> <integer> <1..1000> <text> returns id or -1 if unsuccessful
d <integer> returns id or -1 if unsuccessful
n returns id or -1 if unsuccessful
e returns <integer> or -1 if unsuccessful

Think carefully about what test datasets best evaluate your solution. If you email me test datasets I will post them for the class to share.

Be sure follow all of the code craft requirements carefully! Be sure to do sufficient testing! You are to use only code that you have developed yourself for this assignment.