Partner Information: You are allowed to work with one partner. Be sure to indicate in your submission who your partner is. Each Java class should have the name of each student in a comment at the top of the program
Submission Instructions: Upload your .java files to the Program 5 Dropbox.
The goal of this lab is:
Gain experience writing recursive methods
Background and Directions
In this assignment, you will solve a variety of problems using recursion. This assignment is divided up into four problems. You will use Program5Demo.java as a starting point, and fill in the method for each task.
Part I: Detecting Palindromes in Strings
A palindrome is a word, phrase, or sequence that reads the same backward as forward, such as "racecar", or "kayak". The first method, is_palindrometakes a string as an argument. This method needs to return true if the given string is palindrome, and return false if the string is not a palindrome. This method must use recursion.
Part II: Binary Search using recursion
Binary Search (as discussed in Monday 4/24's lecture) is an algorithm that searches through a sorteddataset for a target value. You will need to implement the recursive solution for binary search by filling in the body of the binary_search method. This method takes in an array, a target value, a low bound, and a high bound as an argument. This method must search through the given array and return the index of the target value. If the target value is not in the array, then the method should return -1.
Part III: Minimum number of coins to make change
In the lecture for Wednesday, April 26th, we discussed an algorithm for determing the minimum number of coins needed to make K change using a set of D denominations. You will implement this algorithm by filling in the body of the min_coins method. This method takes in an array of denominations (such as [1,5,10,25] and a target value K). This method needs to return the minimum number of coins (using the given denominations) to make the value K. For example, if K=28, and D = [1,5,10,25], the method should return 4 (25, 1, 1 ,1). This method MUST use recursion and should not use the greedy approach, because greedy does not guarantee you an optimal solution.
Part IV: Finding the solution coins used from part III
At this point, you should have the minimum number of coins needed to make some value K from part III, lets call it n. In this task, you will now find what coins were used to make K. We can calculate this by finding all combinations of length n using the denominations from the set D. Then, we only print out the combinations that add up to be K.
For example, if D = [1,5,10], n = 3, and K = 12, we calculate the following combinations:
However, the only combination that adds up to K is [1,1,10], so that is the only combination that gets printed out.
We wrote the code for this during the lecture for Wednesday, April 26th. You should be able to reuse that code here.
Starting Code
You need to use Program5Demo.java as a starting point. You are not allowed to change anything in the main() method. You are allowed to define more methods if you'd like.
Restrictions
All four of the methods you write MUST use recursion, or call a method that uses recursion
Sample Output
When your program is run, it should look exactly like this: sample output
Grading (100 points)
Requirement
Points
Palindrome method is correct and uses recursion
30
Binary Search method is correct and uses recursion
20
Minimum coins method is correct and uses recursion