CSE 2010: Asgn #9, Experiment

Due: Wednesday, 17 June 2009 (midnight)

The Task

Perform several experiments on your computer and collect the running time of the Josephus program and the insertion sort program.

The Experiments

The programs

For your convenience, the programs are already instrumented and found in the jar file experiment.jar. You don't have to write any new code for this assignment. If your DLL code is not complete, then you won't be able to run all the experiments.

Josephus

java.util.LinkedList; skip=7; n=10,000,...,90,000; trials=10 

java -cp experiment.jar Josephus10 java.util.LinkedList 7 10000 10

java.util.ArrayList; skip=7; n=10,000,...,90,000; trials=10 

java -cp experiment.jar Josephus10 java.util.ArrayList 7 10000 10
java -cp experiment.jar Josephus10 java.util.ArrayList 7 20000 10
...
java -cp experiment.jar Josephus10 java.util.ArrayList 7 90000 10

[Your Doubly Linked List Class]; skip=7; n=10,000,...,90,000; trials=10 

java -cp experiment.jar Josephus10 DLL 7 10000 10
java -cp experiment.jar Josephus10 DLL 7 20000 10
...
java -cp experiment.jar Josephus10 DLL 7 90000 10

Sort

java.util.LinkedList; seed=4321567; n=200,...,1,800; trials=50 

java -cp experiment.jar Sort10 java.util.LinkedList 4231567 200 50
java -cp experiment.jar Sort10 java.util.LinkedList 4231567 400 50

java.util.ArrayList; seed=4321567; n=200,...,1,800; trials=50 

java -cp experiment.jar Sort10 java.util.ArrayList 4231567 200 50
java -cp experiment.jar Sort10 java.util.ArrayList 4231567 400 50

[Your Doubly Linked List Class]; seed=4321567; n=200,...,1,800; trials=50 

java -cp experiment.jar Sort10 DLL 4231567 200 50
java -cp experiment.jar Sort10 DLL 4231567 400 50

Curve Fitting

Fit the Josephus program to a linear equation y=a+b*n and sort to a quadratic equation y=a+b*n+c*n*n

Report

Using Excel, report the following data

  1. Six sets of timing data.
  2. Two graphs (use type "line with markers"), each with three curves

Answer the following questions in a text file:

  1. What is the order of magnitude of the basic list operations performed by a reasonable implementation of the Josephus program? Explain.
  2. What is the order of magnitude of the basic list operations performed by a reasonable implementation of insertion sort program? Explain.
  3. For each class used in the experiments for the Josephus problem what is the equation of the best fitting line? What is the RMS error? What is the correlation coefficient?
  4. Perdict the performance of 
          java -cp experiment.jar Josephus10 A/L/DLL 7 115000 10
    How many seconds? Explain.
  5. How many seconds do you actually get?
  6. For each class used in the experiments for the Josephus problem does the class performance fit a linear curve?
  7. Explain the perfomance on any class implementing the Josephus problem which does not fit a line.
  8. For each class used in the experiments for sorting what is the equation of the best fitting quadratic? What is the RMS error? What is the correlation coefficient?
  9. Perdict the performance of 
          java -cp experiment.jar Sort10 A/L/DLL 4231567 1950 50
    How many seconds? Explain.
  10. How many seconds do you actually get?
  11. For each class used in the experiments for sorting does the class performance fit a quadratic curve?
  12. Explain the perfomance on any class implementing sort which does not fit a quadratic curve.

Turning it in

Turn in the Java source code for the program using the submission server. The file name should be Caesar.java and the project is asgn09. Be sure your name is in comments at the beginning of your program as required in the standard header for this class. For your convenience, here is a submission form for this assignment.

File 1
File 2
Control code:
Course=cse2010
Project=asgn09

Ryan Stansifer <ryan@cs.fit.edu>
Last modified: Tue Jun 23 18:32:47 EDT 2009