Lab 4.5: Evaluating Algorithms
Bard College – Computer Science – Data Structures

We’ll practice the experimental approach for evaluating algorithms outlined in section 1.4 (pg 174–179).

ThreeSum

First, develop run-time models T(N)T(N) of ThreeSum and ThreeSumFast on your own machine. 

  1. Gather run-time statistics for both programs using varying input sizes (e.g.  1K, 2K, 4K, 8K) using StopWatch . (Best to record the means of many experiments per input size, why?)
  1. Enter those findings into a spreadsheet.
  1. Plot the running time of both algorithms (a scatter chart with standard axes and a trend line).
  1. Log-transform the data.
  1. Plot the log-transformed data and compute the best-fit line (i.e., linear trend-line). 
  • You can use the =SLOPE(D2:D16, C2:C16) and =INTERCEPT(D2:D16, C2:C16) formulas for finding the equation of the best-fit line.
  1. Report your estimate of T(N)=aNmT(N)=aN^m and use it to predict the run-times of the various input sizes (pg. 176).
  1. Reflect on how well your model summarizes and predicts (16K) run-times.

Traveling Salesperson

Second, develop run-time models for the heuristics for finding Traveling Salesperson tours we developed last week;  follow the same process as you did with ThreeSum . Compare a simple insert (LIFO or FIFO) with one or both of your heuristics. If you were not able to get either heuristic working, use the reversing task instead (see below).

Reversing a Stream

Explore the performance of array-based data structures to reverse a stream of data. Compare the book’s resizing strategy (doubling the size of the array) with the naive approach where you grow and shrink the array by one.

 ResizingArrayStack<Integer> stack = new ResizingArrayStack<Integer>();
 while (!q.isEmpty()) stack.push(q.dequeue());
 while (!stack.isEmpty()) q.enqueue(stack.pop());

Develop models for both types of array-based data structures. You will have to modify the book’s  ResizingArrayQueue & ResizingArrayStack to grow and shrink by one.

EXTRA: You might also compare with the linked-list variety:  Queue and Stack .  

Submission

Bring a hard copy of your PDF describing your findings: include the graphs, tables of the data, and the resulting mathematical models. Include graphics showing your TSP solution working. Also bring a hardcopy of your final Tour.java file.