Computer Science 15-100 (Sections S-V), Fall 2008
Homework 2
Due: Mon 8-Sep-2008 at 11:59pm (email copy) and at Tuesday's
class/recitation
(identical physical copy)
(no late submissions accepted).
Note #1: Submit this hw via one and only one email submission to koz <at> andrew.cmu.edu (David Kosbie). Do not submit to your CA. And be sure to follow the exact submission guidelines as noted below.
Note #2: Be sure to pay attention to details. For example, name your program "Hw2.java" as specified, and not "hw2.java" or "MyHw2.java" or anything exception "Hw2.java". Failure to adhere to any of the specific instructions will result in a 5% or greater deduction in your hw2 score.
Read these instructions first!
public static void testBinaryToDecimal() { System.out.print("Testing binaryToDecimal... "); assert(binaryToDecimal("0") == 0); assert(binaryToDecimal("1") == 1); assert(binaryToDecimal("10") == 2); assert(binaryToDecimal("11") == 3); assert(binaryToDecimal("01001") == 9); assert(binaryToDecimal("11001") == 25); assert(binaryToDecimal("This is not a binary number!") == -1); assert(binaryToDecimal("") == -1); assert(binaryToDecimal(null) == -1); System.out.println("Passed all tests!"); }
Hint #1: Not sure about counting in binary? Try this
page:
http://en.wikipedia.org/wiki/Binary_numeral_system#Counting_in_binary
Or for more fun, try this page:
http://en.wikipedia.org/wiki/Finger_binary
Hint #2: In base 10 (decimal, what you are used to), say you have a number (say, 32) and you wish to add a digit (say, 4) to its right end (hoping to get 324). To do this, multiply the number by 10 (320 * 10 = 320) and add the new digit (320 + 4 = 324 -- hurray!). The same approach works in binary, only instead of multiplying by 10 (the base of our decimal system), we multiply by 2 (the base of the binary system). So, if we have the binary number 110 (the number 6 in decimal), and we wish to add a 1 to the right, we multiply 110 times 2 (which is written as 10 in binary) to get 1100 in binary (or 12 in decimal, and indeed 6*2 = 12) and then add 1 to get 1101 in binary, which is 13 in decimal. Why is this a hint? Because this is the simple way to solve this problem. According to this algorithm, you can solve this problem by starting your answer at zero, and iterating over the string from left-to-right, where for each character (representing a digit) you double your current answer and then add the next digit to it. That's it.
Hint #3: For this and other problems in this assignment, you may need to determine the length of a string. This is done with the length method, as the following code demonstrates:
class MyCode {
public static void main(String[] args) {
String s = "Carpe diem";
int n = s.length();
System.out.println(n); // prints 10
}
}
public static void testIsPalindrome() { System.out.print("Testing isPalindrome... "); assert(isPalindrome("a") == true); assert(isPalindrome("ab") == false); assert(isPalindrome("a ba") == false); assert(isPalindrome("bab") == true); assert(isPalindrome("baab") == true); assert(isPalindrome("b,ab") == false); assert(isPalindrome("b,a,b") == true); assert(isPalindrome("Madam, I'm Adam") == false); assert(isPalindrome("madamimadam") == true); assert(isPalindrome("") == true); assert(isPalindrome(null) == false); System.out.println("Passed all tests!"); }
public static void testAbcd() { System.out.print("Testing abcd... "); int n = abcd(); assert((n >= 1000) && (n < 10000)); assert(pow(n/1000,(n/100)%10)*pow((n/10)%10,n%10) == n); System.out.println("Passed all tests!"); }
Helper Method: pow
In writing the "abcd" method, you will see that you will have to raise
an integer value to an integer power. Now, the Math class has a pow
method, but it raises a double value to a double power, and returns a
double. We could convert that into an int by rounding it and then
truncating, but that's a nuisance, especially if we have to do it more than
once (which in fact you must for the abcd problem). Instead, it would
be handy to write our own method, pow, that takes two integers and returns
the integer value of raising the first integer to the second integer.
Because we are writing this pow method specifically to help us with the abcd
method, we say the pow method is a
helper method.
Using helper methods is a form of
decomposition, breaking a
problem up into smaller, more easily manageable problems. Here is the
complete description for the helper method pow that you must write to solve
the abcd problem:
Write the following method:
public static
int pow(int a, int b)
This method takes two integers, a and b,
and returns the integer value ab. If b is less than 0, the
method just returns 0. As usual, do not worry about overflow.
Here is a test method for you:
public static void testPow() { System.out.print("Testing pow... "); assert(pow(2, -1) == 0); assert(pow(2, 0) == 1); assert(pow(2, 1) == 2); assert(pow(2, 5) == 32); assert(pow(-2, 5) == -32); assert(pow(-2, 6) == 64); System.out.println("Passed all tests!"); }
Note: When writing pow, you must use a loop, and
you may not use any Math methods. In the loop, keep multiplying by
"a", and keep doing this until you have multiplied "b" times.
public static void testMostFrequentChar() { System.out.print("Testing mostFrequentChar... "); assert(mostFrequentChar("STUV") == 'S'); assert(mostFrequentChar("tuvw") == 'T'); assert(mostFrequentChar("UTSR") == 'R'); assert(mostFrequentChar("This is a test") == 'S'); assert(mostFrequentChar("") == ((char)0)); assert(mostFrequentChar(null) == ((char)0)); System.out.println("Passed all tests!"); }
Helper Method: unspecified (but required!)
In writing your mostFrequentChar method, you must use top-down
design, including a well-conceived helper method. What should it do?
Well, it would be handy if you had a method that took 2 parameters, a String
and char, and returned the number of times (that is, the frequency)
the given char occurs in the given String. With this helper method,
you could write mostFrequentChar by checking frequency of each char between
'A' and 'Z' and selecting the largest one. Note that you must also include a test method for your helper method
(and you will be graded, in part, on the quality of the test cases in that
test method).
public static void testNthPerfectNumber() { System.out.print("Testing nthPerfectNumber... "); assert(nthPerfectNumber(-5) == -1); assert(nthPerfectNumber(0) == -1); assert(nthPerfectNumber(1) == 6); assert(nthPerfectNumber(2) == 28); assert(nthPerfectNumber(3) == 496); System.out.println("Passed all tests!"); }
Helper Method: unspecified (but required!)
Again, in writing your nthPerfectNumber method, you must use a well-conceived helper method. You must
also include a test method for your helper
method (and, again, you will be graded, in part, on the quality of the test
cases in that test method).
Note: As should be apparent,
decomposition
into helper
methods
is a great way to design your programs. You are expected to use
this approach in all future programming assignments.
public static void testIsPalindromeBonus() { System.out.print("Testing isPalindromeBonus... "); assert(isPalindromeBonus("a") == true); assert(isPalindromeBonus("ab") == false); assert(isPalindromeBonus("a ba") == true); // false for isPalindrome assert(isPalindromeBonus("bab") == true); assert(isPalindromeBonus("b,ab") == true); // false for isPalindrome assert(isPalindromeBonus("b,abb") == false); assert(isPalindromeBonus("b,a,b") == true); assert(isPalindromeBonus("Madam, I'm Adam") == true); // false for isPalindrome assert(isPalindromeBonus("madamimadam") == true); assert(isPalindromeBonus("") == true); assert(isPalindromeBonus(null) == false); System.out.println("Passed all tests!"); }
public static void testWordsearchContains() { System.out.print("Testing wordsearchContains... "); // These tests cover this wordsearch: // t a c w // n o o c // d o g x assert(wordsearchContains("tacw|nooc|dogx", "cat")); assert(wordsearchContains("tacw|nooc|dogx", "cod")); assert(wordsearchContains("tacw|nooc|dogx", "coon")); assert(wordsearchContains("tacw|nooc|dogx", "dog")); assert(wordsearchContains("tacw|nooc|dogx", "ox")); assert(!wordsearchContains("tacw|nooc|dogx", "caw")); assert(!wordsearchContains("tacw|nooc|dogx", "cow")); assert(!wordsearchContains("tacw|nooc|dogx", "con")); assert(!wordsearchContains("tacw|nooc|dogx", "dogs")); assert(!wordsearchContains("tacw|nooc|dogx", "ax")); System.out.println("Passed all tests!"); }Note: This approach of representing a 2-dimensional board in a 1-dimensional string is not a very good idea. Soon, we will learn about other ways we can more naturally represent this data, such as in a 2-dimensional array.
Carpe diem!