Comp 121 – Introduction to Data Structures

Comp 121 – Introduction to Data Structures. Fall 2000

Programming Assignment 2 -- Due October 4, 2000

Let class C be a class for which the "£ " operator is defined in a reflexive, antisymmetric, and transitive manner. For any collection of objects of class C, a minimum object in the collection is one that is £ every other object in the collection.

A priority queue for such a class C is an abstract data type which supports the following public interface:

template <class C>

class pqueue

{

public:

pqueue(); //constructor

~pqueue(); //destructor

bool isEmpty() const; //is the priority queue empty?

bool isFull() const; //is the priority queue full?

void insert(const C & x);//insert x into the priority queue

C min() const; //return the minimum object in the priority queue

void deleteMin(); //delete the minimum object from the priority queue

};

Implementing a priority queue.You are to provide a complete implementation of the priority queue ADT. Use an array for internal representation. You may either choose to keep this array sorted at all times (in which case the minimum element is easily found), or you may keep it as an unsorted list and search for the minimum element as needed. Jutify your design decision – provide run-time analysis (bigOh run-times) of each operation in your chosen implementation.

Priority-queue sort. Priority queues can form the basis of a sorting algorithm – given a file of data-items that are to be sorted, we can insert these elements into a priority queue, and then repeatedly delete the minimum element from the priority queue until it is empty. Test your priority queue implementation by using it to sort a number of points, where a point is specified according to its x- and y- coordinates, and points are compared according to their distance from the origin (the point with coordinates (0,0)). Assume that you will read in the input points from the standard input, where you will be provided with first the number of points, and then ordered pairs of integers representing the points.

You are also required to collect timing information (by using the Unix time command) on the performance of this sorting algorithm in sorting certain data-sets that will be made available on the class web-page prior to the assignment due-date. Read the manual pages on the time command to learn how to do so. Sort each input file provided several times, and record the time required for each run.

Rules for submitting this (and future) programs:

You are not permitted to work in groups – all your work must be your own, and you must attest to this in a signed comment that begins each program – failure to do so results in your program not being graded.

Include a complete listing of all your code, input files, and output files

Your code must be appropriately commented --- if we don’t understand your code with reasonable effort, you get no credit for it.

Include a test plan detailing how you tested your program, and why you believe it is correct.

Include a (neatly typed – not handwritten) design plan and some general comments on the structure and layout of your assignment.

Summarize the timing information you have collected in tabular form. Based upon this timing information, draw conclusions regarding the runtime complexity of your sorting program.

All of the above should be placed in an envelope with your name and student-ID on the outside, and submitted at the beginning of class on the due date. Submissions will not be accepted after 10 minutes have elapsed from the start of class – no late submissions will be accepted without documented reasons.