Assignment 9

Instructions

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.

• Your report on the findings of the sorting detective should be written as a professionally prepared report - use a word processor; use Excel or other spreadsheet program to create tables of data, charts that illustrate your results and insert them into your document, then add a clearly written description of your findings.

  Submit this report as one file in one of the following formats: pdf, MS Word, or open office word processor.

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:

• Which algorithms run mostly in quadratic time, i.e. O(n^2)?

• Which algorithms run mostly in O(n.log_n) time?

• Which algorithms use the functional style, using Cons lists?

• Which algorithm is the selection sort?

• Why is there a difference when the algorithms use a different Comparator?

• Copy the results into a spreadsheet. You may save the result portion in a text editor with a .csv suffix and open it in Excel (or some other spreadsheet of your choice). You can now study the data and represent the results as charts.

  Do so for at least three algorithms, where there is one of each — a quadratic algorithm and a linear-logarithmic algorithm.

• Produce a report with a paragraph that explains what you learned, using the Excel charts to illustrate this.