Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Download: https://solutionzip.com/downloads/homework-7/
- 1. (3 points) Exercise 9, page 205. Just write out the recursive method gcd; you arenβt
- required to write or run a test program.
- 2. (3 points) Exercise 17, page 209.
- 3. (4 points) Draw a recursion tree for the call binarySearch(5, 0, 8). Use the
- recursive version of the method found on p. 174 of your textbook.
- Label each node of the recursion tree with the indices of the subarray being searched
- (given by the parameters first and last). Assume the array values contains the
- following:
- [-2 1 3 5 7 12 18 20 23]
- 4. (2 points) How many total calls are made to binarySearch? What is the depth of
- recursion for this call? Here depth of recursion = longest path in the recursion tree.
- 5. (4 points) In class we saw two ways to formulate the choose function, one with two
- recursive calls, and another needing only one recursive calls. Write both versions (call
- them choose1 and choose2, for the number of recursive calls) as static methods in a
- class along with a main method for testing. For both, be sure to check the validity of the
- arguments and throw IllegalArgumentException if invalid. Your test will prompt
- the user for n and m and return the results of running both versions of choose.
- Record the results of testing your code with arguments (4,2) and (6,4). Then test them for
- (15,8) and (35,20). On some computers the last call may take several minutes. If any of
- your answers are negative, explain why.
- 6. (2 points) Java provides the primitive type long for integral computations which cannot
- be expressed using int. Long integers hold values from more than 92 quintillion to less
- than -92 quintillion. Rewrite each choose method so that it returns value of type long.
- Rerun each computation from the previous problem and record the results.
- 7. (2 points) How many total calls are made to choose2(6,4)? What is the depth of
- recursion for this call? Use a recursion tree to answer this question (extra credit for
- turning in a drawing of the tree).
- 8. (4 points) For each of the algorithms gcd, contains, binarySearch,
- and choose2, say if they are tail recursive or not.
- Download: https://solutionzip.com/downloads/homework-7/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement