CS 261 Lab D - Run-time Efficiency and Big-O Complexity

Due Wed Feb 12 at 9:00am

Overview

This lab will give you a chance to practice with and explore the concept of run-time efficiency and Big-O notation. Rather than writing a program as usual for a lab, you'll be working on a number of small problems to help you get a feel for talking about and algorithmic complexity.

This lab should be completed in pairs. Don't just divide up the work; rather go through things together and talk over any oddities you find!

Objectives

To practice determining run-time polynomials and Big-O complexity
To develop a stronger intuition for the speed differences between different complexity orders

Necessary Files

You will need to download the copy of the zipped source files and import them into Eclipse. This file contains EfficiencyLabMethods.java, a class with methods (similar to what we used in class) of which you'll be studying the efficiency, and EfficiencyLabTester.java, a class that you will complete to demonstrate the complexity of the methods. It also has an ArrayHelpers.java class that has some helper methods for quickly generating arrays of numbers.

Note that for this lab you'll also want to have a spreadsheet program handy (e.g., Microsoft Excel).

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.

Your professor will provide you with a worksheet ("Lab D - Complexity Worksheet") that contains a table for you to fill out. Each row of the table represents an algorithm with the given complexity, while each column represents the approximate number of operations for a particular data size (ignoring overhead). Other columns present the growth ratio between these operations, while other columns describe the approximate "wall clock time" required for the algorithm if each operation requires 1 microsecond (or 1,000,000th of a second).

You can calculate these run-times by simply plugging in the value for n.
You will want to use a calculator for this. Most any scientific calculator will do; the one built into your OS will work, or you can just use Google's calculator.
You can list wall-clock time in whatever units make sense (seconds, hours, light-years, etc).
Note that some of the really slow algorithms (e.g., factorial) may not be calculable; if so you can include that information.
Helpful fact: 2¹⁰ ≈ 1000. This can make estimating speed pretty easy.
If there are any questions, let me know!

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 Polynomials and Big-O

For part two of this lab, consider the five (5) methods in the provided EfficiencyLabMethods class [note that the last problem is optional]. For each method, do the following:

Calculate the run-time polynomial of the method. Write this polynomial in the comment of the method (e.g., T(n) = 3n+5)
- For operations, you should count any assignments, comparisons, and method calls (you can ignore mathematical operations).
- I recommend you put inline comments counting the operations for each line of code, then combine those into the polynomial!
Using the run-time polynomial, calculate the Big-O complexity of the method. Write this in the comment of the method as well (e.g., O(n^2))
In the EfficiencyLabTester, implement the appropriate testing method (e.g., methodATest()).
- In each testing method ("tester"), you should call the method in question with at least 5 different sized inputs, calculating the clock-time of each run. Print out the data size (the n) and the elapsed clock time.
  - You will need to generate some "testing" data. I recommend making arrays filled with random numbers, or with numbers from 1 to n. You are welcome to use the array generation code from lecture in your assignment (with proper credit given!)
- Does the growth in clock time reflect the Big-O efficiency you calculated? Why or not why? Include an answer to this question in this method comment for the "tester" method. You might plot these numbers on a graph (such as in Excel) to help you answer the question!
- Helpful tip: you might write a loop to call the method you are testing multiple times with increasing sized inputs. You might also want to run the "tester" method multiple times, just in case there are any computer flukes!
- Think about the different "sizes" of data you should use for each method.

Submission

Submit Part 1 by handing the worksheet to the professor before you leave lab. Make sure both names are on the paper!

Submit Part 2 (both EfficiencyLabMethods and EfficiencyLabTester) to the Lab D submission folder on hedwig. One partner should upload the code--we will only grade one copy! Make sure both your names are in the class comments at the top of both classes. The lab is due at the start of class the morning after lab.

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

Grading

This assignment will be graded on approximately the following criteria:

The Part 1 worksheet is complete and accurate [30%]
You have determined the run-time polynomial for each of the 5 required method [20%]
You have determined the Big-O complexity for each method [25%]
You have demonstrated that the method has that complexity using wall-clock time [20%]
You completed your lab partner evaluation [5%]