3.4 Learning Objective: To compare the time for power) and powerFaster() to calculate I'. To determine why in some cases powerFaster() ia faster than power(). To understand that the time complexity of a solution to a problem can vary depending on the algorithm that is employed. Instructions: Modify H03_33.java by copying the power() method from class H03_32 to the H03_33 class. This question is not graded so you do not need to submit H03_33.java nor H03_33_Teat.java. Problem: Within the H03_33_Teat clasa, declare two private int instance variables named calls and callsFaster. Modify the test driver in H03_33_Test that your wrote for Ex. 3.3 to call both power) and powerFoster to calcu- late x' for z = 1, 2, 3, and for cach value of z, n = 0, 1, 2, ..., 10. Next, within power, write a statement as the first statement in the method which increments calls, before you check the base case. Within powerFaster(), write a statement as the first statement in the method which increments colleFaster, again, before you check the base case. After each method returns the computed power z' back to HO3_33_Test.run(), print the values of calls and callsFoster (I hope you have figured out that calls and callsFaster are counting the number of times cach method is called during the computation of z"). You should notice a difference between these two values for some values of n. Explain why the number of calls to power Faster() ia fewer than the number of calls to power') in some cases. 9.5 Learning Objective: To write a recursive method. Instructions: See the instructions in $1.1 for what to submit for grading. This is not a complete program. Name your clase H03_35 and save it in a file named H03_35.java. When you are done, copy H03_35.java to your asuriteid-h03 folder, i.e., to the same folder as the PDF. Problem: Write a recursive method public String reverse(String 3) that returns the reverse of s. For example, if 9 ia "Hello world" then the method shall return "dlrow olleH". Hint: The baze case occurs when the length of 5 is either 0 or 1. When the length is 0, it meana s is the empty atring "" and the reverse of the empty string is the empty string. When the length is 1, it means that you have a atring such as "A" and the reverse of "A" i "A" (or in general, the reverse of a string of length = 1 is the string itself). Otherwise, retrieve the first character of : at index 0, call the character c (hint: read about the String.charAt) method). Extract the substring t at indices 1....length() - 1 (read the Java API documentation for the String.sub- string() method). Then, call reverse(t) which will return a string, let's call the string revt. Concatenate c onto the end of revT and then return the newly formed string. Testing: We will be teating your method using our driver routine. For testing on your end, write your own test driver in a class named H03_35_Test. Within H03_35_Test.run() you should call reverse() on many different stringe, in- cluding the empty string, to verify your solution is correct. 4 Linear and Binary Search 4.1 Learning Objective: To write a recursive method which acarches a list for a key element. Instructions: See the instructions in 1.1 for what to submit for grading. This is not a complete program. Name your class H03_41 and save it in a file named H03_41.java. When you are done, copy H03_41.java to your asuriteid-h03 folder, i.e., to the same folder as the PDF Problem: We discussed in the lectures how to write a linear scarch algorithm using a for loop which iterates over cach element of a liat. Lincar acorch can also be implemented recursively. For this exercise, write a recursive method public int recLinear Search(ArrayLiat pliat, String pkey, int pBeginIdx, int pEndIdx) that searches pList elementa pBeginidr up to and including pendidr for pKey and returns the index of pKey in pList if found or -1 if not found. Hint: The baze case is reached when p Beginidr is greater than pendid (what does this mean?). Otherwise, check to see if the element at pBeginidr is equal to pkey. If it is, then return pBeginidz. If it is not, then make a recursive method call which will search pList at elementa pBeginidz + 1 to pEndidz. Testing: We will be testing your method using our driver routine. For testing on your end, write your own testing driver in & cls22 named H03_41_Teat. For testing, your method will be called in this manner to search the entire liet: ArrayList pliat, String pkey, int pBeginIdx, int pEndIdx) that searches pList elementa pBeginidr up to and including pendidr for pKey and returns the index of pKey in pList if found or -1 if not found. Hint: The baze case is reached when p Beginidr is greater than pendid (what does this mean?). Otherwise, check to see if the element at pBeginidr is equal to pkey. If it is, then return pBeginidz. If it is not, then make a recursive method call which will search pList at elementa pBeginidz + 1 to pEndidz. Testing: We will be testing your method using our driver routine. For testing on your end, write your own testing driver in & cls22 named H03_41_Teat. For testing, your method will be called in this manner to search the entire liet: ArrayList