Assignment 10
Goals: Learn to design an efficient implementation of a priority queue; investigate the time complexity of sorting algorithms.
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.
Due Date: Tuesday, November 20th, 11:59 pm.
Practice Problems
Practice Problems
Review your implementations of the following sorting algorithms:
Selection sort from the previous assignment and from the lectures.
Insertion sort from the previous assignment.
QuickSort from Fundies 1 and from the lectures.
Binary Tree Sort from the assignment that dealt with binary search trees and from lectures.
MergeSort from Fundies 1 and from the lectures.
Try to implement the QuickSort and the MergeSort. In both cases, you probably want to use two ArrayLists, one that provides the data to sort, and the other where you save the results of the next step in the divide and conquer process.
Note: This is not exactly a practice problem, but it is something you should try to do, think about, and research a bit to gain fluency with more complex algorithms.
Problem 1 HeapSort and Priority Queue
Finish the problem from Lab 10.
Problem 2 Timing Trials
Finish the problem from Lab 10.
Hand in you report as a porfessionally designed file (Word, PDF, or open source word processor format). Include in it tables of results and charts that illustrate/support your findings.