Question

1. Copy the following java codes and compile

//// HighArray.java

//// HighArrayApp.java

Study carefully the design and implementation HighArray class and note the attributes and its methods.

  

2. Create findAll method which uses linear search algorithm to return all number of occurrences of specified element.

/**
* find an element from array and returns all number of occurrences of the specified element, returns 0 if the element does not exit.
*
* @param foundElement   Element to be found
*/
int findAll(int foundElement)

3. Modify the HighArray class to create a deleteAll method, which deletes a specified element from the array (if it exists, else return 0). Moving subsequent elements down one place in the array to fill the space vacated by the deleted element. The method should delete all the element occurrences.
   
   /**
   * Delete all element occurrences from array if found otherwise do nothing.
   *
   * @param deletedElement   Element to delete
   */
   int deleteAll(int deletedElement)

4. Modify HighArray class to create the following methods

long max()	Returns the maximum value in a
int maxIndex()	Returns the index of the maximum value
long min()	Returns the minimum value in a
int minIndex()	Returns the index of the minimum value
long range()	Calculates the range (max-min)
long sum()	Calculates the sum of elements of a
double avg()	Calculates the average of a
double std()	Calculates the standard deviation of a
long rank(int i)	Return the ith largest element of a
boolean checkOrdered()	Returns true if a is ordered otherwise returns false
boolean checkUnique()	Returns true if a has unique elements
void removeDuplicates()	Removes duplicates from a
void fillArrayRandom()	Fills a with Random numbers

  

5. Modify the binary search algorithm implemented in the search method of the HighArray class, to print a trace showing for each iteration of the search, the upper and lower limits of the search and the middle item selected in the binary split.
   
   The output might look something like this:
   
   Pass 1 left=0 right=9 pivot=4
   Pass 2 left=0 right =3 pivot =1
   Pass 3 left=2 right =3 pivot =2

6. Modify the HighArray class to implement the method specified below, which reads integer data from a file to fill the array. The first integer read from the file should indicate the number of integers contained in the file which can be read into the array.

/**
* Read integers into array from named file. First element in
* file is a count of number of integers contained in the file.
*
* @param fileName   name of file containing integer data
*/
void readIntFile(String fileName)

Note: Use the void insert(int value) method defined in the class to add each integer to the array as it is loaded from the file.

Here is a sample code to read data from file

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;

public class FileReaderSample {

    public static void main(String[] args) throws FileNotFoundException {

        Scanner in = new Scanner(System.in);

        System.out.println("Please enter file name");

      String s = in.nextLine();

        Scanner input = new Scanner(new File(s));

        int[] arr = new int[100];

        int i = 0;

        while (input.hasNextInt()) {

            int next = input.nextInt();

            arr[i] = next;

            i++;

        }// end while

        int nElems = i;

// Print the array contents

       System.out.println("Array Contents");

        for (i = 0; i < nElems; i++) {

            System.out.println(i + "\t" + arr[i]);

        }// end for

    }// end main

}// end class

7. Compare the performance between linearSearch, BinarySearch, InsertOrdered and InsertNotOrdered using System.nanoTime();

Fill the following table

         

Method	N= 100	N = 1000	N = 100000	N=1000000
InsertOrdered
Insert
LinearSearch(find method in HighArray)
BinarySearch

8. Create HiArray<T> class to store generic values,
9. Modify HighArray class and implement bubble sort, insertion sort and selection sort
10. Modify HighArray<T> class to implement bubble sort, insertion sort and selection sort

-------------------------------------------------------------------------------------------------

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

// highArray.java // demonstrates array class with high-level interface // to run this program: C>java HighArrayApp //////////////////////////////////////////////////////////////// class HighArray { private long[] a; // ref to array a private int nElems; // number of data items //----------------------------------------------------------- public HighArray(int max) // constructor { a = new long[max]; // create the array nElems = 0; // no items yet } //----------------------------------------------------------- public boolean find(long searchKey) { // find specified value int j; for(j=0; j<nElems; j++) // for each element, if(a[j] == searchKey) // found item? break; // exit loop before end if(j == nElems) // gone to end? return false; // yes, can't find it else return true; // no, found it } // end find() //----------------------------------------------------------- public void insert(long value) // put element into array { a[nElems] = value; // insert it nElems++; // increment size } //----------------------------------------------------------- public void insertOrdered(long value) // put element into array { int j; for(j=0; j<nElems; j++) // find where it goes if(a[j] > value) // (linear search) break; for(int k=nElems; k>j; k--) // move bigger ones up a[k] = a[k-1]; a[j] = value; // insert it nElems++; // increment size } // end insert() //----------------------------------------------------------- public boolean delete(long value) { int j; for(j=0; j<nElems; j++) // look for it if( value == a[j] ) break; if(j==nElems) // can't find it return false; else // found it { for(int k=j; k<nElems; k++) // move higher ones down a[k] = a[k+1]; nElems--; // decrement size return true; } } // end delete() //----------------------------------------------------------- public void display() // displays array contents { for(int j=0; j<nElems; j++) // for each element, System.out.print(a[j] + " "); // display it System.out.println(""); } //----------------------------------------------------------- public int binarySearch(int searchKey) { int left = 0, right = nElems-1; while (left <= right) { int pivot = (left + right) / 2; if (a[pivot] == searchKey) { return pivot; // found } else { if (a[pivot] < searchKey) left = pivot + 1; // search right else right = pivot - 1; // search left } } return -1; } public int size() { return nElems; } } // end class HighArray ////////////////////////////////////////////////////////////////

--------------------------------------------------------------------

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class HighArrayApp { public static void main(String[] args) { int maxSize = 100; // array size HighArray arr; // reference to array arr = new HighArray(maxSize); // create the array arr.insert(77); // insert 10 items arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); arr.display(); // display items int searchKey = 35; // search for item if( arr.find(searchKey) ) System.out.println("Found " + searchKey); else System.out.println("Can't find " + searchKey); arr.delete(00); // delete 3 items arr.delete(55); arr.delete(99); arr.display(); // display items again } // end main() } // end class HighArrayApp

------------------------------------------------------------------

I need the answer of 9 and 10

Answer 1

output:

below number of occurances of 55 is 3 and results also displaying after delteing all the occurances of 55

77 99 44 55 22 88 55 11 0 66 55 33
Can't find 35
number of occurances of 55 is 3
77 44 22 88 11 66 33

HighArray.java

class HighArray
{
private long[] a; // ref to array a
private int nElems; // number of data items
//-----------------------------------------------------------
public HighArray(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
//-----------------------------------------------------------
public boolean find(long searchKey)
{ // find specified value
int j;
for(j=0; j<nElems; j++) // for each element,
if(a[j] == searchKey) // found item?
break; // exit loop before end
if(j == nElems) // gone to end?
return false; // yes, can't find it
else
return true; // no, found it
} // end find()
//-----------------------------------------------------------
public int findAll(long searchKey)
{ // find specified value
   int n=0;
int j;
for(j=0; j<nElems; j++) // for each element,
if(a[j] == searchKey) // found item?
n++; // exit loop before end
return n; // no, found it
} // end find()
//-----------------------------------------------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
//-----------------------------------------------------------
public void insertOrdered(long value) // put element into array
{
int j;
for(j=0; j<nElems; j++) // find where it goes
if(a[j] > value) // (linear search)
break;
for(int k=nElems; k>j; k--) // move bigger ones up
a[k] = a[k-1];
a[j] = value; // insert it
nElems++; // increment size
} // end insert()
//-----------------------------------------------------------
public boolean delete(long value)
{
int j;
for(j=0; j<nElems; j++) // look for it
if( value == a[j] )
break;
if(j==nElems) // can't find it
return false;
else // found it
{
for(int k=j; k<nElems; k++) // move higher ones down
a[k] = a[k+1];
nElems--; // decrement size
return true;
}
} // end delete()
//-----------------------------------------------------------
public boolean deleteAll(long value)
{
   int i;
   for(i=0; i<nElems; i++){
   int j;
   for(j=0; j<nElems; j++) // look for it
   if( value == a[j] )
   break;
   if(j==nElems) // can't find it
   return false;
   else // found it
   {
   for(int k=j; k<nElems; k++) // move higher ones down
   a[k] = a[k+1];
   nElems--; // decrement size
   }
       }
   return true;
} // end delete()
//-----------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
//-----------------------------------------------------------
public int binarySearch(int searchKey) {
int left = 0, right = nElems-1;

while (left <= right) {
int pivot = (left + right) / 2;
if (a[pivot] == searchKey) {
return pivot; // found
} else {
if (a[pivot] < searchKey)
left = pivot + 1; // search right
else
right = pivot - 1; // search left
}
}
return -1;
}

public int size() {
return nElems;
}

} // end class HighArray

HighArrayApp.java

class HighArrayApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
HighArray arr; // reference to array
arr = new HighArray(maxSize); // create the array

arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(55);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(55);
arr.insert(33);

arr.display(); // display items

int searchKey = 35; // search for item
if( arr.find(searchKey) )
System.out.println("Found " + searchKey);
else
System.out.println("Can't find " + searchKey);
  
searchKey = 55; // search for item
System.out.println("number of occurances of " + searchKey + " is "+arr.findAll(searchKey));

arr.delete(00); // delete 3 items
arr.delete(55);
arr.delete(99);
arr.deleteAll(55);

arr.display(); // display items again
} // end main()
} // end class HighArrayApp