LANGUAGE: JAVA

PLEASE USE THE CODE BELOW AS HELP WITH THE FIRST PROBLEM PLEASE FOLLOW THIS FORMAT

Problem 1. Design a program that allows you to experiment with different sort algorithms. This program should allow you to easily plug-in new sorting algorithms and compare them. For this homework, you will work with insertion, selection and bubble sorts (more sorts will be added later) Assume that input data is generated randomly and stored in a text file. You will experiment with your program in two steps: Step 1: Experimenting with a prototype data (integers from 1 to 10) to ensure that your implementation works correctly and the results match expectations. The results must be reported in a table format (not generated by the program, but collected manually from multiple program runs) in the a Word document as follows: ordered dataset reverse order random order comparisons exchanges comparisons exchanges comparisons exchanges buble sort selection sort insertion sort Step 2: Experimenting with large data sets of 2000 elements. The results must be reported in the same table format. In addition, in the report, explain the empirical results generated by your program comparing them to the known theoretical results paying special attention to any discrepancies which must be clearly explained. Must submit for grading: the java code ONLY and the report (Word document) containing your empirical results as explained above and MOST IMPORTANTLY the analysis of this results - what do they suggest, are they consistent with expected (theoretical) results, why - explain the algorithms, how the algorithms compare based on YOUR results. Also report everything that deviates from expectations and explain it. Note that this report is 95% of the grade the code is supplemental necessity to allow you to write the report. Problem 2. Study, program, and compare the efficiencies of the following recursive algorithms: Recursive binary search Computing the factorial of N Computing the N-th Fibonacci number. Must submit the tree of recursive calls for each program, the Big-O function with an explanation for each program, PLUS the java code and example runs to demonstrate the correctness of the implementation. public class Sorts PrepSelection { public static void main (String [] args) { System.out.println(" ==-=- System.out.println ("Testing selection sort: "); int[] arraylSelection = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10); int[] array2Selection = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1); int[] array3Selection = {1, 3, 2, 5, 4, 7, 9, 6, 8, 10}; System.out.println(" --- best case ---"); selectionsort (array1 Selection); System.out.println(" --- worst case ---"); selectionSort (array2 Selection); System.out.println(" --- avarage case ---"); selectionSort (array3 Selection); System.out.println(" ----- } public static void selectionSort (int[] array) { int temp, min, exchanges - 0, comparisons = 0; int numberof Items - array.length; for (int pass=0; pass !- numberOfItems - 1; pass++) min - pass; for (int index - pass+l; index != numberOfItems; index++) { comparisons++; if (array[index]