3 files in total
BuggyRecursion.java
ChangeMaker.java
A PDF that contains your self-assessment & reflection
Homeworks are an opportunity to engage with the material and practice your programming skills. To support you, solutions will be available on moodle. It is your responsibility to engage with them in a way that strategically moves your learning forward. You should:
Attempt the homework without looking at the solutions.
Review the solutions; if you were stuck, you may revise your homework. You may find yourself iteratively reviewing and revising to best support your learning.
When you submit your homework, you will be required to complete a self-assessment and reflection:
Give yourself an assessment mark on the initial attempt:
✘ if you did not complete it
✓- if you completed it, but were very far from the solution
✓ if you completed it and essentially had the solution
✓+ if you completed it correctly, including precise communication
? if you are unsure as to whether or not you completed it
Provide a short reflection as to why you earned that mark, such as:
I did not understand how to get started, and it was too close to the deadline to visit support hours.
I got stumped by a bug where my program entered an infinite loop.
If you used the solutions to revise your work, describe what you needed to change, as in:
I modified the style of my conditional when I saw a simpler approach in the solutions.
I was so stuck that the majority of my submission is based on the solutions.
Ask specific questions on portions that are still confusing, such as:
Why does it cause an error when I returned "1" instead of 1?
[Optional] Provide one hint for the homework (to your past self or future student).
For this homework, you'll be focused on recursion. First, you'll debug a program, then you'll implement a recursive solution to a problem that you will probably encounter again in CS 312 Algorithms. This is a chance to practice implementing a recursive function, even though you may not have thought up the recursive approach.
Develop a little, test a little...
Be thoughtful of your process; you may want to think about the design vs implementation phases
Resist the temptation to write the entire program all at once! Otherwise, the debugging process becomes so much more difficult and time-consuming!
First, create the skeleton of your program files by writing "stubs" (declarations of the classes, instance methods and functions with "placeholder" implementations).
Then implement one part at a time and test as you go.
Remember you have different types of debugging strategies:
Print statements help you peek at memory during program execution.
Tracing your program on paper helps you understand when the execution doesn't match your intended logic.
The Debugger can help you do both!
Be strategic!
Be intentional around your approach to working on the project:
Start early!
Ask questions!
Leave time for questions by... starting early :)
When you're stuck, pause and evaluate what could be going on. Consider the self-regulated learning cycle!
Do you have a plan?
Are you evaluating your plan? How will you test your code as you go?
How will you revise? What will you do when you're confused? Stuck?
The program below has some bugs in it!
Copy it into a file named BuggyRecursion.java
Work to debug the program, using the comments and test code to guide you.
public class BuggyRecursion
{
public BuggyRecursion()
{
testReverseString();
testPalindrome();
testCountDown();
}
/**
* Given a word, reverse it. For example,
* "cat" -> "tac" and "bulb" -> "blub".
*/
public String reverseString( String word )
{
// base case
if (word.length() == 0)
return word;
// recursive case
else
{
// peel off the first letter and recurse
String firstLetter = word.substring(0,1);
String restOfWord = word.substring(1);
return firstLetter + reverseString(restOfWord);
}
}
/**
* A palindrome is a word that is the same as its own reversal.
* For example, "wow" is a palindrome since it is the same forwards as backwards,
* but "bulb" is not. This function should return true if the given word
* is a palindrome.
* @return
*/
public boolean isPalindrome( String word )
{
// base case
if (word.length() == 1)
return true;
// recursive case
else
{
// peel off outer two
String firstLetter = word.substring( 0, 1 );
String lastLetter = word.substring( word.length() - 1 );
String interior = word.substring(1,word.length()-1 );
// check if the first and last match
if (firstLetter.equals(lastLetter))
// then recurse
return isPalindrome(interior);
// otherwise, we know it's not a palindrome
return false;
}
}
/**
* Given a number greater than or equal to 0
* to start at, counts down until the value 1, then ends with "Go!".
* Invalid inputs (with a negative number) should return the empty string "".
* For example,
* 5 -> "5,4,3,2,1,Go!"
* 3 -> "3,2,1,Go!"
* -4 -> ""
*/
public String countDown( int startValue )
{
// base case
if (startValue == 0)
return "Go!";
// recursive case
else
return countDown( startValue - 1 ) + Integer.toString(startValue) + ",";
}
public void testReverseString()
{
String[] testCases = {"bulb","cat",""};
String[] expectedOutput = {"blub","tac",""};
for ( int i = 0; i < testCases.length; i++ )
{
String testOutput = "Testing reverseString(" + testCases[i] + ")...";
String testResult = reverseString( testCases[i] );
if (testResult.equals(expectedOutput[i]))
testOutput += "PASSED";
else
testOutput += "FAILED";
System.out.println( testOutput + "\nExpected: " + expectedOutput[i] + ", Actual: " + testResult );
}
}
public void testCountDown()
{
int[] testCases = {5,3,0,-2};
String[] expectedOutput = {"5,4,3,2,1,Go!","3,2,1,Go!","Go!",""};
for (int i = 0; i < testCases.length; i++ )
{
String testOutput = "Testing countDown(" + Integer.toString(testCases[i]) + ")...";
String testResult = countDown( testCases[i] );
if (testResult.equals(expectedOutput[i]))
testOutput += "PASSED";
else
testOutput += "FAILED";
System.out.println( testOutput + "\nExpected: " + expectedOutput[i] + ", Actual: " + testResult );
}
}
public void testPalindrome()
{
String[] testCases = {"bulb","wow","","cat"};
boolean[] expectedOutput = {false,true,true,false};
for (int i = 0; i < testCases.length; i++ )
{
String testOutput = "Testing isPalindrome(" + testCases[i] + ")...";
boolean testResult = isPalindrome( testCases[i] );
if (testResult == expectedOutput[i] )
testOutput += "PASSED";
else
testOutput += "FAILED";
System.out.println( testOutput + "\nExpected: " + expectedOutput[i] + ", Actual: " + testResult );
}
}
public static void main( String[] args )
{
new BuggyRecursion();
}
}
You're at a convenience store and want to be something that costs target cents. You look in your wallet and see a random assortment of coins. Can you pay with exact change?
Here is a more precise formulation of the problem:
Input
An integer target
An array of integer values representing the coins you have
Output
true if there is a subset of the values (you can only "use" each element of the array at most once) that sum to the target
false otherwise
As discussed in class, we can use a recursive approach to solve this problem:
Base cases
When target < 0, you cannot make change
When target is 0, you can make change
When target > 0 and there are no coins, you cannot make change
Recursive case (when target > 0 and there are coins)
Choose an arbitrary coin -- we'll use the last one
You can make change if:
You use that coin and can make change with only the remaining coins and a reduced target value (target minus the value of that coin)
OR
You can make change with only the remaining coins
To help you move towards an implementation in Java, here is some starter code.
Work through and add some additional test cases to make sure you understand the problem.
Implement the comments with pseudocode to practice writing recursive function calls.
ChangeMaker.java
public class ChangeMaker
{
public ChangeMaker()
{
testExactChange();
}
/**
* Determine if it is possible to make exact change for the target
* value given the array of coin values. Return true if it is possible
* and false otherwise.
*/
public boolean exactChange( int target, int[] values )
{
// "start" the recursion by allowing all coins to be used
return exactChange( target, values, values.length );
}
/**
* Determine if it is possible to make exact change for the target
* value using only coin values at indices 0 up to (but not including)
* stopIndex. Return true if it is possible and false otherwise.
*/
public boolean exactChange( int target, int[] values, int stopIndex )
{
// Base cases
// When target < 0, you cannot make change
// When target is 0, you can make change
// When target > 0 and there are no coins, you cannot make change
// HINT: there are no coins if the stopIndex is 0
// Recursive case (when target > 0 and there are coins)
// Choose an arbitrary coin -- we'll use the last one
// HINT: the last one is the one at index stopIndex - 1
// You can make change if:
// You use that coin and can make change with only the remaining coins
// and a reduced target value (target minus the value of that coin)
// OR
// You can make change with only the remaining coins
// HINT: to recurse on the remaining coins, subtract 1 from the stopIndex
// STUB placeholder
return false;
}
/**
* Here are some initial test cases, though you should add some of your own as well!
*/
public void testExactChange()
{
int[] coins1 = {1,1,5,10,50};
int[] targets1 = {2,22,53,61};
boolean[] expectedOutputs1 = {true, false, false, true};
int[] coins2 = {5,26,30};
int[] targets2 = {31,35,28,0};
boolean[] expectedOutputs2 = {true, true, false, true};
int[] coins3 = {2,3,7,7,22,50,75};
int[] targets3 = {62,63,97,17};
boolean[] expectedOutputs3 = {true, false, true, true};
int[] coins4 = {};
int[] targets4 = {0,5,10};
boolean[] expectedOutputs4 = {true, false, false};
testExactChange( coins1, targets1, expectedOutputs1 );
testExactChange( coins2, targets2, expectedOutputs2 );
testExactChange( coins3, targets3, expectedOutputs3 );
testExactChange( coins4, targets4, expectedOutputs4 );
}
public void testExactChange( int[] values, int[] targets, boolean[] expectedOutputs )
{
for (int i = 0; i < targets.length; i++ )
{
String testOutput = "Testing exactChange(" + Integer.toString(targets[i]) + ", {";
for ( int j = 0; j < values.length; j++ )
testOutput += Integer.toString( values[j] ) + ", ";
// if there were values in the list, we have an extra ", " at the end
if (values.length > 0)
// strip off the last two characters to remove the extra ", "
testOutput = testOutput.substring( 0, testOutput.length() - 2);
testOutput += "})...";
boolean testResult = exactChange( targets[i], values );
if (testResult == expectedOutputs[i])
testOutput += "PASSED";
else
testOutput += "FAILED";
System.out.println( testOutput + "\nExpected: " + expectedOutputs[i] + ", Actual: " + testResult );
}
}
public static void main( String[] args )
{
new ChangeMaker();
}
}