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

Assignment 9

  • 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:

For this assignment you submit only your log file and your report. There is no code to be submitted.

If your HeapSort program does not work, use the student folder as given. In that case all timing for the HeapSort will report zero miliseconds. Please, note this in your report.

Due Date: Tuesday, December 3rd, 11:59 pm.

Problem 1: Priority Queue and HeapSort

You will need to add the code for your solution to Problem 4 of Assignment 7a to the subfolder student, so that your tests include tests for the HeapSort as well.

Problem 2: Sorting Algorithms Detective

Finish the Lab 12 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: