CS 261 Lab D - Searching, Sorting, and Big-O Complexity

Due Wed Sep 24 at 3:00pm

Overview

This lab will give you a chance to practice with and explore the concepts of run-time efficiency and Big-O notation. Rather than writing a stand-alone program for the lab, you'll be testing some existing algorithms (which will require writing some testing code!) to help you get a feel for talking about algorithmic complexity, as well as to see the effects of complexity differences in action. Specifically, you'll be empirically demonstrating the Big-O of the searching and quadratic sorting algorithms we've discussed in class.

This lab should be completed in pairs. Partner assignments for this lab can be found on Moodle Don't just divide up the work; rather go through things together and talk over any oddities you find!

Objectives

Necessary Files

You will need to download the copy of the zipped source files and import them into Eclipse. This file contains SearchSorts.java, a class with static implementations of some searching and sorting methods (similar to what we used in lecture), and EfficiencyTester.java, a class that you should use to help demonstrate the complexity of the provided algorithms. Note that the EfficencyTester class has a number of helper methods for quickly producing arrays of numbers.

Finally, you'll need the Lab D - Complexity Worksheet that I will hand out at the beginning of lab.

Part 1: Comparing Big-O rates

As we discussed in class, there are a number of different common growth rates for algorithmic efficiency. Your first task is to work out exactly how much of a speed difference there is between these different algorithms as the data size increases.

The first page of the worksheet contains a table for you to fill out. Each row of the table represents an algorithm with the given complexity [note that complexities are listed as functions f(n)], while each column represents the approximate number of operations for a particular data size (ignoring overhead)--thus f(10) means "run on a data set of 10 items". Other columns preresent the growth ratio between these operations, while further columns describe the approximate "wall clock time" required for the algorithm if each operation requires 1 microsecond (or 1,000,000th of a second).

Note that the table has 11 columns and 8 rows you need to fill out!

When you are finished (before you leave the lab), submit the worksheet to the professor to turn it in!

Part 2: Calculating Run-time and Big-O

For the second part of the lab, you will be empirically demonstrating the Big-O of searching and sorting algorithms, as well as evaluating how fast they run in practice (e.g., wall-clock time and run-time efficiency).

For each method (linearSearch, binarySearch, bubbleSort, selectionSort, and insertionSort), you will need to complete the included table, requiring you to do the following:

  1. Determine the number of list item comparisons made when running the method on random and ordered lists of different sizes (as specified on the worksheet).
    • Add code to the methods that will "count" the number of comparisons (calls to the compareTo() method) made. This counter should be a local variable; do not use a static variable! At the end of the method, you can print out or return the count to determine what it is.
      • Be sure and count the comparison before it occurs--since if the comparison is made in the if statement, then it won't get counted if it returns false!
    • I recommend using a for loop to easily get the comparisons for a large number of different list sizes.
    • Because the number of operations can vary based on the ordering of the list, you should make sure that your random number generation is always the same. To do this, you can specify a "seed" value for the random number generator--this effectively determines the start of the random sequence. Two random numbers generated from the same seed will always be the same. Each time a random number is generated the seed automatically changes (unless you specify it). Use the second parameter on the provided shuffled() method to specify a seed number. It doesn't matter what seed number you use, just that you use the same one for all your methods!
    • Remember that binarySearch requires a list to be sorted to work; make sure and sort your list (likely using insertionSort) before searching it! For searching, you can search for a random (but consistent) number, which can again be generated using a seeded random number generator.
  2. Determine the wall clock run-time of the method for the given list sizes. You can do this using System.currentTimeMillis(). This should give you a sense for how fast these methods work in practice.
    • Remember to "restart" the timer for each test!
    • Note that some methods may take a bit of time to run (particularly bubble sort), or report taking no time at all. Because of slight changes in the computer state, you may wish to run your "tests" multiple times and average the results.

After you have filled in the tables, be sure and answer the questions at the end of the worksheet!

Submission

Submit this lab by during in the worksheet to the professor. You can do this before you leave lab, or at the beginning of class tomorrow. Make sure both names are on the worksheet!

You are not required to turn in any code for this lab.

However, remember to log onto Moodle and submit the Lab D Partner Evaluation. Both partners need to submit evaluations!

Grading

This assignment will be graded out of 33 points: