x^{0} = 1 x^{y} = x*x^{y-1} for all y > 1File Power.java contains a main program that reads in integers base and exp and calls method power to compute base^{exp}. Fill in the code for power to make it a recursive method to do the power computation.
Print Power.java.
fib(0) = 0 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2) n>1For example, the first eight elements of the sequence are 0,1,1,2,3,5,8,13.
Because the Fibonacci sequence is defined recursively, it is natural to write a recursive method to determine the nth number in the sequence. File Fib.java contains the skeleton for a program that reads an integer n from and computes and prints the n^{th} Fibonacci number. Save this file to your directory. Following the specification above, fill in the code for method fib so that it recursively computes and returns the nth number in the sequence.
Print Fib.java.
Here is an example for converting 30_{10} to base 4:
quotient remainder -------- --------- 30/4 = 7 2 7/4 = 1 3 1/4 = 0 1The answer is read bottom to top in the remainder column, so 30_{10} = 132_{4}.
Think about how this is recursive in nature: If you want to convert x (30 in our example) to base b (4 in our example), the rightmost digit is the remainder x % b. To get the rest of the digits, you perform the same process on what is left; that is, you convert the quotient x / b to base b. If x / b is 0, there is no rest; x is a single base b digit and that digit is x % b (which also is just x).
The file BaseConversion.java contains the shell of a method convert to do the base conversion and a main method to test the conversion. Note that the convert method returns a string representing the base b number. This means that in the base case, when the remainder is what is to be returned, it must be converted to a String object by concatenating it with a null string. Similarly, in the recursive case the result of the recursive call will be concatenated with the remainder.
Fill in the code for convert and the call in the main method. Here is some data to test your program on:
Print BaseConversion.java.
The file Sorting.java contains the a skeleton of the MergeSort (as well as the other sorts). The file TimeSorts.java is the familiar driver for these sorting routines. Download them both to your directory. Fill in the code to complete the mergeSort (as directed by comments), and add an option to TimeSorts that allows you to execute and time MergeSorts.
Make sure that your MergeSort is working by printing out a sorted list (Option 1 on the menu).
Download the file SortingCompare2.ods to your directory. Open this file using OpenOffice Spreadsheet. You will see a worksheet similar to lab4. Conduct sorts on the appropriate list sizes and record your data. What does the chart tell you about the efficiency of MergeSort relative to Selection Sort and Insertion Sort? (write your answer in the spreadsheet). Save the worksheet and print a copy of your graph.