This is the final version. It is still your responsibility to check back here for any changes or updates.

Required reading: Savitch text Chapter 6, Section 10.1 of Chapter 10, and Chapter 11.

This exercise should be done using only the material from Chapters 1 through 6, Section 10.1 of Chapter 10, and Chapter 11.

Due dates: Check the Announcements.

Note you can do this and take an interview without turning in the assignment, as long as it is before the turnin deadline (and until the deadline is announced it is definitely before the deadline.)

Programming: For this assignment you will do two versions of the same program; one version using arrays as Hw # 3 and one version using vectors as HW #4.

Program interface specification: The program will ask the user for a list of words, entered one per line. The user ends his/her list of words by typing in the character # on a line by itself. there is no limit to the number of words that can be entered.

Words must consist entirely of letter (any mix of uppercase and lowercase); in particular, words cannot contain a hyphen, apostrophe, or any character that is not a letter.

The program echoes the list of words in alphabetical order with the same uppercase and lowercase spelling that the user entered. (Note: the user may enter the words in any order. So they need to be sorted.) Use the selection sort algorithm given in Chapter 6 to do the sorting.

The program then asks the user if the user wants to search for a word in the list.

If the user says yes, then the user is asked to enter a word.

The program tells whether or not the word is in the list and shows the list. If the word is in the list, then that word appears in all uppercase letters. If the word is not in the list, then the location of where the word would be if it were in the list is given.

Below is a sample dialogue:

Enter a list of words (consisting entirely of letters).
End the list by typing a # on a line by itself.

Java
coffee
cappuccino
espresso
Blue berry muffin
Sorry, "Blue berry muffin" is illegal.
Words must consist entirely of letters.
Renter last word: muffin
continue: soda
apple
#

In alphabetical order the words are:
apple
cappuccino
coffee
espresso
Java
muffin
soda

Would you like to search for a word? (y/n): y

Enter a word to search for: java

"java" is on the list:
apple
cappuccino
coffee
espresso
JAVA
muffin
soda

Again? (y/n): y

Enter a word to search for: tea-cakes
Sorry, "tea-cakes" is illegal.
Words must consist entirely of letters.
Renter last word: buns

"buns" is not on the list:
apple
No "BUNS" here
cappuccino
coffee
espresso
Java
muffin
soda

Again? (y/n): n

End of program.

To see how your program should perform, run ArraySearcher.class in the hw3 subdirectory of the assignments directory on sunpal.

Version 1 (This is Hw # 3):
In this version you will use a class called ExpandableArray. The class will have two private instance variables one for an array of Strings and one of type int to indicate the number of array locations in use. The array is a partially filed array that adds elements to an initial segment of the array, as described in the text. Your class ExpandableArray must have the following methods, and can have more methods if you wish:

A default constructor that makes the initial size of the array 10.

A constructor with one int argument for the initial size of the array.

/** Returns true if the array is full */
public boolean full()

/** Adds the newEntry to the array. If the array is full, then the method expand is used to produce a larger array. */
public void add(String newEntry)

/** Replaces the array in the array instance variable with an array of twice the size. All the elements in the old
partial array are copied to the new partial array. */
public void expand()

/** Sorts the partially filled array into alphabetical order */
public void sort()
Use the selection sort algorithm given in Chapter 6 to do the sorting.

/** Returns the String in array index position i. Returns null if i is not an index for a used array position. */
public String at(int i)

/** If target is in the array, returns the first index for an array element that holds target. If target is
not in the array, returns -1. */
public int locate(String target)

Important: You must implement locate with the RECURSIVE binary search algorithm described in Chapter 11. Your program must use locate to search for the words the user enters to see if they are on the list.

Call your program ArraySearcher. Write your program using the two files ExpandableArray.java and ArraySearcher.java. However, when you turn in your program, make ExpandableArray an inner class in the class ArraySearcher so that you have only one file to turn in.

*** Save your copy of this program. You will use it in one or more future assignments ***

Version 2 (This is Hw #4):
Redo the same program using the class Vector instead of the class ArraySearcher.

You will need to write a method to sort a vector of Strings. Use the selection sort algorithm given in Chapter 6 to do the sorting.

You will also need a to write a method similar to the method locate in Version 1. You must implement this method with the RECURSIVE binary search algorithm described in Chapter 11. Your program must use this method to search for the words the user enters to see if they are on the list.

Call your program VectorSearcher.

*** Save your copy of this program. You will use it in a future assignment ***

Last Update: Jan 20, 2003 (by Nakul Verma)