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.

////////////////////////////////

import java.util.Arrays;

class Uniqueness {

/** Returns true if there are no duplicate elements in the array. */ public static boolean unique1(int[] data) { int n = data.length; for (int j=0; j < n-1; j++) for (int k=j+1; k < n; k++) if (data[j] == data[k]) return false; // found duplicate pair return true; // if we reach this, elements are unique }

/** Returns true if there are no duplicate elements in the array. */ public static boolean unique2(int[] data) { int n = data.length; int[] temp = Arrays.copyOf(data, n); // make copy of data Arrays.sort(temp); // and sort the copy for (int j=0; j < n-1; j++) if (temp[j] == temp[j+1]) // check neighboring entries return false; // found duplicate pair return true; // if we reach this, elements are unique }

} ///////////////////////////////////////

public class Unique3 {

/** Returns true if there are no duplicate values from data[low] through data[high].*/ public static boolean unique3(int[] data, int low, int high) { if (low >= high) return true; // at most one item else if (!unique3(data, low, high-1)) return false; // duplicate in first n-1 else if (!unique3(data, low+1, high)) return false; // duplicate in last n-1 else return (data[low] != data[high]); // do first and last differ? } } ///////////////////////////////////

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"); } } /////////////////////////////////

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 }

}