Lab 12
Logistics
- Due: on Thursday, November 17th anywhere on earth (6am Friday). (Penalties from the syllabus apply if you turn it in any later.)
- Submission instructions: you have two options. The first option is to demonstrate the execution of your lab to your TA during your assigned lab section on Thursday. The second option is to submit your Java file(s) on D2L.
Learning outcomes
- Understand binary search
- Write a recursive algorithm in Java
Assignment
In this assignment, you will complete the binarySearch
methods and the recursiveMultiply
methods in the starter code file. The main
method of the starter code has some tests so that you can ensure that your implementations are correct. You do not need to modify the main
method.
Binary search
The main
method of the starter code calls a two-parameter binarySearch
method. In this method, you should call your own private binarySearch
method, which will have a different method signature than the public binarySearch
. It should return true if the target
integer is in data
and false otherwise. You can assume that data
is already sorted. You are not required to check the validity of the input.
In addition to returning a boolean, your binarySearch
method should print out the total number of calls made to the method.
You can start by copying the book’s binarySearch
method if you want. However, you will need to add code to print out the number of calls to the method.
Recursive multiply
This is based on problem C-5.13 from the book.
Complete the recursiveMultiply
method so that it returns the product of two positive integers m
and n
using only addition and subtraction. You do not need to check that m
and n
are positive, but you can assume that they always are.
Sample output
Result computed using 1 call(s) to binarySearch
true
0 in [0] is true
Result computed using 8 call(s) to binarySearch
false
100 in [0,...,99] is false
Result computed using 5 call(s) to binarySearch
true
77 in [0,...,99] is true
Result computed using 9 call(s) to binarySearch
true
4 in the length 1000 array is true
Result computed using 11 call(s) to binarySearch
false
5004 in the length 1000 array is false
Result computed using 14 call(s) to binarySearch
false
2001 in the length 10000 array is false
Result computed using 11 call(s) to binarySearch
true
16301 in the length 10000 array is true
Result computed using 14 call(s) to binarySearch
false
-1 in the length 10000 array is false
Result computed using 17 call(s) to binarySearch
true
4 in the length 100000 array is true
Result computed using 16 call(s) to binarySearch
true
200000 in the length 100000 array is true
Result computed using 18 call(s) to binarySearch
false
4438923 in the length 100000 array is false
5 times 4 is 20
1 times 7 is 7
9 times 10 is 90
Grading - 10 points
Binary search
- 1 point -
binarySearch
with two parameters calls a privatebinarySearch
(likely with more parameters) - 2 points - correct true/false value for all tests
- 2 points - correct number of calls for all tests
Recursive multiply
- 5 points - method is recursive and all tests get correct value
Grading turnaround
This lab will be graded with scores in Brightspace before Tuesday, November 22nd.