Objectives:

• Learn how to time code
• Get a feel for the relative speed of different operations
• Generate and interpret growth functions of code

Activity

Create and clone this GitHub Classroom repository: classroom.github.com/g/z-KjfgMW

Begin by watching this video describing the timing code and how it works. The video also discusses how to plot results.

Prepare a document with the following information:

1. Compare the running times of max, sumInts, and multiplyInts:
   • Remove the comments from tests 1, 2 and 3 in main.
   • Run the main method.
   • Plot the data in columns 1 and 2 of the resulting files. If you are using gnuplot you can use this command: plot "sumInt.bigO", "multInt.bigO", "max.bigO"
   Include the graph in your lab write up.
2. Find the (approximate) slope of each line in the graph.
3. About how much slower is multiplication than addition?
4. Graph the running times of sumProductPairsSlow and sumProductPairsFaster (tests 4 and 5).
5. Approximately how much faster is sumProductPairsFaster than sumProductPairsSlow. Notice that the graphs both have a parabolic shape, and that the difference in speed (as a percentage) is consistent. This is how we know the two algorithms are in the same class (i.e., have the same big-O).
6. Graph the running time of sort (test 6).
7. Find the line that best fits the graph. (You can "eyeball it". No need to use fancy regression tools.) If you are using gnuplot you can use a command similar to this: plot "sort1.bigO", x*log(x). Notice that x*log(x) is not in quotes.
8. Notice that the graph is not quite a line. It curves up slightly. A graph of the form a*x*log(x) should fit better. Find the coefficient a. Plot both graphs together and include them in your lab write up.
9. Graph the running times of insertAtHead and insertAtTail (tests 9 and 10).
10. Do the two methods belong to the same complexity class (i.e., have the same big-O)? If not, which one is faster? Why?

Examine the code for insertAtHead and insertAtTail. Notice that the ArrayList is actually stored in a variable of type List. List is an interface that ArrayList implements. The class LinkedList also implements the List interface. This means you can replace new ArrayList<Integer>() with new LinkedList<Integer>() and the code will still compile and run.

11. Replace the ArrayList in insertAtHead and insertAtTail with a LinkedList as described above. Then, generate graphs for the new code. (You can use tests 10 and 11).
12. Describe any differences you see. Speculate about the causes of the differences. (Make sure your output for tests 10 and 11 differ from that of 9 and 10. If it doesn't you didn't get the code modified correctly.)
13. Optional: Graph the running times of sumIntsBig and multiplyIntsBig (tests 7 and 8). Are these graphs O(n). If not, why not?

Submission

Updated Wednesday, 8 July 2020, 6:31 PM