CS 261 Lab L - The CS Detectives and The Case of the Scrambled Sorts!

Due Wed May 08 at 9:00am

Overview

"Oh no! In developing a program to demonstrate the efficiency of different sorting algorithms, the algorithms have gotten all mixed up! I have a program that graphically displays the number of comparisons, the number of swaps, and the total runtime for all of our sorting algorithms... but some dastardly villain has erased the labels on the program's interface. I need you, CS Detectives, to figure out which button is which sorting algorithm. Will you take the case?"

This lab will be completed in pairs. Partner assignments for this lab can be found on Moodle

Remember to review the pair programming guidelines before you get started!

Don't check in with other groups though! Try do this just as a pair.

Objectives

To practice testing and analyzing existing programs
To apply your understanding of algorithm efficiency to identify different techniques
To play with a practical demonstration of the differences in algorithm speed.

Necessary Files

You will need to a copy of the SortingLab.zip file. This file contains the provided program as an executable jar. You should be able to run this file by double-clicking it (once it has been extracted). Note that if you want to run the .jar from the command-line to see the terminal output, you can use the command:

java -jar SortingDetective.jar

You should use this technique if you have problems running the file (double-clicking wasn't always working for me on lab machines...)

Details

Your task is to use the provided program, performing tests and analysis to identify which which button (Alpha, Beta, Gamma, Delta, Epsilon, Zeta, or Theta) corresponds to which sorting algorithm that we've discussed in class (bubble sort, selection sort, insertion sort, shell sort, mergesort, heapsort, and quicksort).
You should be able to identify these algorithms based on their reported efficiencies: look at the number of swaps and the number of exchanges. Remember that a quadratic (O(n^2)) will quadrupal speed if you double the list size, while an O(n*lg n) algorithm will do a little bit more than twice as much work (a linear algorithm will only do twice as much!). Before you begin the lab, you may want to review your notes about the expected performances of the various algorithms.
Come up with a plan to figure out which sorting algorithm is which, so that you can match each algorithm to a button name.
- Take careful notes as you execute your plan! You will need to describe your procedure and the results of your experiments.
Note that there is absolutely no programming in this lab. A significant portion of your grade on this lab will be determined by the thoroughness of the writing of the report. This includes the completeness and clarity of your explanation (please proofread your document!)
- Your report should include your names, a table of what buttons match to what sorts, a list of experiments that prove this matching, and your argument explaining why this matching is correct.
- Remember that your report doesn't need to detail every experiment you ran. Rather, it should provide evidence to justify your conclusions. You may have a short report if your experiments are very well chosen; indeed, after you figure out the matching you might consider whether there was a shorter way to arrive at your conclusion.
Some of the sorts can be difficult to distinguish, but you can get credit if you make a compelling and valid argument (even if your conclusion ended up being wrong).

Submitting

Submit your written report (a Word document would be preferable) to the LabL submission folder on vhedwig. Make sure your names are at the top, and make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

After you have submitted your solution, log onto Moodle and submit the Lab L Partner Evaluation. Both partners need to submit evaluations.

Extensions

No extensions on this one! If you're looking for other things to do, try browsing the Wikipedia list of sorting algorithms. Figuring out different algorithms can be fun!

Alternatively, make sure you're caught up on your homework and/or use the time to work on Homework 7.

Grading

This assignment will be graded out of 18 points:

[7pt] Correctly identifying the 7 sorting algorithms
[4pt] You clearly explain/justify your matchings
[1pt] Your report is readable and easy to follow
[1pt] You have completed your lab partner evaluation