1. Test two algorithms provided in class StringExperiment of composing a string with two different ways:

(a) with the use of StringBuilder and (b) with copies of characters.

a. For this practice, you would need to change some related parameters such that the execution times for both can be completed with a range of 1~3 minutes and that the real time for concatenation can correctly reflect the right big-Oh evaluations.

b. You would need to jot down the time vs data size and figure out the big-Oh functions for the algorithms.

2. Write a test program to test 5 different methods (algorithms) defined in the class Exercises.

a. You may need in the test program to define an array of integers as the testing data. Preferably, write code to generate data, save to a text file, and read it back for testing (sample code provided in InputOutput.java program).

b. Test the 5 methods/algorithms with carefully prepared data, record the execution times, jot down the times vs data size.

c. You are to answer Big-Oh related questions for the methods/algorithms. CODE:

public class StringExperiment {

/** Uses repeated concatenation to compose a String with n copies of character c. */ public static String repeat1(char c, int n) { String answer = ""; for (int j=0; j < n; j++) answer += c; return answer; }

/** Uses StringBuilder to compose a String with n copies of character c. */ public static String repeat2(char c, int n) { StringBuilder sb = new StringBuilder(); for (int j=0; j < n; j++) sb.append(c); return sb.toString(); }

/** * Tests the two versions of the 'repeat' algorithm, doubling the * size of n each trial, beginning with the given start value. The * first command line argument can be used to change the number of * trials, and the second to adjust the start value. */ public static void main(String[] args) { int n = 50000; // starting value int trials = 10; try { if (args.length > 0) trials = Integer.parseInt(args[0]); if (args.length > 1) n = Integer.parseInt(args[1]); } catch (NumberFormatException e) { } int start = n; // remember the original starting value

// let's run version 2 (the quicker one) first System.out.println("Testing repeat2..."); for (int t=0; t < trials; t++) { long startTime = System.currentTimeMillis(); String temp = repeat2('-', n); long endTime = System.currentTimeMillis(); long elapsed = endTime - startTime; System.out.println(String.format("n: %9d took %12d milliseconds", n, elapsed)); n *= 2; // double the problem size }

System.out.println("Testing repeat1..."); n = start; // restore n to its start value for (int t=0; t < trials; t++) { long startTime = System.currentTimeMillis(); String temp = repeat1('-', n); long endTime = System.currentTimeMillis(); long elapsed = endTime - startTime; System.out.println(String.format("n: %9d took %12d milliseconds", n, elapsed)); n *= 2; // double the problem size } } }

import java.io.IOException; import java.util.Formatter; import java.util.Scanner; import java.nio.file.Paths;

public class InputOutput { public static void main(String[] args) throws IOException { //output to a text file Formatter output = new Formatter("testData.txt"); output.format("%d %d %d", 123, 2, 3); output.close(); //read from a text file that contains integers Scanner input = new Scanner(Paths.get("testData.txt")); int x; while (input.hasNext()){ x = input.nextInt(); System.out.printf("%d, ", x); } input.close(); System.out.println(" HHHHHHHHHHHHHh"); } }

class Exercises {

/** Returns the sum of the integers in given array. */ public static int example1(int[] arr) { int n = arr.length, total = 0; for (int j=0; j < n; j++) // loop from 0 to n-1 total += arr[j]; return total; }

/** Returns the sum of the integers with even index in given array. */ public static int example2(int[] arr) { int n = arr.length, total = 0; for (int j=0; j < n; j += 2) // note the increment of 2 total += arr[j]; return total; }

/** Returns the sum of the prefix sums of given array. */ public static int example3(int[] arr) { int n = arr.length, total = 0; for (int j=0; j < n; j++) // loop from 0 to n-1 for (int k=0; k <= j; k++) // loop from 0 to j total += arr[j]; return total; }

/** Returns the sum of the prefix sums of given array. */ public static int example4(int[] arr) { int n = arr.length, prefix = 0, total = 0; for (int j=0; j < n; j++) { // loop from 0 to n-1 prefix += arr[j]; total += prefix; } return total; }

/** Returns the number of times second array stores sum of prefix sums from first. */ public static int example5(int[] first, int[] second) { // assume equal-length arrays int n = first.length, count = 0; for (int i=0; i < n; i++) { // loop from 0 to n-1 int total = 0; for (int j=0; j < n; j++) // loop from 0 to n-1 for (int k=0; k <= j; k++) // loop from 0 to j total += first[k]; if (second[i] == total) count++; } return count; }

}