Homework 12 - james-bern/CS136 GitHub Wiki
README
This homework is shorter so you have a chance to get a jump start on your Final Project!
But be careful on the big O runtimes! Discuss with your friends! Ask questions!
Recall that stringA + stringB is O(length of the longer string).
Specification
- To get a A:
- ✅ Implement and document (fill in big O runtime & explanation) all the functions.
- ✨ Some functions are already implemented for you; just document those ones. 🙂👍
- ✅ Implement and document (fill in big O runtime & explanation) all the functions.
Submission Instructions
- ✅ Put your answers to the Final Project questions at the top of your code file.
- ✅ Put the output of
runAutograder()in a comment at the top of your code file.- 🚨 You must do this.
Starter Code
class HW12 {
static void runAutograder() {
System.out.println("\nRUNNING AUTOGRADER");
System.out.print ("------------------");
System.out.print("\n _ITERATIVE_isPalindrome");
_grade( _ITERATIVE_isPalindrome("racecar"));
_grade(!_ITERATIVE_isPalindrome("racedar"));
_grade( _ITERATIVE_isPalindrome("amanaplanacanalpanama"));
_grade( _ITERATIVE_isPalindrome(""));
_grade( _ITERATIVE_isPalindrome("a"));
System.out.print("\n isPalindromeRecursive");
_grade( isPalindrome("racecar"));
_grade(!isPalindrome("racedar"));
_grade( isPalindrome("amanaplanacanalpanama"));
_grade( isPalindrome(""));
_grade( isPalindrome("a"));
System.out.print("\n _ITERATIVE_getInBinary");
_grade(_ITERATIVE_getInBinary(0), "0");
_grade(_ITERATIVE_getInBinary(1), "1");
_grade(_ITERATIVE_getInBinary(2), "10");
_grade(_ITERATIVE_getInBinary(3), "11");
_grade(_ITERATIVE_getInBinary(4), "100");
_grade(_ITERATIVE_getInBinary(37), "100101");
System.out.print("\n getInBinary");
_grade(getInBinary(0), "0");
_grade(getInBinary(1), "1");
_grade(getInBinary(2), "10");
_grade(getInBinary(3), "11");
_grade(getInBinary(4), "100");
_grade(getInBinary(37), "100101");
System.out.print("\n _ITERATIVE_areBalanced");
_grade( _ITERATIVE_areBalanced(""));
_grade(!_ITERATIVE_areBalanced("("));
_grade( _ITERATIVE_areBalanced("()"));
_grade(!_ITERATIVE_areBalanced(")("));
_grade( _ITERATIVE_areBalanced("()()"));
_grade( _ITERATIVE_areBalanced("(())"));
_grade( _ITERATIVE_areBalanced("(())()"));
_grade(!_ITERATIVE_areBalanced("(())("));
_grade(!_ITERATIVE_areBalanced("(()))("));
System.out.print("\n areBalanced");
_grade( areBalanced(""));
_grade(!areBalanced("("));
_grade( areBalanced("()"));
_grade(!areBalanced(")("));
_grade( areBalanced("()()"));
_grade( areBalanced("(())"));
_grade( areBalanced("(())()"));
_grade(!areBalanced("(())("));
_grade(!areBalanced("(()))("));
System.out.print("\n subsetSum");
_grade( subsetSum(new int[] {}, 0));
_grade( subsetSum(new int[] { 2 }, 2));
_grade( subsetSum(new int[] { 2 }, 0));
_grade(!subsetSum(new int[] { 2 }, 7));
_grade( subsetSum(new int[] { 1, 5, 9 }, 10));
_grade( subsetSum(new int[] { 1, 5, 9 }, 0));
_grade(!subsetSum(new int[] { 1, 5, 9 }, 3));
_grade( subsetSum(new int[] { 3, 4, 5 }, 3));
_grade( subsetSum(new int[] { 3, 4, 5 }, 12));
_grade(!subsetSum(new int[] { 3, 4, 5 }, 6));
}
////////////////////////////////////////////////////////////////////////////////
// YOUR WORK STARTS HERE ///////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
public static void main(String[] arguments) {
runAutograder();
}
// Get whether the word is the same forwards and backwards.
// Big O Runtime: O(?)
// Big O Runtime Explanation: ???
static boolean _ITERATIVE_isPalindrome(String word) {
for (int i = 0; i < word.length() / 2; ++i) {
int j = (word.length() - 1) - i;
if (word.charAt(i) != word.charAt(j)) {
return false;
}
}
return true;
}
// Get whether the word is the same forwards and backwards.
// NOTE: You must use recursion.
// NOTE: Do NOT write any helper functions.
// HINT: Check the String Documentation for charAt(...) and substring(...).
// Big O Runtime: O(?)
// Big O Runtime Explanation: ???
static boolean isPalindrome(String word) {
// TODO
return false;
}
// Get n in binary.
// 0 -> "0"
// 1 -> "1"
// 2 -> "10"
// ...
// Big O Runtime: O(?)
// Big O Runtime Explanation: ???
static String _ITERATIVE_getInBinary(int n) {
String result = "";
do {
result = (n % 2) + result;
n /= 2;
} while (n > 0);
return result;
}
// Get n in binary.
// 0 -> "0"
// 1 -> "1"
// 2 -> "10"
// ...
// NOTE: You must use recursion.
// HINT: You may eventually want to use a helper function.
// Big O Runtime: O(?)
// Big O Runtime Explanation: ???
static String getInBinary(int n) {
// TODO
return "";
}
// Get whether the parentheses are balanced.
// (()(())) is balanced
// (() is NOT balanced
// ())( is NOT balanced
// Big O Runtime: O(?)
// Big O Runtime Explanation: ???
static boolean _ITERATIVE_areBalanced(String parens) {
int count = 0;
for (int i = 0; i < parens.length(); ++i) {
if (parens.charAt(i) == '(') { ++count; }
if (parens.charAt(i) == ')') { --count; }
if (count < 0) { return false; }
}
return (count == 0);
}
// Get whether the parentheses are balanced.
// ()(()) is balanced
// (() is NOT balanced
// ())( is NOT balanced
// NOTE: You must use recursion.
// HINT: ()(()) -> (()) -> () -> => balanced
// HINT: (() -> ( => NOT balaned
// HINT: ())( -> )( => NOT balaned
// HINT: Check the String Documentation for substring(...) and indexOf(...).
// PS on't forget about the all_powerful + (plus sign).
// Big O Runtime: O(?)
// Big O Runtime Explanation: ???
static boolean areBalanced(String parens) {
// TODO
return false;
}
// Get whether there is a subset of numbers in the set that sum to the target.
// You can only use each number once.
// { 1, 5, 9 } can make 10 (1 + 9 = 10)
// { 1, 5, 9 } can NOT make 3 (no subset sums to 3)
// NOTE: You must use recursion.
// NOTE: Do NOT modify set; do NOT make any new arrays.
// HINT: You will want to write a helper function.
// HINT: subsetSum(...) can be 1 line long.
// HINT: _subsetSumHelper(...) can be ~2 lines long (definitely not more than ~10).
// Big O Runtime: O(?)
// Big O Runtime Explanation: ???
static boolean subsetSum(int[] set, int target) {
// TODO
return false;
}
////////////////////////////////////////////////////////////////////////////////
// YOUR WORK ENDS HERE /////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
static void _grade(boolean shouldBeTrue) {
System.out.print(shouldBeTrue ? '+' : '-');
}
static void _grade(String student, String answer) {
boolean shouldBeTrue = student.equals(answer);
_grade(shouldBeTrue);
if (!shouldBeTrue) {
System.out.print("[\"" + student + "\" vs. \"" + answer + "\"]");
}
}
}