Java

here is the instructions

I need help with number 20

13. percentError: that takes a correct value and an estimated value and returns the percent error of the estimate: (predicted actual) / actual.
14. runAlgorithm: that takes the algorithm choice (number) and the size of the problem (N) as parameters and runs the desired algorithm (from Algorithms.java in the util folder) returning its result. An invalid algorithm choice results in a negative result. Note: If you use a switch statement, make sure you start your code on a new line after each case statement.
15. timeAlgorithm: that takes the algorithm number and the size of the algorithm and returns the time it takes to run the algorithm once. To determine the time it took to run an algorithm, you can use the System.currentTimeMillis() method before and after the algorithm call (Hint: You can use the runAlgorithm method you already wrote). Dont forget to convert from milliseconds to seconds before returning the result (Hint: There is a constant already made at the top called "MILLISECONDS_PER_SECOND"). Javas built-in garbage collector can run at any time so discourage it from interfering with your timing by forcing it to run just before you run your analysis (Hint: The System.gc() line does this for you).
16. At this point, you might want to experiment with the different algorithms. The BigOh.main() program takes user input and returns the timing results of your timeAlgorithm method. To run the program, browse in the Package Explorer and right-click on Lab03-->select Run As-->Java Application->BigOh (it may do this choice for you). You can select different algorithms and problem sizes and see what your timeAlgorithm method returns. Does it always return the same number for the same input?
17. robustTimeAlgorithm: because Java's garbage collector and code optimizer may run at inopportune moments when you are trying to measure the time it takes to run a method, we must run the method several times taking the minimum timing as the result. robustTimeAlgorithm takes the same parameters as timeAlgorithm but generates a robust estimate of the timing by returning the minimum time among 5 tries (Hint: You can use the timeAlgorithm method you already wrote).
18. bigOhFunc: that takes the algorithm number and size of the problem (N), and returns the big-oh function for each algorithm that you computed by hand. For example, if you think algorithm 1 has a big-oh of N^2, then calling bigOhFunc(1, 100) would return 10000. This function must be correct in order for Web-CAT to grade your lab.
19. estimateTiming: that takes a problem size (n1) and a timing (t1) and estimates the timing for a second problem size (n2). Remember: t2 = t1 * f(n2) / f(n1) (Hint: You can use the bigOhFunc you already wrote).
20. computePercentError: this method takes an algorithm choice and two problem sizes (n1 and n2) and returns the percent error between predicted time to run on problem size n2 and the empirical timing result for n2. Use robustTimeAlgorithm to get the empirical estimate for n1 and n2, estimateTiming for the estimated n2 (from empirical estimate for n1), and percentError to compute the difference between them.
21. After the previous methods are implemented and working correctly, you can run the JUnit test cases to see if your Big-Oh functions match up with your timing results. We provide one test case per algorithm named testAlgorithm# where # is the number of the algorithm. This test selects a small problem size (n1) that results in a timing of approximately 0.1 seconds, and a large problem size (n2) that results in a timing of approximately 0.5 seconds. It uses n1, t1, and n2 to estimate t2 and compares it to an empirical estimate of t2. If the error is small enough, it will pass.

here is the code

public class BigOh { private static final double MILLISECONDS_PER_SECOND = 1000.0; private Random rand;

/** * No-args constructor initializes the random using current time. */ public BigOh() { rand = new Random(); }

/** * Constructor takes an Random object to initialize the randomness of the * algorithms. * * @param rand * the random number generator */ public BigOh(Random rand) { this.rand = rand; }

/** * robustTimeAlgorithm returns the minimum time it takes to run the chosen * algorithm over 5 trials. * * @param choice * The index of the algorithm to use * @param n * The size of the problem * @return the time in seconds */ public double robustTimeAlgorithm(int choice, int n) { // TODO return -1.0; }

/** * timeAlgorithm returns the time it takes to run the algorithm once. * * @param choice * The index of the algorithm to use * @param n * The size of the problem * @return the time in seconds */ public double timeAlgorithm(int choice, int n) { // make sure that the garbage collector doesn't run // during timing. (Do this first.) System.gc();

// TODO return -1 * 2; }

/** * runAlgorithm selects the algorithm to run based on choice. * * @param choice * The number representing the algorithm choice * @param numElements * The size of the problem * @return The result of the algorithm */ public int runAlgorithm(int choice, int numElements) { // TODO (be sure to change return statement too) if(choice < 6) { return Algorithms.java(); } else { System.out.print(" invalid algorithm choice"); } if(choice > 0) { return Algorithms.java(); } else { System.out.print(" invalid algorithm choice"); } return Algorithms.java(); }

/** * bigOhFunc returns the Big-Oh function for algorithm and problem size * parameters. * * @param choice * The number representing the algorithm choice * @param n * The problem size. * @return The Big-Oh function for problem size, n. */ public double bigOhFunc(int choice, double n) { return -1 * 4; }

/** * estimateTiming takes an algorithm choice, problem size and timing, and * estimates the timing for a second problem size. * * @param choice * The number representing the algorithm choice * @param n1 * The first problem size * @param t1 * The first timing * @param n2 * The second problem size * @return The estimated timing for the second problem size */ public double estimateTiming(int choice, int n1, double t1, int n2) { // TODO return -1 * 8; }

/** * percentError returns the percent error in an estimate. * * @param correct * the correct value * @param estimate * the estimated value * @return the percent error */ public double percentError(double correct, double estimate) { // TODO return -1 * 16; }

/** * computePercentError takes an algorithm choice, and two problem sizes and * computes the error in estimating the timing of the second problem using * the timing of the first. * * @param choice * The number representing the algorithm choice * @param n1 * The first problem size * @param n2 * The second problem size * @return the percent error in estimating t2 given n1 and n2. */ public double computePercentError(int choice, int n1, int n2) { // TODO return -1 * 32; }

/** * Main method. * * @param args * Command line arguments not used. */ public static void main(String[] args) { int choice; int numElements = 0; Scanner keyInput = new Scanner(System.in); BigOh bo = new BigOh();

// run the fragments choice = menu(keyInput); while (choice != 7) { if (choice >= 1 && choice <= 6) { System.out.print("How many elements: "); numElements = keyInput.nextInt(); double time = bo.timeAlgorithm(choice, numElements); long milliseconds = (long) (time * MILLISECONDS_PER_SECOND); System.out.println("The time for alg" + choice + " with n=" + numElements + " is " + milliseconds + " ms. "); } choice = menu(keyInput); } System.out.println("Quitting"); }

/** * Prints the menu and prompts for input. * * @param keyInput * The scanner to read input * @return the number read */ public static int menu(Scanner keyInput) { int choice = -1;

System.out.println(); System.out.println(" 1. Method #1 "); System.out.println(" 2. Method #2 "); System.out.println(" 3. Method #3 "); System.out.println(" 4. Method #4 "); System.out.println(" 5. Method #5 "); System.out.println(" 6. Method #6 "); System.out.println(" 7. Quit "); System.out.print("Enter your choice: "); choice = keyInput.nextInt(); return choice; } }