HW11 - 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 has runtime O(length of the longer string).
NOTE's
- Do NOT use
StringBuilder(unless you really want to). Your big O comments must match your implementation.
TODO's
-
A-
- Implement and document (fill in big O runtime & explanation) all the functions except
subsetSum(...)- ✨ Some functions have already been implemented for you; for those ones just do the documentation part 🙂👍
- IMPORTANT: Copy and paste the autograder output into a comment at the top of your code file once you're done with everything
- IMPORTANT: Put your answers to the Final Project questions at the top of your code file
- Implement and document (fill in big O runtime & explanation) all the functions except
-
A
- Finish all the functions
-
A+
- Implement seam carving from scratch 🙂👍
- You will need to figure out how to load an image into memory from file; you can draw the image as a bunch of tiny squares using Cow
- Example: https://www.aryan.app/seam-carving/
- Implement seam carving from scratch 🙂👍
Starter Code
/*
TODO: Paste autograder output below here
TODO: Answer the questions listed here: https://github.com/james-bern/CS136/wiki/HW13
*/
class HW11 extends Cow {
public static void main(String[] arguments) {
// NOTE: Feel free to write your own tests in main
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;
}
////////////////
// AUTOGRADER //
////////////////
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("\nisPalindromeRecursive");
_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("\ngetInBinary");
_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("\nareBalanced");
_GRADE( areBalanced(""));
_GRADE(!areBalanced("("));
_GRADE( areBalanced("()"));
_GRADE(!areBalanced(")("));
_GRADE( areBalanced("()()"));
_GRADE( areBalanced("(())"));
_GRADE( areBalanced("(())()"));
_GRADE(!areBalanced("(())("));
_GRADE(!areBalanced("(()))("));
System.out.print("\nsubsetSum");
_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));
}
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 + "\"]");
}
}
}