Programming question for Homework 1 & 2

Implement a max-priority heap class, and use this class to implement a HeapSort algorithm that sorts Vector objects. The heap is implemented as a complete binary tree, and is encapsulated in a class (called Heap) that extends the Vector class. The tree used to represent the heap is stored in the Vector as follows. The root of the tree is stored at position 0 of the Vector, and, for every i = 0..(size()-1), the left and right children of the element stored at position i, if they exist, are stored at positions 2i+1 and 2i+2, respectively. For every element of the heap, the priority of this element must be higher than or equal to that of its children. To compare the priorities of two heap elements an instance of a class that implements the PriorityComparator interface is used.

For Homework 1, due Thursday, February 1 (5:30pm), you should implement the following methods of the Heap class (described in the starter code):

The worst-case time complexity of buildHeap() should be O(n), and the worst-case time complexity of extractTop() should be O(logn), where n is the size of the heap.

To mark your assignment, we will test the above two methods using a tester routine that is more thorough than the sample HeapTester class provided. The sample HeapTester class that we provide is very basic, running it successfully does not guarantee that your code is correct or will pass our marking tester routine. You are encouraged to derive your own  test cases. Each method gets 10 marks if it works correctly, and gets 0 marks otherwise.

For Homework 2, due Thursday, February 15 (5:30pm), you should implement the following methods of the Heap class (described in the starter code):

You must also implement the following method of the HeapSort class:

The worst-case time complexity of insertElement(), replaceElement() and removeElement() should be O(logn), and the complexity of sort() should be O(nlogn), where n is the size of the heap.

We will test the above procedures with our own tester code. As mentioned above, the tester code that we provide is very basic, and running it successfully does not guarantee that your code is correct or will pass our marking tester routine. Each one of these four procedures gets 5 marks if it works correctly, and gets 0 marks otherwise.

For more details, including exact specifications of the methods that you should implement, see the starter code. All of your work must be done inside the Heap class and the HeapSort class, where indicated by comments that start with: "// TODO:". You may also add appropriate private instance variables or helper methods.

Starter code:

Submission Instructions for Homework 1:

  1. Submit your code using the "submit" mechanism (by 5:30pm on the due date). Use the following command from the directory containing your solution: submit -N PGM1 cscb63s Heap.java
    The command "man submit" contains general instructions for submitting your code electronically.

  2. Submit only the .java file Heap.java of the starter code (after you have implemented the missing parts) to the directory called PGM1 . All the code that you implement should be inside this file.

  3. Do not submit any other file, and in particular, do not submit any class files. If you do, we will delete them before we compile your code.

  4. Do not submit any printout of the code.

  5. Do not rename the file Heap.java, or any of the methods and variables found in our starter code.

  6. Write your name, student number and username in a comment at the top of the Heap.java file. If you have a partner, you should also write the corresponding information about your partner.

  7. We will compile your code by typing "javac Heap.java", and we will test the resulting .class file(s) using our own tester code (which is similar to, but more thorough than, the tester code that we provide as part of the starter code).

  8. Your code must compile and run on the standard Unix/Linux system of your campus (cdf/fissure/cslinux). Test it there! Programs that do not compile and run get 0 marks.

Submission Instructions for Homework 2:

  1. Submit your code using the "submit" mechanism (by 5:30pm on the due date). Use the following command from the directory containing your solution: submit -N PGM2 cscb63s Heap.java HeapSort.java
    The command "man submit" contains general instructions for submitting your code electronically.

  2. Submit only the .java files Heap.java and HeapSort.java of the starter code (after you have implemented the missing parts) to the directory called PGM2. All the code that you implement should be inside these two files.

  3. Do not submit any other files, and in particular, do not submit any class files. If you do, we will delete them before we compile your code.

  4. Do not submit any printout of the code.

  5. Do not rename the files Heap.java and HeapSort.java, or any of the methods and variables found in our starter code.

  6. Write your name, student number and username in a comment at the top of the Heap.java file. If you have a partner, you should also write the corresponding information about your partner.

  7. We will compile your code by typing "javac Heap.java" and "javac HeapSort.java", and we will test the resulting .class file(s) using our own tester code (which is similar to, but more thorough than, the tester code that we provide as part of the starter code).

  8. Your code must compile and run on the standard Unix/Linux system of your campus (cdf/fissure/cslinux). Test it there! Programs that do not compile and run get 0 marks.