Problem 1: Priority Queue and Heap Sort
Problem 2: Sorting Algorithms Detective

Assignment 11

  • Learn to implement a priority queue and heapsort algorithm.

  • Explore the time compexity of sorting algorithms.


The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit.

Make sure you follow the style guidelines for code indentation.

You will submit this assignment by the deadline using the Web-CAT submission system.

With each homework you will also submit your log file named pairxxx.txt where you replace xxx with your pair number.

On top of every file you submit you will have the names of both partners, and the pair number.

The .txt file will be the log of your work on this assignment. Each log entry will have data and time, who was present (one or both of the partners) and a short comment decribing what you were working on.

Submission Details:

Due Date: Wednesday, April 3rd, 11:00 pm.

Problem 1: Priority Queue and HeapSort

Your job is to design a priority queue using the heap algorithm. You then use this to implement the heapsort algorithm and add it to a collection of algorithms to be evaluated for time-complexity.

The descrioption of this assignment is written in a tutorial style - so you can recall the lecture details.

If it helps you, draw the picture of the tree and manipulate stickies or pieces of paper to see how the algorithms for inserting and deleting nodes work.

Typically, we represent this heap as an ArrayList<T> with the first item (at index 0) unused (maybe null).

Problem 2: Sorting Algorithms Detective

Finish the Lab 11 work on measuring time spent of different sorting algorithms and finding out from the timing and test behavior which algorithms could exhibit the observed behavior.

As it says in the lab description:

Run the program a few times with small data sizes, to get familiar with what it can do. Then run experiments and try to answer the following questions: