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!

• Be sure to include your name, your Andrew ID, and your section clearly on the top of each file in your assignment.
   
• Also on the top of each file, include a timesheet logging all the time you spent on that part of the assignment.
  You will not be graded on your number of hours, but this information will be helpful to the course staff.
   
• For non-programming problems:
  • Place all your solutions to the non-programming problems in a single file named Hw2 (with whatever extension is appropriate for the format you choose, such as Hw2.txt or Hw2.html, etc).  You must use a one of these file formats:  plain text (txt), or RTF, or HTML, or Word (doc, not docx), or PDF.  No other file formats will be accepted.
  • Show your work.  Correct answers without supporting calculations will not receive full credit.
     
• For programming problems:
  • Place all your solutions in a single file named Hw2.java.  Start with this file (with all the support code but without your solutions, of course!):  Hw2.java.
  • Use well-named variables, proper indenting, reasonable commenting, etc.
  • Restrictions:
    1. You may not use arrays or any classes or methods from java.util.* in this assignment.
    2. You may not use any String methods except charAt() and length() in this assignment.  Using other String methods will result in zero points for that problem.
    3. The point of this assignment is to practice using loops and conditionals, and so every solution must use loops and conditionals, even if an alternative approach without loops and conditionals exists.
        
• What to submit
  • Exactly two files:  Hw2.txt (or whatever extension you choose) and Hw2.java, as attachments in an email as explained above.  It is recommended that you "cc" yourself in that email, too, just to confirm that you properly sent the email.

1. ch5Exercises
2. binaryToDecimal
3. isPalindrome
4. abcd
5. mostFrequentChar
6. nthPerfectNumber
7. Bonus/Optional: isPalindromeBonus (A better isPalindrome)
8. Bonus/Optional: wordsearchContains

1. ch5Exercises
   Do the following Exercises from Chapter 5 (pp 281-283):
   Exercises 5.1,  5.2,  5.3,  5.4,  5.5,  5.7,  5.8,  5.9,  5.10  (i.e., 5.1 through 5.10 except 5.6)
    
2. binaryToDecimal
   Write the following method:
      public static int binaryToDecimal(String s)
   This method takes a (possibly-null) string s that represents a non-negative binary number and returns the decimal equivalent of that number as an int. If the string is null, or empty, or contains any characters besides '0' or '1', the method should return -1  As usual, do not worry about overflow. While there are several ways to solve this problem, you must use an approach that requires a loop in which you inspect each digit of the binary number in turn as you construct the result.  Here is a test method for you:

     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
     }
   }

3. isPalindrome
   Write the following method:
      public static boolean isPalindrome(String s)
   This method takes a possibly-null string and returns true if the given string is a palindrome, that is, the same forwards as backwards, and false otherwise.  The method returns false if the string is null, but true if it is empty (why?).  Note that this version checks non-alphabetic characters, too, so "a ba" is not a palindrome. Here is a test method for you:

     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!");
     }

4. abcd
   Write the following method:
      public static int abcd()
   This method takes no parameters and returns the one-and-only 4-digit integer abcd (where a is non-zero) where the number abcd is equal to the product of  (a^b) times (c^d). So, for example, 2371 is not the answer because (2³) * (7¹) = 8 * 7 = 56 != 2371. This method must not just return the hardcoded answer, but must use one or more "for" loops to search for the answer, and then return it.  Here is a test method for you:

     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 a^b.  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.
    

5. mostFrequentChar
   Write the following method:
      public static char mostFrequentChar(String s)
   This method takes a string and returns the most-frequently-occurring character in the given string, with ties going to the first character alphabetically. Unlike in the previous problem, this problem is case-sensitive, so 'a' and 'A' both count as an 'A', and the method's result is always an uppercase character. If the string is empty or null, the result should be the char value 0.  Here is a test method for you:

     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).
    

6. nthPerfectNumber
   Write the following method:
      public static int nthPerfectNumber(int n)
   This method takes an integer "n" and returns the nth perfect number, where a perfect number is an integer that is the sum of its proper divisors (that is, the numbers less than it that evenly divide it). For example,the proper divisors of 6 are 1, 2, and 3, and 6 = 1 + 2 + 3, so 6 is a perfect number.  Conversely, the proper divisors of 8 are 1, 2, and 4, and 8 != 1 + 2 + 4, so 8 is not a perfect number.  If n is less than 1, the method should return -1.  And, as usual, do not worry about overflow.  Here is a test method for you:

     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.
    

7. Bonus/Optional:  isPalindromeBonus (A better isPalindrome)
   Write the following method:
      public static boolean isPalindromeBonus(String s)
   This method tests for palindromes, just like the non-bonus version that was assigned, only here the matching algorithm only considers alphabetic characters, and then without regard to case.  Non-alphabetic characters are simply skipped while matching.  So, for example, the following IS a palindrome:
       "Madam, I'm Adam!"
   
   Note:  One way to solve this would be to first construct a new String composed only of the alphabetic characters in the given string, then call the simpler isPalindrome method on that string. You may not solve this problem this way!!   (Not even for partial credit.)  It is too inefficient, and it also sidesteps the logic that we want you to deal with.
   
   Instead, you must solve this by having one index increase from the left end of the string and the other decrease from the right end, with each index skipping non-alphabetic characters. Think about it...
   
   Here is a test method for you:

     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!");
     }

8. Bonus/Optional:  wordsearchContains
   Write the following method:
      public static boolean wordsearchContains(String wordsearch, String word)
   This method takes a two strings, the first representing a wordsearch (stored in a single string!), and returns true if the second string occurs in that wordsearch and false otherwise.
   
   To represent a wordsearch as a string, we simply store each row concatenated to the next where we separate the rows with a | (that is, a vertical bar, or a pipe).  So, consider this wordsearch:
   
   t a c w
   n o o c
   d o g x
   
   The rows are: "tacw", "nooc", and "dogx", so we represent the entire wordsearch as: "tacw|nooc|dogx".
   Note that this wordsearch contains:
   
   cat
   cod
   coon
   dog
   ox
   
   You are guaranteed the wordsearch contains only lowercase letters, and that the rows are all the same positive length (you do not need to handle other cases in any way).
   
   Here is a test method for you:

     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!