Bard College – Computer Science – Data Structures
We’ll practice the experimental approach for evaluating algorithms outlined in section 1.4(pg 174–179).
ThreeSum(we’ll do this together)
First, develop run-time models T(N) of ThreeSum and ThreeSumFast on your own machine.
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?)
Enter those findings into a spreadsheet.
Plot the running time of both algorithms(a scatter chart with standard axes and a trend line).
Log-transform the data.
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.
Report your estimate of T(N)=aNm and use it to predict the run-times of the various input sizes(pg. 176).
Reflect on how well your model summarizes and predicts(16K) run-times.
CAVEAT: One downside of this log-log line fitting method is that it does not treat all of the points the same; the smaller values, which are pretty noisy, have a disproportionate influence on the fitted model. One way to(somewhat) alleviate this problem, is to only include the data points that take > 0.25 seconds or so, which likely is a different set of inputs for different algorithms.
Reversing a String
A common programming task is building a larger string from smaller pieces. For example, imagine we want to reverse all the characters in a stream or file.
$ echo"hello" | java Reverse
$ olleh
Our first instinct is to use string concatenation:
publicclassReverse {
publicstaticvoidmain(String[] args){
String s = "";
while (StdIn.hasNextChar()) {
char c = StdIn.readChar();
s = c + s; //tack on the character to the front of the string
}
System.out.println(s.length()); // or println(s)
}
}
Another Java class for doing this is called StringBuilder.
publicclassReverseSB{
publicstatic void main(String[] args) {
StringBuilder sb = new StringBuilder();
while (StdIn.hasNextChar()) {
char c = StdIn.readChar();
sb.append(c);
}
String s = sb.reverse().toString();
System.out.println(s.length()); // or println(s)
ThreeSum (we’ll do this together)
Reversing a String
$ echo "hello" | java Reverse$ ollehpublic class Reverse { public static void main(String[] args) { String s = ""; while (StdIn.hasNextChar()) { char c = StdIn.readChar(); s = c + s; //tack on the character to the front of the string } System.out.println(s.length()); // or println(s) }} public class ReverseSB { public static void main(String[] args) { StringBuilder sb = new StringBuilder(); while (StdIn.hasNextChar()) { char c = StdIn.readChar(); sb.append(c); } String s = sb.reverse().toString(); System.out.println(s.length()); // or println(s) }