copyright 2012 Felleisen, Proulx, et. al.

CS 2510 Spring 2012:Assignment 12 - Stress Tests; HeapSort, Priority Queue

Practice Problems

Review your implementations of the following sorting algorithms:

Selection sort from the previous lab 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.
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.

Pair Programming Assignment

These problems should be checked into your pair's SVN repository by the due date, which is WEDNESDAY 4/11/2012 at 11:59pm.

Project naming requirements

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. Every file you submit must have a header that identifies you and the problem it solves. So, for the heapsort problem the header should look like this:

// Assignment 12 Problem 1
// Partner Name1
// partner1username
// Partner Name2
// partner2username
// 11 April 2012

Submit your report as a .doc, .docx or a .pdf file. Open source equivalent of .docx is also acceptable. Name it TimingReport.xxx

Submit your Excel chart as a .xls or a .xlsx file. Open source equivalent of .xlsx is also acceptable. Name it TimingResults.xxx

Problem 1: HeapSort and Priority Queue

Problem 2: Timing Trials

Finish problems in part one and part two of the lab.

Last modified: Thu Mar 29 11:29:37 EDT 2012