CompSci-61B Lab 4
Big Oh and Timing Studies

There are no new class developments in this lab assignment. Instead we take pause to reflect upon work already done. We did not bother to analyze the scalability of the accessors and mutators we developed so far -- we just wrote what we had to in order to make them work. Tests with small numbers of values did not reveal any consequences of our choices. In only one case did we even mention time efficiency, and that was with "compsci61b.MyLinkedList.add(T value)" vs "compsci61b.testing.MyLinkedList.add(T value)".

In this assignment we will determine and verify the big-oh performance of the algorithms we've used so far. This will involve determination through analysis, or counting of the #of operations as a function of size, and doing actual timing tests. You will write compsci61b.testing.TimingTests.java, with main only. In successive exercises, you will create and further develop this program. Submit only your last version of the program!

This assignment is worth 40 points, and consists of 8 exercises. Zero points will be awarded for programs with misspelled filenames, or incorrect case. Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader. Be sure to complete both exercises and post the lab4.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work. Check the course outline for due dates for lab assignments.

1. compsci61b.testing.MyArrayList.add(T)
2. compsci61b.testing.MyArrayList.add(int, T)) at the front
3. compsci61b.testing.MyArrayList.add(int, T) in the middle
4. compsci61b.testing.MyArrayList.add(int, T) at the end
5. compsci61b.testing.MyArrayList.remove(int) at the front
6. compsci61b.testing.MyArrayList.remove(int) in the middle
7. compsci61b.testing.MyArrayList.remove(int) at the end
8. compsci61b.testing.MyArrayList.clear()
9. compsci61b.testing.MyArrayList.replace(int, T)
10. compsci61b.testing.MyArrayList.getEntry(int)
11. compsci61b.testing.MyArrayList.contains(T)
12. compsci61b.testing.MyArrayList.size()
13. compsci61b.testing.MyArrayList.isEmpty()
14. compsci61b.testing.MyArrayList.isFull()
15. compsci61b.testing.MyArrayList.toString()

For example, here is how to express the answer for one of the above:

System.out.println("compsci61b.testing.MyArrayList.remove(int) in the middle is O(n).");

1. compsci61b.MyArrayList.add(T)
2. compsci61b.MyArrayList.add(int, T) at the front
3. compsci61b.MyArrayList.add(int, T) in the middle
4. compsci61b.MyArrayList.add(int, T) at the end
5. compsci61b.MyArrayList.remove(int) at the front
6. compsci61b.MyArrayList.remove(int) in the middle
7. compsci61b.MyArrayList.remove(int) at the end
8. compsci61b.MyArrayList.clear()
9. compsci61b.MyArrayList.replace(int, T)
10. compsci61b.MyArrayList.getEntry(int)
11. compsci61b.MyArrayList.contains(T)
12. compsci61b.MyArrayList.size()
13. compsci61b.MyArrayList.isEmpty()
14. compsci61b.MyArrayList.isFull()
15. compsci61b.MyArrayList.toString()

For example, here is how to express the answers for two of the above:

System.out.println("compsci61b.MyArrayList.add(int, T) at the front is O(n).");
...
System.out.println("compsci61b.MyArrayList.isEmpty() is O(1).");

1. compsci61b.testing.MyLinkedList.add(T)
2. compsci61b.testing.MyLinkedList.add(int, T) at the front
3. compsci61b.testing.MyLinkedList.add(int, T) in the middle
4. compsci61b.testing.MyLinkedList.add(int, T) at the end
5. compsci61b.testing.MyLinkedList.remove(int) at the front
6. compsci61b.testing.MyLinkedList.remove(int) in the middle
7. compsci61b.testing.MyLinkedList.remove(int) at the end
8. compsci61b.testing.MyLinkedList.clear()
9. compsci61b.testing.MyLinkedList.replace(int, T)
10. compsci61b.testing.MyLinkedList.getEntry(int)
11. compsci61b.testing.MyLinkedList.contains(T)
12. compsci61b.testing.MyLinkedList.size()
13. compsci61b.testing.MyLinkedList.isEmpty()
14. compsci61b.testing.MyLinkedList.isFull()
15. compsci61b.testing.MyLinkedList.toString()

For example, here is how to express the answers for two of the above:

System.out.println("compsci61b.MyLinkedList.add(int, T) at the end is O(n).");
...
System.out.println("compsci61b.MyLinkedList.remove(int) at the front is O(1).");

1. compsci61b.MyLinkedList.add(T)
2. compsci61b.MyLinkedList.add(int, T) at the front
3. compsci61b.MyLinkedList.add(int, T) in the middle
4. compsci61b.MyLinkedList.add(int, T) at the end
5. compsci61b.MyLinkedList.remove(int) at the front
6. compsci61b.MyLinkedList.remove(int) in the middle
7. compsci61b.MyLinkedList.remove(int) at the end
8. compsci61b.MyLinkedList.clear()
9. compsci61b.MyLinkedList.replace(int, T)
10. compsci61b.MyLinkedList.getEntry(int)
11. compsci61b.MyLinkedList.contains(T)
12. compsci61b.MyLinkedList.size()
13. compsci61b.MyLinkedList.isEmpty()
14. compsci61b.MyLinkedList.isFull()
15. compsci61b.MyLinkedList.toString()

