COL 106 Assignment 4

Clarifications

  • Please ensure bottom-up construction of the heap, level by level. Fill each level from left to right (taking the next un-inserted values from left to right in the input array).

    Assignment

    Implement an extendible array. The initial size of the array should be 1. Use this extendible array to implement a heap based Priority Queue as given below: 
    interface eArray <T> {
   T at(int index);
   void set(int index, T value);
}

class pTuple <T> {
   T e_;
   int priority_;
   pTuple(T e, int priority) { e_ = e; priority_=priority; }
   T element()    { return e_; }
   int priority() { return priority_; }
}

interface priorityQ <T> {
   void construct(eArray<pTuple <T>> t);
   pTuple <T> dequeue();
   void enqueue(T e, int priority);
   void enqueue(pTuple <T> t);
}

    There should be no use of arrays except inside a class that implements eArray. Arrays of String are allowed in main.

    Implementation

    Implement public class Assignment4, with a static main that takes on the command line, the name of a file containing on each line a string followed by an integer priority value. main constructs tuples for each line and constructs a priority queue.

    It then print a pre-order traversal of the heap on standard output, one nodes' tuple printed per line.

    Example

    Example input 
    Name1 is a string 239
Name2 string 889
Third     2391
Word 231
None 2
    Example output 
    Third 2391
Name2 string 889
Name1 is a string 239
None 2
Word 231

    Submission instructions

    Submission will be at moodle.

    Please ensure that you follow the following set of instructions meticulously while submitting the assignment on Moodle. Also, please note that in case of deviation from this procedure will render your submission faulty, and your assignment might not be evaluated at all by the script. Please follow these steps:

    1. On eclipse, by default, all your source files (.java files) are saved into a directory called "src" inside your project. You have to compress this directory (to zip format) and rename the zip file in this format: 
      your-entry-number_assignment4.zip
      Example: If your entry number is 2012CSZ8019, the zip file should be named 2012CSZ8019_assignment4.zip. It should expand to a directory called src, which contains all your .java files. Please make sure that you follow exactly this naming format.
    2. Next, convert the zip file to base64 format. On any linux system, you can do this easily by issuing the following command on the terminal : 
         base64 entrynumber_assignment4.zip > entrynumber_assignment4.zip.b64
      This will create a file with the same name with a b64 extension appended at the end.
    3. Upload this b64 file on moodle and submit it (in the "Submission" section). After Submission, there is an option of "Evaluate" in the "Edit" section. Click on "Evaluate". On the right side of the window, you will get information about the submission status. On clicking the "Evaluate" link, you should see a script running and producing an output of your codes' performance against the standard set of test cases that we supply internally for the assessment. A dialog box will show you the messages on how your codes performed against the benchmarks that we provided.
            Important notes