​​Lab 5: Evaluating Algorithms
​​Bard College – Computer Science – Data Structures
​​
 
User-uploaded image: image+10.png
​​
​​
​​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, 16K) 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-plot 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.
  1. ​​Reflect on how well your model summarizes and predicts run-times.

​​Traveling Salesperson

​​Second, develop run-time models for the two heuristics for finding Traveling Salesperson tours we developed last week;  follow the same process as you did with ThreeSum​ . If you were unable to get both heuristics working yet, use the reversing task in its place (see below).

​​Submission

​​Submit a PDF file describing your findings: include the graphs, tables of the data, and the resulting mathematical models.
​​
​​

​​EXTRA: Reversing a Stream

​​Compare the performance of array-based data structures to reverse a stream of data. Compare the book’s 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 1.
​​
​​EXTRA; EXTRA: You might also compare with the linked-list variety:  Queue​ and Stack​ .  

​​Lab 5 Checklist

  • ​​Did I evaluate both algorithms?
  • ​​Did I use the specified varying input sizes?
  • ​​Does my report include graphics such as graphs, tables, and mathematical models?
​​