full size picture of the trace.
public static int total1 (int[] A, int start, int finish) {
if (finish==start)
return A[finish];
else
return A[start] + total1(A, start+1, finish);
}
public static int total2 (int[] A, int start, int finish) {
if (finish==start)
return A[finish];
else {
int mid = (start+finish)/2;
return total2(A, start, mid) + total2(A, mid+1, finish);
}
}
Some particular things to notice:
Let k be any integer >= 0.
INDUCTION HYPOTHESIS: Assume that S(k) is true.
INDUCTION STEP: Prove that S(k+2) is true.
You should be able to figure out exactly what it is that
this allows one to conclude. If not, you'll never be sure that
a proof structure is valid. Here's the answer:
For all k>=0, [ S(k) => S(k+2) ]
(For more practise with this issue, look at question 1 on Horton's
second midterm, evening section.)
Now ask yourself, does this connect properly with the base case(s)
to allow one to conclude that S(n) is true for all n >= 0?
Let S(n) represent the following statement:
"If isaPalindrome is called with a string of length n, the
method returns true if the string is a palindrome and false
otherwise."
PROVE: S(n) is true for all n >= 0.
PROOF: by induction on n.
-------------------------------------------------------------------------------
BASE CASES: Prove S(0) and S(1)
Assume isaPalindrome is called with a string of length either 0 or 1.
- All strings of length 0 or 1 are palindromes.
- In both cases, the first if-condition is satisfied,
so the first branch of the if-statement is taken,
and true is immediately returned.
Thus S(0) and S(1) are both true.
Let k be any integer >= 0.
INDUCTION HYPOTHESIS: Assume that S(k) is true.
INDUCTION STEP: Prove that S(k+2) is true.
Assume that isaPalindrome is called with a string of length k+2.
- Consider the following two exhaustive cases:
Case (1): s(0) == s(s.length()-1)
- Since the first and last characters of s are the same,
s is a palindrome if and only if s with those characters removed
is a palindrome.
- k >= 0, so k+2 >= 2. Thus the length of the string is >= 2.
- Thus the first if-condition is not satisfied,
but the second one is, because s(0) == s(s.length()-1).
- So the second branch of the if-statement is taken,
and the method returns the value of:
isaPalindrome (s.substring(1, s.length()-1))
- The length of the string in this recursive call is
two less than the length of s, that is (k+2)-2, which is k.
- By the induction hypothesis, S(k) is true. In other words,
if isaPalindrome is called with a string of length k, the
method returns true if the string is a palindrome and
false otherwise.
- So the recursive call will return true if the inner part of s
(s with the outer two characters removed) is a palindrome,
and false otherwise.
- Consider those two exhaustive cases:
Case (1a): the inner part of s is a palindrome.
- Thus s as a whole is a palindrome, since its first and
last characters are also equal.
- In this case, the recursive call returns true,
and this true is returned from the original call.
Case (1b): the inner part of s is *not* a palindrome.
- Thus s as a whole is not a palindrome.
- In this case, the recursive call returns false,
and this false is returned from the original call.
- So in both Cases (1a) and (1b), the method returns
true if the string is a palindrome and false otherwise.
Case (2): s(0) != s(s.length()-1)
- s is not a palindrome, since the first and last characters differ.
- k >= 0, so k+2 >= 2. Thus the length of the string is >= 2.
- Thus the first if-condition is not satisfied,
and neither is the second one, since s(0) != s(s.length()-1).
- The last branch of the if-statement is therefore taken, and
isaPalindrome returns false.
- So in this case, the method returns
true if the string is a palindrome and false otherwise.
- So in both Cases (1) and (2), the method returns
true if the string is a palindrome and false otherwise.
So if isaPalindrome is called with a string of length k+2,
the method returns true if the string is a palindrome and false otherwise.
So, S(k+2) is true.
INDUCTION CONCLUSION: S(n) is true for all n >= 0.
One flaw in the solution is that Lexicon's buildLexicon method itself prompts for and opens the file. It would be better if it was merely told the stream to read from. This would leave the client code responsible for doing that work, but in return the client code would have more control. Perhaps there is already a file stream open, for example.
Similarly, other methods in Lexicon include output messages that I would prefer to see handled by the client code. This is particularly clear in the lookup method. It would be better to return a boolean than to print a message about the string. The client code may not want to print any message at all -- just to act on whether or not the string is in the lexicon.
There are 3 things that influence the behaviour of the method: the contents or shape of the trie, the length of the string being inserted, checked, or printed, and the presence or absence of words sharing the same prefix.
1. Test the methods on an empty trie.
- Check should return false
- Print all strings should do nothing.
- Print strings with prefix should give an appropriate message.
- Insert should correctly insert a string into an empty trie.
- potentially two cases here: inserting a string of length
1, and inserting a string of length longer than one.
- Build a lexicon should correctly start from an empty trie
The remainder of the tests assume that the trie contains at least one
string.
2. Testing Insert
- correctly adds a word with one character
a) no word in the trie beginning with that character
(adding a new node to the trie)
b) at least one word in the trie begins with that character
(only changing the isWord flag)
- correctly adds a word that has no prefix in common with other
words in the trie. The length of the word is greater than 1.
- correctly adds a word that shares a multiple letter prefix with
other words in the trie. The length of the word is greater than 1.
- does not change the trie if the word to be added is already in
the trie.
3. Testing Check
- gives the appropriate result (returning true or false, or
printing a message) for the following cases:
- The word is not in the trie, and the word is not a prefix of a
word in the trie..
- The word is not in the trie, but is a prefix of a word in the
trie.
- The word is in the trie, and no word that is a prefix of the
given word is in the trie.
- The word is in the trie, and a word that is a prefix of the
given word is in the trie.
4. Testing Print
- prints all the words when none of the words share a prefix (i.e.,
the all begin with different letters)
- prints all the words when some of the words share prefixes.
5. Testing Print given prefix
- gives the appropriate message if no word with the given prefix is
found in the trie
- prints the word if the prefix itself is a word.
- prints all the words that share the prefix
- prefix is one character long
- prefix is multiple characters.
6. Testing Build
- given that insert has been thoroughly tested
- inserts all the words from a file in the following 2 cases:
- one word in the file
- more than one word in the file
- behaves appropriately when we start with a non-empty Lexicon
The assignment specifications did not say what should happen
under this circumstance. Whatever a student decided, it should be
documented and tested.
7. Miscellaneous
- This test plan does not include specific cases for testing the
translation of a character into an array index. The
cases listed above should include the use of letters
'a' and 'z' to ensure that the index conversion method works
correctly at the boundaries of the alphabet.
- The test plan assumes that all input with be of valid types. We
do not test to ensure that the words contain only lower case
letters. If the program allowed upper case and lower case
letters, we should include test cases for that.