Question

Take a look at the file GenericMethods.java. There are three methods you must implement: ·public static...

Take a look at the file GenericMethods.java.

There are three methods you must implement:

·public static <T extends Comparable<T>> int findMin(T[] arr): Iterate through the array to find the index of the smallest element in the array. If there are two elements with the smallest value, the method should return the index of the first one. The method should run in O(n).

·public static <T extends Comparable<T>> int findMinRecursive(T[] arr): Should behave just like findMin, but should be implemented recursively. Your method may not contain any while or for loops. Hint: the public findMinRecursive method should not, itself, be recursive. Instead, write an additional private helper method with additional parameters. This private helper method should be called from findMinRecursive. This must run in O(n) time.

·public static <T extends Comparable<T>> int binarySearch(T[] arr, T x): Implement a recursive binary search to find a value equal to x. Hint: The public binarySearch method, itself, should not be recursive. Instead, write an additional private helper method with additional parameters. This private helper method should be called from the public binarySearch method. This must run in O(log n) time. If the value is not found in the array, return -1. Else, return the index in the array where the value was found.

To test your code, you may compile and run GenericMethodTester.java. This tester class uses the types defined in the package shapes, which includes an interface Shape and concrete classes Rectangle, Square, and Circle. The Shape interface extends the Comparable interface, which means that the concrete classes all need to have a compareTo method. In this case, the differnt shapes are compared according to their area. Take a look at the code for these classes to make sure you understand how everything works. There is nothing you need to change in this package – it’s only here to test the GenericMethods.

Homework Answers

Answer #1

// GenericMethods.java
public class GenericMethods {
/*
   * method that iterate through the array to find the index of the smallest element in the array.
   * If there are two elements with the smallest value, the method should return the index of the first one
   * Input array is not null
   */
   public static <T extends Comparable<T>> int findMin(T[] arr)
   {
       int minIdx = 0; // set minIdx to -1
       // loop over the array
       for(int i=0;i<arr.length;i++)
       {
           // if minIdx is not set or ith element of array < minIdx element of array, set minIdx to i
           if(minIdx == -1 || (arr[i].compareTo(arr[minIdx]) < 0))
               minIdx = i;
       }
      
       return minIdx; // return the minimum index
   }
  
   /*
   * method that recursively finds the index of the smallest element in the array.
   * Input array is not null
   */
   public static <T extends Comparable<T>> int findMinRecursive(T[] arr)
   {
       return findMinRecursive(arr, 0);
   }
  
   /*
   * helper method that recursively returns the index of the smallest element of the array
   * It takes as input the array and the start index of the array
   */
   private static <T extends Comparable<T>> int findMinRecursive(T[] arr, int startIndex)
   {
       if(startIndex == arr.length-1) // if we reach the last index of the array, return the index
           return startIndex;
       else
       {
           // get the index of minimum element of the array starting with startIndex+1
           int index = findMinRecursive(arr, startIndex+1);
           if(arr[index].compareTo(arr[startIndex]) < 0) // if element at index < element at startIndex, return index
               return index;
           else
               return startIndex; // else return startIndex
       }
   }
  
   /*
   * method to return the index of x in the array using recursion.
   * return index if x is present in arr else return -1
   * the input array arr, is sorted is ascending order
   */
   public static <T extends Comparable<T>> int binarySearch(T[] arr, T x)
   {
       return binarySearch(arr, x, 0, arr.length-1);
   }
  