For example, here is how to express the answers for two of the above:

System.out.println("compsci61b.MyLinkedList.add(int, T) at the end is O(1).");
...
System.out.println("compsci61b.MyLinkedList.remove(int) in the middle is O(n).");

1. Create a "compsci61b.MyList" object of the class "compsci61b.MyArrayList" for either Integer storing Double values -- your choice.
2. Fill the Double list with randomly-generated values, using Math.random(), which returns fractional values between 0 and 1. Or fill the Integer list with zero values, or some number of your choosing.
3. Prompt the user for how many values to add, and add them in a for-loop. There will be 3 additional tests besides this one, so prompt before every test -- some tests are faster than others. Ref: Burns, chapter 5.
4. Measure the elapsed time for the operation, and print the results.
5. Double the #of values to add, and repeat for a total of 4 times. That is, if the user enters 100 for the number of values to add, build 4 data structures of sizes 100, 200, 400, and 800. Be sure to recreate the data structure object for each repetition.
6. Report the results with 5 values per repetition like in the lecture topic 4 notes, in an aligned table. The values in the last 2 columns in each line should be roughly the same. Show the last value, "normalized", to 2 decimal digits. (The "normalized" value is the value from column 4 divided by the value in the first line's column 4.)
7. Include a heading above the listed results, like "Timing test for MyArrayList.add(int, T) at the front, O(n)".

For example:

       Timing test for MyArrayList.add(int, T) at the front, O(n)
------------------------------------------------------------------------
     n      big oh  elapsed time in millis   elapsed time / big oh  normalized
------  ----------  ----------------------   ---------------------  ----------
  1000        1000                    1324                  1.3240        1.00
  2000        2000                    2745                  1.3725        1.04
  4000        4000                    5501                  1.3753        1.04
  8000        8000                   10698                  1.3337        1.01

Do not report the results of your own tests. Every time the tests are run, the results may be somewhat different -- and on other systems they may be very different. But the consistency of the last column should remain in all cases.

HINT. This example shows how to get tabular output in Java SE, with the first 4 columns from the above table:

System.out.printf("%6d%12d%24d%24.4f\n", n, bigOh, elapsedMillis, elapsedOverBigOh);

Create your final version of lab4.jar, with files from this and all previous labs. Post your lab4.jar file to your student UNIX account for grading and credit.

• Before you can time an operation on a data structure that has "n" values already stored in it, you have to actually build such a data structure. It does not matter what values are stored, so they might as well all be zero or some other number of your choosing. To avoid taking lots of time to prepare the data structure, add at index zero for linked lists, since that is O(1) -- adding "n" values to the front is O(n). For arrays, you would add at the end, because that is O(1) -- adding to the front is O(n), and adding "n" values to the front is O(n-squared)! So before each timing test of an operation with a data structure of size "n", create an empty data structure, and use a simple for-loop to fill it with "n" values, using an O(1) operation. Then start the timer, do the operation, and end the timer.
• Here's how to time something in Java:

  long start = System.currentTimeMillis();
  ...do something...
  long end = System.currentTimeMillis();
  long elapsedTime = (end - start); // in milliseconds
  

• We're timing some operations that are O(1) -- they are almost too fast to time. To time something that is very fast, do it a large number of times (like 1,000,000) and add the time it takes to do all of them.

  long elapsedTime = 0;
  for (int i = 0; i < 1000000; i++) // 1,000,000 repetitions
  {
    long start = System.currentTimeMillis();
    ...do something with a data structure of size "n"...
    long end = System.currentTimeMillis();
    elapsedTime += (end - start); // in milliseconds
    ...reset the data structure for next repetition, if necessary...
  }
  

• Since we are dealing with filled data structures, make sure that when you do 1,000,000 repetitions that you use the same data structure size for each repetition. That means if you are doing a timed "add", be sure to reset the data structure for next repetition by doing a "remove" before going to the next repetition, and do not include the "remove" in the time calculation (i.e., put it in the loop after the elapsedTime +=).
• If your test time is too fast, your calculation of the normalized fraction may divide by zero. In that case you will get NaN as a result -- "not a number".
• For a non-zero timing test, the normalized fraction should be 1.00 for the first in a series of tests. This fraction should be close to 1.00 for the remaining tests. But if "n" is too small for the first test, other "overhead" effects may dominate the operation that you are testing. The result is that subsequent tests that double the values of "n" may all have the same normalized fraction as each other, but not equal to 1. That means your initial "n" is too small -- try doubling it.
• Expect wide variability in the results, even when you repeat them with no changes. What you are looking for is some stability in the normalized fraction -- if you are wrong about the big oh determination, you should see that the normalized fraction grows or decays rapidly. (To see this effect, try a wrong big oh on purpose.)

[ Home | Contact Prof. Burns ]