CSC 385 Recursion Assignment
Spring 2022
This assignment presents multiple problems that must be solved recursively. While some problems might be solved easily with iteration the goal is to get a sense of solving problems recursively. Each problem has an accompanying class file that contains tests to validate your solution as well as the method or methods to implement for each problem. You may implement any additional helper methods to help you solve the problem so long as iteration is not used except where specified.
Problem 1 – Display Row of Characters (15 Points)
Implement a method that takes a positive integer count and a char and prints on a single line the char count-times. If count is 0 or negative, then nothing should happen.
Example
Input – ‘x’, 5
Output – xxxxx
Problem 2 – Count Element (15 points)
Implement a method that takes a char array and a char and returns the number of times the char appears in the array. A 0 should be returned if the char is not in the array.
Example
Input – [‘f’, ‘a’, ‘c’, ‘a’, ‘a’, ‘e’, ‘e’, ‘f’], ‘a’
Output – 3
Reason – In the array there are 3 ‘a’ characters.
Problem 3 – Negation (15 points)
Implement a method which takes an array of 1’s and 0’s. You should turn all 1’s to 0’s and all 0’s to 1’s. This should be done on the original array. No additional arrays should be used. If the array is empty, then nothing should happen.
Example
Input – [0, 0, 1, 1, 0, 1, 0, 1, 1, 1]
After the method runs the array should become [1, 1, 0, 0, 1, 0, 1, 0, 0, 0].
Problem 4 – Reverse Array (15 points)
Reverse order for this problem means from N to 0 where N is the last index of the array. So if an array has a last index of 3 then reverse order would be 3, 2, 1, 0.
Part A – Implement a recursive method that takes an array of integers and prints it in reverse. Each number should be on a separate line. You may start from either the front or the back of the array so long as the elements are printed in reverse order. If the array is empty, then nothing should be printed.
Example
Input – [1, 2, 3]
Output
3
2
1
Part B – Implement a method that reverses the array passed to it so that the element at index 0 is now at index N, element at index 1 is now at index N – 1, and so on. This should be performed on the original array. No additional arrays should be used. If the array is empty, then nothing should happen.
Example
Input – [1, 2, 3]
After the method runs the array should be [3, 2, 1]
Problem 5 – Max or Min Value (15 points)
Part A – Implement a method that takes an integer array and returns the maximum value in the array. If the array is empty, then throw an IllegalArgumentException the contains a message about the array being empty.
Example
Input – [1, 1, 2, 2, 3, 3, 3, 4, 5, 4, 4, 3, 4, 5, 2]
Output – 5
Reason – 5 is the maximum value in the array.
Part B – Implement a method takes an integer array and returns the minimum value in the array. If the array is empty, then throw an IllegalArgumentException the contains a message about the array being empty.
Example
Input – [1, 1, 2, 2, 3, 3, 3, 4, 5, 4, 4, 3, 4, 5, 2]
Output – 1
Reason – 1 is the minimum value in the array.
Challenge Problems
Pick one of the challenge problems for 25 points. Doing both will get you an additional 10 bonus points.
Challenge Problem 1 – Add or Subtract
Implement a method that takes an array of positive integers and a target integer. Return true if it is possible to place a + or – in front of every number and get a total equal to the target number. If the array is empty a false should always be returned regardless of the target value.
Example
Input – [1, 2, 3, 4], -2
Output – true
Reason – 1 – 2 + 3 – 4 = -2
Input – [7, 1, 3, 5], 9
Output – false
Reason – No combination of + or – will result in a value of 9.
For a hint, see the end of this document.
Challenge Problem 2 – Game of Value
Suppose you are playing a game in which you draw a certain number of cards that contain two numbers. The first number represents the cost of the card, and the second number represents the value. In addition to these cards, you have a set amount of money you can spend. Implement a solution that returns the maximum value you can make while spending at or less than the amount of money you have. Each card can only be purchased once. Value, cost, and spending limit are all positive integers to keep things simple. You may assume there will be at least 1 card.
Example
Input – spend amount = [(cost=12, value=4), (cost=2, value=2), (cost=1, value=2), (cost=1, value=1), (cost=4, value=10)], spend limit=15
Output – 15
Reason – The cards with cost 2, 1, and 4 should be picked. The card with cost 12 should be ignored.
For a hint, see the end of this document.
Bonus Problem – Chardoku (15 points)
For this problem, you should watch the video on solving sudoku with backtracking on Canvas.
Implement a solution that can take 9 different alphabetic characters, all lowercase and all different, and solves a sudoku puzzle involving those 9 different characters. For examples of this type of puzzle you can visit the following page: https://www.sudokudragon.com/dailyword.php
You do not need to solve for the word just solve the Sudoku square involved. The input may contain a random collection of characters that do not pertain to a word. A sample puzzle file is given as puzzle.txt.
For this, iteration is okay for guess validation and as a part of the recursive method.
What you should turn in
Once you have completed the problems you should zip your project folder. The zip should be named your netID.zip. For instance, if your netID is broge2 then your zip should be broge2.zip.
Challenge problem 1 Hint
This problem is a decision problem which requires us to try every possible combination of adding or subtracting each value. Each choice should be a recursive call that either adds the value or subtracts the value. The base case will occur once a decision is made for each number and returned should be true or false if the total is equal to the target. The pseudocode looks like the following
This is a slight modification of the sum problem from the lab but instead of ignoring values as your second recursive call you are subtracting it from a total.
Challenge problem 2 Hint
This problem is like a decision problem. Like the sum problem from the lab, you either buy the card or you do not. Unlike a decision problem as defined in computer science you are not returning a true or false but instead returning a value that represents the maximum value you can make by keeping the cost at or below your spending amount. Base case is a little more involved in that once you’ve reached the end of the array of cards, deciding either to buy or not buy each card, you then need to make sure you haven’t gone over your spending limit. If you haven’t gone over then you should return the value of all the cards purchased. If you have gone over the spending limit, then you should return a 0.
The only other tricky part is how to determine if you’ve got the maximum value. This can be handled in several different ways. Some pseudocde might help
return max(recursive call that buys a card, recursive call that ignores a card)
The post CSC 385 Recursion Assignment Spring 2022 This assignment presents multiple problems that must be solved recursively. While some problems might be solved easily with iteration the goal is to get a sense of solving problems recursively. Each problem has an accompanying class file that contains tests to validate your solution as well as the method or methods to implement for each problem. You may implement any additional helper methods to help you solve the problem so long as iteration is not used except where specified. Problem 1 – Display Row of Characters (15 Points) Implement a method that takes a positive integer count and a char and prints on a single line the char count-times. If count is 0 or negative, then nothin appeared first on My Blog.
