Question

Correctly follow the described algorithm to complete the method
   * Add operation counts -
   * f(N) formula (show your work) -
   * O(N) reduction -
   */
   public static int[] algorithm1(int N)//f(N) = ; O(N) =
   {
       long opCount = 0;
       int[] arr = new int[N];
       /*
       * Use the following method to fill the array
       * For each position in the array, generate a random number between zero and N
       * - If N = 10, random numbers should be 0-9
       * Check if that random number is used in any previous position in the array
       * - If it is used anywhere else, generate a new number and try again
       * - If it is not used anywhere else, place it into the position and move forward
       */
       System.out.println("f(N) = [your answer]");
       System.out.println("O(N) = [your answer]");
       System.out.println("OpCount : "+opCount);
       return arr;
   }
   /*
  
   * Correctly follow the described algorithm to complete the method
   * Add operation counts
   * f(N) formula (show your work)
   * O(N) reduction
   */
   public static int[] algorithm2(int N)//f(N) = ; O(N) =
   {
       long opCount = 0;
       int[] arr = new int[N];
       boolean[] used = new boolean[N];
       /*
       * Use the following method to fill the array
       * For each position in the array, generate a random number between zero and N
       * - If N = 10, random numbers should be 0-9
       * Check if that used[random] is true
       * - If it is, generate a new number and try again
       * - If it is not, place it into the position, set used[random] = true, and move forward
       */
       System.out.println("f(N) = [your answer]");
       System.out.println("O(N) = [your answer]");
       System.out.println("OpCount : "+opCount);
       return arr;
   }
   /*
   * Correctly follow the described algorithm to complete the method
   * Add operation counts
   * f(N) formula (show your work)
   * O(N) reduction
   */
   public static int[] algorithm3(int N)//f(N) = ; O(N) =
   {
       long opCount = 0;
       int[] arr = new int[N];
       /*
       * Use the following method to fill the array
       * Fill the arr with zero to N-1 in order
       * Run a loop through each position
       * - For each position, swap that position and a randomly chosen position
       */
       System.out.println("f(N) = [your answer]");
       System.out.println("O(N) = [your answer]");
       System.out.println("OpCount : "+opCount);
       return arr;
   }
}

Answer 1

CODE

public static int[] algorithm1(int N)//f(N) = ; O(N) =

{

long opCount = 0;

int[] arr = new int[N];

/*

* Use the following method to fill the array

* For each position in the array, generate a random number between zero and N

* - If N = 10, random numbers should be 0-9

* Check if that random number is used in any previous position in the array

* - If it is used anywhere else, generate a new number and try again

* - If it is not used anywhere else, place it into the position and move forward

*/

for (int i=0; i<N; i++) {

int random = -1;

Random rand = new Random();

while (true) {

if (N == 10) {

random = rand.nextInt(10);

} else {

random = rand.nextInt(N);

}

opCount ++;

boolean found = false;

for (int j = 0; j<= i; j++) {

if (arr[j] == random) {

opCount ++;

found = true;

break;

}

}

if (!found) {

break;

}

}

}

System.out.println("f(N) = N^2 + C");

System.out.println("O(N) = O(N^2)");

System.out.println("OpCount : "+opCount);

return arr;

}

/*

* Correctly follow the described algorithm to complete the method

* Add operation counts

* f(N) formula (show your work)

* O(N) reduction

*/

public static int[] algorithm2(int N)//f(N) = ; O(N) =

{

long opCount = 0;

int[] arr = new int[N];

boolean[] used = new boolean[N];

/*

* Use the following method to fill the array

* For each position in the array, generate a random number between zero and N

* - If N = 10, random numbers should be 0-9

* Check if that used[random] is true

* - If it is, generate a new number and try again

* - If it is not, place it into the position, set used[random] = true, and move forward

*/

for (int i=0; i<N; i++) {

int random = -1;

Random rand = new Random();

while (true) {

if (N == 10) {

random = rand.nextInt(10);

} else {

random = rand.nextInt(N);

}

opCount ++;

if (!used[random]) {

break;

}

}

used[random] = true;

}

System.out.println("f(N) = N + c");

System.out.println("O(N) = O(N)");

System.out.println("OpCount : "+opCount);

return arr;

}

/*

* Correctly follow the described algorithm to complete the method

* Add operation counts

* f(N) formula (show your work)

* O(N) reduction

*/

public static int[] algorithm3(int N)//f(N) = ; O(N) =

{

long opCount = 0;

int[] arr = new int[N];

/*

* Use the following method to fill the array

* Fill the arr with zero to N-1 in order

* Run a loop through each position

* - For each position, swap that position and a randomly chosen position

*/

for (int i=0; i<N; i++) {

arr[i] = i;

opCount ++;

}

Random rand = new Random();

for (int i=0; i<N; i++) {

int random = rand.nextInt(N);

arr[i] = arr[random];

opCount ++;

}

System.out.println("f(N) = 2N + c");

System.out.println("O(N) = O(N)");

System.out.println("OpCount : "+opCount);

return arr;

}