   /*
   * helper method to return the index of x if found else return -1
   */
   private static <T extends Comparable<T>> int binarySearch(T[] arr, T x, int low, int high)
   {
       if(low <= high) // if low <= high
       {
           int mid = (low+high)/2; // get the mid index
           // if element at mid = x, return mid
           if(arr[mid].compareTo(x) == 0)
               return mid;
           else if(arr[mid].compareTo(x) > 0) // element at mid > x then x if present must be in the left subarray
               return binarySearch(arr, x, low, mid-1);
           else                               // element at mid < x then x if present must be in the right subarray
               return binarySearch(arr, x, mid+1,high);
       }
      
       return -1; // x not found in the array
   }
}
//end of GenericMethods.java

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Complete the java code as per the comments public class Sorting {    ///////////////////////////////////////////////    //...
Complete the java code as per the comments public class Sorting {    ///////////////////////////////////////////////    // STEP 1 -- Make sorting methods generic    ///////////////////////////////////////////////       /**    * Re-orders the contents given array using the insertion sort algorithm.    *    * @param data The array to be sorted.    */    //TODO: Make me generic to work on any kind of Comparable data!    public static void insertionSort(int[] data)    {        int insert; // temporary...
Language: Java Topic: Deques Using the following variables/class: public class ArrayDeque<T> { /** * The initial...
Language: Java Topic: Deques Using the following variables/class: public class ArrayDeque<T> { /** * The initial capacity of the ArrayDeque. * * DO NOT MODIFY THIS VARIABLE. */ public static final int INITIAL_CAPACITY = 11; // Do not add new instance variables or modify existing ones. private T[] backingArray; private int front; private int size; Q1: write a method that constructs a new arrayDeque called "public ArrayDeque()" Q2: write a method called "public void addFirst(T data)" that adds an element...
Write code in java Implement a method to build an AVL tree out of a sorted...
Write code in java Implement a method to build an AVL tree out of a sorted (ascending order) array of unique integers, with the fastest possible big O running time. You may implement private helper methods as necessary. If your code builds a tree that is other than an AVL tree, you will not get any credit. If your code builds an AVL tree, but is not the fastest big O implementation, you will get at most 12 points. You...
can you please explain how to complete all methods in java ? thanks /* Note:   Do...
can you please explain how to complete all methods in java ? thanks /* Note:   Do not add any additional methods, attributes.         Do not modify the given part of the program.         Run your program against the provided Homework2Driver.java for requirements. */ /* Hint:   This Queue implementation will always dequeue from the first element of         the array i.e, elements[0]. Therefore, remember to shift all elements         toward front of the queue after each dequeue. */ public class QueueArray<T>...
JAVA please Arrays are a very powerful data structure with which you must become very familiar....
JAVA please Arrays are a very powerful data structure with which you must become very familiar. Arrays hold more than one object. The objects must be of the same type. If the array is an integer array then all the objects in the array must be integers. The object in the array is associated with an integer index which can be used to locate the object. The first object of the array has index 0. There are many problems where...
Use Java: Also: Please include screenshots if possible. Create a class called AbstractStackTest. Write an abstract...
Use Java: Also: Please include screenshots if possible. Create a class called AbstractStackTest. Write an abstract method called makeStack that returns a Stack of Strings. Use the Stack interface as the return type, not a specific implementation! Write a class named NodeStackTest that extends your AbstractStackTest class. Implement the makeStack method to return a NodeStack. Repeat parts 1 and 2 for the Queue interface and the NodeQueue implementation. Write a new stack implementation, ArrayStack. It should be generic and use...
Complete the following program. This program should do the following: 1. Creates a random integer in...
Complete the following program. This program should do the following: 1. Creates a random integer in the range 10 to 15 for variable: allThreads, to create a number of threads. 2. Creates a random integer for the size of an ArrayList: size. 3. Each thread obtains a smallest number of a segment of the array. To give qual sized segment to each thread we make the size of the array divisible by the number of threads: while(size%allThreads != 0)size++ 4....
Objectives:The focus of this assignment is to create and use a recursive method given a moderately...
Objectives:The focus of this assignment is to create and use a recursive method given a moderately difficult problem. Program Description: This project will alter the EmployeeManager to add a search feature, allowing the user to find an Employee by a substring of their name. This will be done by implementing the Rabin-Karp algorithm. A total of seven classes are required. Employee (From previous assignment) HourlyEmployee (From previous assignment) SalaryEmployee (From previous assignment) CommissionEmployee (From previous assignment) EmployeeManager (Altered from previous...
(Sure, take your time. would you like me to post this again?) Thanks in advance !...
(Sure, take your time. would you like me to post this again?) Thanks in advance ! Write the following methods in java class ARM that represent state information as well as functional blocks of the ARM platform. [Go through the following 5 classes then write methods for the instructions: mov, str, ldr, add in class ARM, finally, write a print method for ARM that can display the registers and the memory locations that have been used. (make sure to make...
Task Generics: GenericStack Class. Java and JUnit5 (Unit test) package Modul02; public class GenericStack<E> { private...
Task Generics: GenericStack Class. Java and JUnit5 (Unit test) package Modul02; public class GenericStack<E> { private java.util.ArrayList<E> list = new java.util.ArrayList<>(); public int size() { return list.size(); } public E peek() { return list.get(size() - 1); } public void push(E o) { list.add(o); } public E pop() { E o = list.get(size() - 1); list.remove(size() - 1); return o; } public boolean isEmpty() { return list.isEmpty(); } @Override public String toString() { return "stack: " + list.toString(); } } package...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT