Implement a program to find the number of comparison using sequentialSearch and binarySearch algorithms as follows:

Suppose list is an array with a number of elements.

1. Use a random number generator to fill list;
2. Use a sorting algorithm to sort list;
3. Search list for some items as follows:
4. Use the binary search algorithm to search list (please work on SearchSortAlgorithms.java and modify the algorithm to count the number of comparisons)
5. Use the sequential search algorithm to search list (please work on SearchSortAlgorithms.java and modify the algorithm to count the number of comparisons)
6. Print the number of comparison in step 3(a) and 3(b). If the item is found in the list, print its position.
7. Repeat steps 1-4 with different array sizes (say 16, 64, 256, 1024, 4096, 16384) to record the number of comparisons for the binary search algorithm and sequential search algorithm. Based on the recorded results, explain the reason why you obtain such results (you may graph the results to support your investigation).

(Note: please download Problem51.zip and use the java code provided in the assignment folder)

Java Code Provided in Assignment Folder

import java.util.*;

public class Problem51 { static Scanner console = new Scanner(System.in);

final static int SIZE = 1000;

public static void main(String[] args) { Integer[] intList = new Integer[SIZE];

SearchSortAlgorithms intSearchObject = new SearchSortAlgorithms(); }

//Generic interface that describes various searching and sorting //algorithms. Note that the type parameter is unbounded. However, //for these algorithms to work correctly, the data objects must //be compared using the method compareTo and equals. //In other words, the classes implementing the list objects //must implement the interface Comparable. The type parameter T //is unbounded because we would like to use these algorithms to //work on an array of objects as well as on objects of the classes //UnorderedArrayList and OrderedArrayList.

public interface SearchSortADT { public int seqSearch(T[] list, int start, int length, T searchItem); //Sequantial search algorithm. //Postcondition: If searchItem is found in the list, // it returns the location of searchItem; // otherwise it returns -1.

public int binarySearch(T[] list, int start, int length, T searchItem); //Binary search algorithm. //Precondition: The list must be sorted. //Postcondition: If searchItem is found in the list, // it returns the location of searchItem; // otherwise it returns -1.

public void bubbleSort(T list[], int length); //Bubble sort algorithm. //Postcondition: list objects are in ascending order.

public void selectionSort(T[] list, int length); //Selection sort algorithm. //Postcondition: list objects are in ascending order.

public void insertionSort(T[] list, int length); //Insertion sort algorithm. //Postcondition: list objects are in ascending order.

public void quickSort(T[] list, int length); //Quick sort algorithm. //Postcondition: list objects are in ascending order.

public void heapSort(T[] list, int length); //Heap sort algorithm. //Postcondition: list objects are in ascending order. }

//Generic interface that describes various searching and sorting //algorithms. Note that the type parameter is unbounded. However, //for these algorithms to work correctly, the data objects must //be compared using the method compareTo and equals. //In other words, the classes implementing the list objects //must implement the interface Comparable. The type parameter T //is unbounded because we would like to use these algorithms to //work on an array of objects as well as on objects of the classes //UnorderedArrayList and OrderedArrayList.

public class SearchSortAlgorithms implements SearchSortADT { private int comparisons;

public int noOfComparisons() { //your method here }

public void initializeNoOfComparisons() { //your method here }

//Sequantial search algorithm. //Postcondition: If searchItem is found in the list, // it returns the location of searchItem; // otherwise it returns -1. public int seqSearch(T[] list, int start, int length, T searchItem) { int loc; boolean found = false;

for (loc = start; loc < length; loc++) { if (list[loc].equals(searchItem)) { found = true; break; } }

if (found) return loc; else return -1; } //end seqSearch

//Binary search algorithm. //Precondition: The list must be sorted. //Postcondition: If searchItem is found in the list, // it returns the location of searchItem; // otherwise it returns -1. public int binarySearch(T[] list, int start, int length, T searchItem) { int first = start; int last = length - 1; int mid = -1;

boolean found = false;

while (first <= last && !found) { mid = (first + last) / 2;

Comparable compElem = (Comparable) list[mid];

if (compElem.compareTo(searchItem) == 0) found = true; else { if (compElem.compareTo(searchItem) > 0) last = mid - 1; else first = mid + 1; } }

if (found) return mid; else return -1; }//end binarySearch

public int binSeqSearch15(T[] list, int start, int length, T searchItem) { int first = 0; int last = length - 1; int mid = -1;

boolean found = false;

while (last - first > 15 && !found) { mid = (first + last) / 2;

Comparable compElem = (Comparable) list[mid];

comparisons++;

if (compElem.compareTo(searchItem) ==0) found = true; else { if (compElem.compareTo(searchItem) > 0) last = mid - 1; else first = mid + 1; } }

if (found) return mid; else return seqSearch(list, first, last, searchItem); }

//Bubble sort algorithm. //Postcondition: list objects are in ascending order. public void bubbleSort(T list[], int length) { for (int iteration = 1; iteration < length; iteration++) { for (int index = 0; index < length - iteration; index++) { Comparable compElem = (Comparable) list[index];

if (compElem.compareTo(list[index + 1]) > 0) { T temp = list[index]; list[index] = list[index + 1]; list[index + 1] = temp; } } } }//end bubble sort

//Selection sort algorithm. //Postcondition: list objects are in ascending order. public void selectionSort(T[] list, int length) { for (int index = 0; index < length - 1; index++) { int minIndex = minLocation(list, index, length - 1);

swap(list, index, minIndex); } }//end selectionSort

//Method to determine the index of the smallest item in //list between the indices first and last.. //This method is used by the selection sort algorithm. //Postcondition: Returns the position of the smallest // item.in the list. private int minLocation(T[] list, int first, int last) { int minIndex = first;

for (int loc = first + 1; loc <= last; loc++) { Comparable compElem = (Comparable) list[loc];

if (compElem.compareTo(list[minIndex]) < 0) minIndex = loc; }

return minIndex; }//end minLocation

//Method to swap the elements of the list speified by //the parameters first and last.. //This method is used by the algorithms selection sort //and quick sort.. //Postcondition: list[first] and list[second are //swapped.. private void swap(T[] list, int first, int second) { T temp;

temp = list[first]; list[first] = list[second]; list[second] = temp; }//end swap

//Insertion sort algorithm. //Postcondition: list objects are in ascending order. public void insertionSort(T[] list, int length) { for (int firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder ++) { Comparable compElem = (Comparable) list[firstOutOfOrder];

if (compElem.compareTo(list[firstOutOfOrder - 1]) < 0) { Comparable temp = (Comparable) list[firstOutOfOrder];

int location = firstOutOfOrder;

do { list[location] = list[location - 1]; location--; } while (location > 0 && temp.compareTo(list[location - 1]) < 0);

list[location] = (T) temp; } } }//end insertionSort

//Quick sort algorithm. //Postcondition: list objects are in ascending order. public void quickSort(T[] list, int length) { recQuickSort(list, 0, length - 1); }//end quickSort

//Method to partition the list between first and last. //The pivot is choosen as the middle element of the list. //This method is used by the recQuickSort method. //Postcondition: After rearranging the elements, // according to the pivot, list elements // between first and pivot location - 1, // are smaller the the pivot and list // elements between pivot location + 1 and // last are greater than or equal to pivot. // The position of the pivot is also // returned. private int partition(T[] list, int first, int last) { T pivot;

int smallIndex;

swap(list, first, (first + last) / 2);

pivot = list[first]; smallIndex = first;

for (int index = first + 1; index <= last; index++) { Comparable compElem = (Comparable) list[index];

if (compElem.compareTo(pivot) < 0) { smallIndex++; swap(list, smallIndex, index); } }

swap(list, first, smallIndex);

return smallIndex; }//end partition

//Method to sort the elements of list between first //and last using quick sort algorithm, //Postcondition: list elements between first and last // are in ascending order. private void recQuickSort(T[] list, int first, int last) { if (first < last) { int pivotLocation = partition(list, first, last); recQuickSort(list, first, pivotLocation - 1); recQuickSort(list, pivotLocation + 1, last); } }//end recQuickSort

//Heap sort algorithm. //Postcondition: list objects are in ascending order. public void heapSort(T[] list, int length) { buildHeap(list, length);

for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0; lastOutOfOrder--) { T temp = list[lastOutOfOrder]; list[lastOutOfOrder] = list[0]; list[0] = temp; heapify(list, 0, lastOutOfOrder - 1); }//end for }//end heapSort

//Method to the restore the heap in the list between //low and high. //This method is used by the heap sort algorithm and //the method buildHeap. //Postcondition: list elemets between low and high are // in a heap. private void heapify(T[] list, int low, int high) { int largeIndex;

Comparable temp = (Comparable) list[low]; //copy the root //node of //the subtree

largeIndex = 2 * low + 1; //index of the left child

while (largeIndex <= high) { if (largeIndex < high) { Comparable compElem = (Comparable) list[largeIndex];

if (compElem.compareTo(list[largeIndex + 1]) < 0) largeIndex = largeIndex + 1; //index of the //largest child }

if (temp.compareTo(list[largeIndex]) > 0) //subtree //is already in a heap break; else { list[low] = list[largeIndex]; //move the larger //child to the root low = largeIndex; //go to the subtree to //restore the heap largeIndex = 2 * low + 1; } }//end while

list[low] = (T) temp; //insert temp into the tree, //that is, list }//end heapify

//Method to convert an array into a heap. //This method is used by the heap sort algorithm //Postcondition: list elements are in a heap. private void buildHeap(T[] list, int length) { for (int index = length / 2 - 1; index >= 0; index--) heapify(list, index, length - 1); }//end buildHeap }

Problem 5.2

Two stacks are the same if they have the same size and their elements at the corresponding positions are the same. Add the method equalStack to Class StackClass that takes as a parameter a StackClass object, say otherStack and return true if the stack is the same as otherStack. Also write the definition of method equalStack and a program to test your method. In StackClass.java, please finish method - public boolean equalStack(StackClass otherStack) and testing main program - Problem52.java. (Download Problem52.zip for this problem)

CODE GIVEN:

public class Problem52 { public static void main(String[] args) { StackClass intStack = new StackClass(50); StackClass tempStack = new StackClass(50); // Please add your code here! }

public class StackClass implements StackADT { private int maxStackSize; //variable to store the //maximum stack size private int stackTop; //variable to point to //the top of the stack private T[] list; //array of reference variables

//Default constructor // an array of size 100 to implement the stack. //Postcondition: The variable list contains the base // address of the array, stackTop = 0, // and maxStackSize = 100. public StackClass() { maxStackSize = 100; stackTop = 0; //set stackTop to 0 list = (T[]) new Object[maxStackSize]; //implement the array }//end default constructor

//Constructor with a parameter //implement an array of size stackSize to implement the //stack. //Postcondition: The variable list contains the base // address of the array, stackTop = 0, // and maxStackSize = stackSize. public StackClass(int stackSize) { if (stackSize <= 0) { System.err.println("The size of the array to " + "implement the stack must be " + "positive."); System.err.println("Creating an array of size 100.");

maxStackSize = 100; } else maxStackSize = stackSize; //set the stack size to //the value specified by //the parameter stackSize stackTop = 0; //set stackTop to 0 list = (T[]) new Object[maxStackSize]; //implement the array }//end constructor

//Method to initialize the stack to an empty state. //Postcondition: stackTop = 0 public void initializeStack() { for (int i = 0; i < stackTop; i++) list[i] = null;

stackTop = 0; }//end initializeStack

//Method to determine whether the stack is empty. //Postcondition: Returns true if the stack is empty; // otherwise, returns false. public boolean isEmptyStack() { return (stackTop == 0); }//end isEmptyStack

//Method to determine whether the stack is full. //Postcondition: Returns true if the stack is full; // otherwise, returns false. public boolean isFullStack() { return (stackTop == maxStackSize); }//end isFullStack

//Method to add newItem to the stack. //Precondition: The stack exists and is not full. //Postcondition: The stack is changed and newItem // is added to the top of stack. // If the stack is full, the method // throws StackOverflowException public void push(T newItem) throws StackOverflowException { if (isFullStack()) throw new StackOverflowException();

list[stackTop] = newItem; //add newItem at the //top of the stack stackTop++; //increment stackTop }//end push

//Method to return a reference to the top element of //the stack. //Precondition: The stack exists and is not empty. //Postcondition: If the stack is empty, the method // throws StackUnderflowException; // otherwise, a reference to the top // element of the stack is returned. public T peek() throws StackUnderflowException { if (isEmptyStack()) throw new StackUnderflowException();

return (T) list[stackTop - 1]; }//end peek

//Method to remove the top element of the stack. //Precondition: The stack exists and is not empty. //Postcondition: The stack is changed and the top // element is removed from the stack. // If the stack is empty, the method // throws StackUnderflowException public void pop() throws StackUnderflowException { if (isEmptyStack()) throw new StackUnderflowException();

stackTop--; //decrement stackTop list[stackTop] = null; }//end pop

public boolean equalStack(StackClass otherStack) { // Please add your code here!

} //end equalStack }

public class StackException extends RuntimeException { public StackException() { }

public StackException(String msg) { super(msg); } }

public class StackOverflowException extends StackException { public StackOverflowException() { super("Stack Overflow"); }

public StackOverflowException(String msg) { super(msg); } } public class StackUnderflowException extends StackException { public StackUnderflowException() { super("Stack Underflow"); }

public StackUnderflowException(String msg) { super(msg); } }

Problem 5.3

1. Add the following operation to the Class StackClass:

void reverseStack(StackClass otherStack);

This operation copies the elements of a stack in reverse order onto another stack.

Consider the following statements:

StackClass stack1;

StackClass stack2;

The statement

stack1.reverseStack(stack2);

copies the elements of stack1 onto stack2 in the reverse order. That is, the top element of stack1 is the bottom element of stack2, and so on. The old contents of stack2 are destroyed and stack1 is unchanged.

1. Add the definition of the method to implement the operation reverseStack and a program to test the method reverseStack.

In StackClass.java, please finish method - public void reverseStack(StackClass otherStack) and testing main program - Problem53.java. (Download Problem53.zip for this problem).

CODE GIVEN:

public class Problem53 { public static void main(String[] args) { StackClass intStack = new StackClass(); StackClass tempStack = new StackClass();

// Please add your code here! } }

public interface StackADT { public void initializeStack(); //Method to initialize the stack to an empty state.

public boolean isEmptyStack(); //Method to determine whether the stack is empty. //Postcondition: Returns true if the stack is empty; // otherwise, returns false.

public boolean isFullStack(); //Method to determine whether the stack is full. //Postcondition: Returns true if the stack is full; // otherwise, returns false.

public void push(T newItem) throws StackOverflowException; //Method to add newItem to the stack. //Precondition: The stack exists and is not full. //Postcondition: The stack is changed and newItem // is added to the top of stack. // If the stack is full, the method // throws StackOverflowException.

public T peek() throws StackUnderflowException; //Method to return a reference to the top element of //the stack. //Precondition: The stack exists and is not empty. //Postcondition: If the stack is empty, the method // throws StackUnderflowException; // otherwise, a reference to the top // element of the stack is returned.

public void pop() throws StackUnderflowException; //Method to remove the top element of the stack. //Precondition: The stack exists and is not empty. //Postcondition: The stack is changed and the top // element is removed from the stack. // If the stack is empty, the method // throws StackUnderflowException. }

public class StackClass implements StackADT { private int maxStackSize; //variable to store the //maximum stack size private int stackTop; //variable to point to //the top of the stack private T[] list; //array of reference variables

//Default constructor //an array of size 100 to implement the stack. //Postcondition: The variable list contains the base // address of the array, stackTop = 0, // and maxStackSize = 100. public StackClass() { maxStackSize = 100; stackTop = 0; //set stackTop to 0 list = (T[]) new Object[maxStackSize]; //writethe array }//end default constructor

//Constructor with a parameter //write array of size stackSize to implement the //stack. //Postcondition: The variable list contains the base // address of the array, stackTop = 0, // and maxStackSize = stackSize. public StackClass(int stackSize) { if (stackSize <= 0) { System.err.println("The size of the array to " + "implement the stack must be " + "positive."); System.err.println("Creating an array of size 100.");

maxStackSize = 100; } else maxStackSize = stackSize; //set the stack size to //the value specified by //the parameter stackSize stackTop = 0; //set stackTop to 0 list = (T[]) new Object[maxStackSize]; //write array }//end constructor

//Method to initialize the stack to an empty state. //Postcondition: stackTop = 0 public void initializeStack() { for (int i = 0; i < stackTop; i++) list[i] = null;

stackTop = 0; }//end initializeStack

//Method to determine whether the stack is empty. //Postcondition: Returns true if the stack is empty; // otherwise, returns false. public boolean isEmptyStack() { return (stackTop == 0); }//end isEmptyStack

//Method to determine whether the stack is full. //Postcondition: Returns true if the stack is full; // otherwise, returns false. public boolean isFullStack() { return (stackTop == maxStackSize); }//end isFullStack

//Method to add newItem to the stack. //Precondition: The stack exists and is not full. //Postcondition: The stack is changed and newItem // is added to the top of stack. // If the stack is full, the method // throws StackOverflowException public void push(T newItem) throws StackOverflowException { if (isFullStack()) throw new StackOverflowException();

list[stackTop] = newItem; //add newItem at the //top of the stack stackTop++; //increment stackTop }//end push

//Method to return a reference to the top element of //the stack. //Precondition: The stack exists and is not empty. //Postcondition: If the stack is empty, the method // throws StackUnderflowException; // otherwise, a reference to the top // element of the stack is returned. public T peek() throws StackUnderflowException { if (isEmptyStack()) throw new StackUnderflowException();

return (T) list[stackTop - 1]; }//end peek

//Method to remove the top element of the stack. //Precondition: The stack exists and is not empty. //Postcondition: The stack is changed and the top // element is removed from the stack. // If the stack is empty, the method // throws StackUnderflowException public void pop() throws StackUnderflowException { if (isEmptyStack()) throw new StackUnderflowException();

stackTop--; //decrement stackTop list[stackTop] = null; }//end pop

public void reverseStack(StackClass otherStack) { // your method here } //end reverseStack }

public class StackException extends RuntimeException { public StackException() { }

public StackException(String msg) { super(msg); } }

public class StackOverflowException extends StackException { public StackOverflowException() { super("Stack Overflow"); }

public StackOverflowException(String msg) { super(msg); } }

public class StackUnderflowException extends StackException { public StackUnderflowException() { super("Stack Underflow"); }

public StackUnderflowException(String msg) { super(msg); } }