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
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...
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...
(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...
Compile and execute the application. You will discover that is has a bug in it -...
Compile and execute the application. You will discover that is has a bug in it - the filled checkbox has no effect - filled shapes are not drawn. Your first task is to debug the starter application so that it correctly draws filled shapes. The bug can be corrected with three characters at one location in the code. Java 2D introduces many new capabilities for creating unique and impressive graphics. We’ll add a small subset of these features to the...
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
question : Take the recursive Java program Levenshtein.java and convert it to the equivalent C program....
question : Take the recursive Java program Levenshtein.java and convert it to the equivalent C program. Tip: You have explicit permission to copy/paste the main method for this question, replacing instances of System.out.println with printf, where appropriate. You can get the assert function from assert.h. Try running the Java program on the CS macOS machines. You can compile and run the program following the instructions discussed in class. Assertions are disabled by default. You can enable assertions by running java...
this is the book name. Data Structures and Abstractions with Java 1) Description: The sample programs...
this is the book name. Data Structures and Abstractions with Java 1) Description: The sample programs in Chapter 1 of your textbook are not complete. They are used for illustration purpose only. The implementation of Listing 1-1 on page 39 is explained in Chapter 2. And, in order to see the result of using it, we will need the following set of files: i. BagInteface.java – the specification only. ii. ArrayBag.java – the implementation of BagInerface.java. iii. ArrayBagDemo.java – a...
Goal:   Manage the inventory of objects sold in an online or brick and mortar store. If...
Goal:   Manage the inventory of objects sold in an online or brick and mortar store. If you can't implement all of the features of Project described in this document, implement what you can. Start by implementing the StockItem class, and its derived classes. Then add in the InventoryManager class later. In each case, the test files must be in separate classes. UML Diagram: Use Violet or other drawing software to draw the UML diagrams of each class that you use...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally. 1. Theory. A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps. You can test if...
Complete this in C++ and explain what is being done. 1      Introduction The functions in the...
Complete this in C++ and explain what is being done. 1      Introduction The functions in the following subsections can all go in one big file called pointerpractice.cpp. 1.1     Basics Write a function, int square 1(int∗ p), that takes a pointer to an int and returns the square of the int that it points to. Write a function, void square 2(int∗ p), that takes a pointer to an int and replaces that int (the one pointed to by p) with its...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT