Computer Science 15-100 (Sections T & U), Fall 2007
Homework 7
Due:  Fri 2-Nov-2007 at 8:30am (email copy) and at recitation (physical copy)

  1. Study the sample code from class, including the following examples.  You should be able to write these from scratch, which you should do here (although you do not have to turn in anything for this exercise).  The subsequent exercises have been limited to provide you with extra time to study these methods and to work with the xSortLab demo:
  1. To enable you to study the swapping behaviors of the three sorting algorithms we have studied, here you will write an instrumented "swap" method.  This method has the same signature as the swap method written in class, but it prints out the indexes and values being swapped, as well as the resulting array after the swap.  So a call to swap as such:
         int[] a = { 21, 17, 6, 44, 2 };
         swap(a,1,2);
    Would not only swap a[1] with a[2], but would also print out the following message:
         Swapping a[1]=17 with a[2]=6, now a = { 21, 6, 17, 44, 2 }
    If the array contains more than 10 elements, then do not print out the resulting array, as such:
         int[] a = { 21, 17, 6, 44, 2, 66, 4, 2, 8, 9, 7, 1, 8 };
         swap(a,1,2);
    This prints:
         Swapping a[1]=17 with a[2]=6
    Again, the point of this exercise is for you to use the instrumented version of swap to study the behavior of the three sorting algorithms (bubblesort, selectionsort, and insertionsort).  You are encouraged to do so!
     
  2. Write a method with this signature:
         public static int[] readInts(String prompt)
    This method takes one non-null string, a prompt which it first outputs using System.out.print, and then it reads in a line of text as a string using scanner.nextLine().  The line is guaranteed to contain zero-or-more integers, each separated by exactly one space (and no leading space or trailing space on the line).  This method will convert this string into an array of int's corresponding to these values.  For example, a call to:
         int[] a = readInts("Enter some integers: ");
    would produce I/O like this:
         Enter some integers:  5 3 6 1 2
    and would ultimately set the array a to { 5, 3, 6, 1, 2 }.

    Here, you will be aided by a helpful method:  String.split().  This method, which can only be called on non-null String objects, takes a String delimiter (like a comma, or in this case a space) and returns an array of strings where the original string is split according to the given delimiter.  For example:
         String s = "this is a test";
         String[] sa = s.split(" ");
    This sets the array "sa" equal to { "this", "is", "a", "test" }. 

    To proceed, you should first convert the line of input to an array of strings, then you should call this method (which you will write):
         public static int[] parseStringsToInts(String[] strings)
    This method takes an array of strings which are guaranteed to represent integers (such as we just produced above), and returns an array of "int" values corresponding to those strings.

    In order to write this method, you will iterate over each string in the "strings" array and call this method (which you will also write):
         public static int parseStringToInt(String s)
    This method converts a single string "s", which is guaranteed to represent an integer, into the integer it represents, returning -1 if it is an illegal format.  This method may seem familiar from a previous homework assignment.

    As an important aside:  you should consider how we approached this problem using top-down design.  When writing the "readInts" method, we realized we would benefit from a "parseStringsToInts" method, which then implied the need for a "parseStringToInt" method.  When we decompose or factor our problem in this way, we can write bite-sized pieces of code that are easier to understand, easier to test and debug, and more likely to be reused in future programs we might write.  All good things, and all things you should know (hint:  obvious quiz question:  list three advantages of top-down design).
     
  3. Write a method with this signature:
         public static int median(int[] a)
    This method takes a possibly-null and possibly-empty array "a" of int values and returns the median of those values (or -1 if no median exists).  The median of a list of numbers is the middle number when that list is sorted, or if there are two middle numbers (as with lists with an even number of elements) then it is the average of those two middle numbers.  Thus, we need to have sorted data to find the median.  However, here is an important caveat:  you may not alter the incoming array "a" in any way (that is, you must be non-destructive).   Thus, after checking if the array is null or of zero length (and returning -1 in either case), you should copy the array (using top-down design, so call a method to do this!), then sort the copied array (using a sort from lecture), then find the median of the sorted copied array.

    Your checking code for this method should use your readInts() method from above to read in an array of int values and then should print out their median.
     
  4. Write a method with this signature:
         public static String spellCheck(String sentence)
    This method takes a possibly-null string "sentence" (that your check method will read via "nextLine") and spell checks it against a built-in dictionary, returning the first misspelled word in the sentence, or returning null if there are no misspelled words.

    Here, by the way, is your (very small) dictionary, which is a sorted array of lowercase strings, and which should be placed outside any method but inside your class.  In this way, it will be visible to every method in the class:
         public static String[] dictionary = {
            "a", "can", "cat", "do", "dog", "happy", "i", "is", "sad",
            "say", "says", "test", "that", "the", "this", "very"
         };

    Using top-down design, we realize our first step is to write a method with this signature:
         public static String[] getLowerCaseWords(String sentence)
    This method takes a sentence, as described above, and returns an array of the words in the sentence all in lowercase.  To do this, the method first converts the string to lowercase using string.toLowerCase, then splits this string with String.split using spaces as delimiters.  So if sentence is, say:
         "This, I say, is a test!"
    then the split array will be:
         {"this,", "i", "say,", "is", "a", "test!"}
    Notice that the commas and the exclamation point have been included in the words.  This is undesirable, so the second step is to replace each string in the array with an equivalent string with only letters.  Of course, we do that with top-down design, using this method:
         public static String removeNonLetters(String word)
    After this process, our sample array would be:
         {"this", "i", "say", "is", "a", "test"}
    This array is returned from getLowerCaseWords.  You may have noticed that words containing only non-letters, such as numbers, will be replaced with the empty string "".  This is correct -- we will not spell check these non-letter-containing words.

    To proceed, we now need to iterate over each word and, if that word is non-empty, check if it is in the dictionary.  Here, we realize that the dictionary is a sorted array, and so we should use binary search.  Hence, proceeding with top-down design, we write a method with this signature:
         public static int binarySearch(String[] a, String s)
    This method works like our binarySearch method from class, only it finds a string in a sorted array of strings rather than an int in a sorted array of int's.  The method returns the index where the string "s" occurs, or -1 if it is not in the sorted array.  The main difference between this method and the method from class is that you cannot compare two strings using "==", "<", or ">".  Instead, as you may recall, you must use the compareTo method, as such:
         String s1 = "abc";
         String s2 = "def";
         String s3 = "ghi";
         String s4 = "def";
         System.out.println(s2.compareTo(s3)); // prints a negative #, so s2 < s3
          System.out.println(s2.compareTo(s1)); // prints a positive #, so s2 > s1
         System.out.println(s2.compareTo(s4)); // prints zero, so s2.equals(s4)

    So, if a word is non-empty and the binarySearch method returns -1, then we found a word that is not in our dictionary so we return that word from spellCheck.  If we make it all the way through the array of words, then we return null to indicate that the spellCheck succeeded.

    Your check method should read in a sentence (using nextLine) and print out the first misspelled word or some happy message if the spellCheck succeeded.

Carpe diem!