Sample code is provided for solving the following problems for very small datasets. You need to adapt the given sample code and design and implement your solutions for different algorithms (good and bad ones) for each problem. There are 2 or 3 different solutions/algorithms for a problem: 1. Fibonacci problem (2 algorithms). 2. String Experiment problem (2 algorithms). 3. Uniqueness problem (3 algorithms). For these problems, your major task would be design, test, and select proper data and datasets, and report your testing results. Check the Project Requirements above. Code for generating testing datasets is usually required

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 } } } ////////////////

public class Fibonacci {

/** Returns the nth Fibonacci number (inefficiently). */ public static long fibonacciBad(int n) { if (n <= 1) return n; else return fibonacciBad(n-2) + fibonacciBad(n-1); }

/** Returns array containing the pair of Fibonacci numbers, F(n) and F(n-1). */ public static long[] fibonacciGood(int n) { if (n <= 1) { long[] answer = {n, 0}; return answer; } else { long[] temp = fibonacciGood(n - 1); // returns $\{ F_{n-1},\, F_{n-2} \}$ long[] answer = {temp[0] + temp[1], temp[0]}; // we want $\{ F_{n},\, F_{n-1} \}$ return answer; } }

/** Don't call this (infinite) version. */ public static int fibonacci(int n) { return fibonacci(n); // After all $F_n$ does equal $F_n$ }

public static void main(String[] args) { final int limit = 50;

System.out.println("The good..."); for (int n = 0; n < limit; n++) System.out.println(n + ": " + fibonacciGood(n)[0]);

System.out.println(); System.out.println("The bad..."); for (int n = 0; n < limit; n++) System.out.println(n + ": " + fibonacciBad(n));

// Even worse... fibonacci(10); // the infinite one }

}