CS 104 - Introduction to Computer Science Homework #10

1. Word List - Call your program WordArray.java.  Use the partially-filled array algorithms in class to support the following commands:

• add <word> - add the given word <word> to the end of the list
• size - print the size of the list
• list - print the words of the list, one per line
• max - print the lexicographically maximum list word
• min - print the lexicographically minimum list word
• remove <word> - remove the given word <word> from the list, moving later words up one position in the list.
• insert <word> <position> - insert a word at a given position, moving words from that position and later down one position in the list

All commands should have thorough error handling.  You should given appropriate error messages when one tries to remove a non-existent word, insert a word beyond the end of the list, omits a required command token, etc.  Think through all case scenarios.  You can ignore extraneous tokens after valid input.

Start out with any capacity you desire.  When the size of your word list exceeds the capacity, you should create a new, larger array (e.g. twice the capacity), and copy the old array to the new one, and continue using the new one.

2. Insertion Sort - Call your program InsertionSort.java.  This program will read in a list of words (one per line), sort them by a technique called insertion sort, and finally print out the words in lexicographic order.  Insertion sort is a very simple technique.  Assume you have i words sorted in a list.  For word i+1, find the appropriate position for the new word, and insert it (as in the previous exercise), yielding a sorted list of length i+1.  Starting with an empty (trivially sorted) list, insert each of the words in this way.  The result is a sorted list of all the words.  Print out this sorted list of words (one per line).

3. Insertion Sort Analysis - Assume you have a list of i-1 words and you insert word i.  In the worst case, what is the total number of comparisons and assignments you will have to do to insert ...

• ... the first word into a list of 0 words (empty list)?
• ... the second word into a list of 1 word?
• ... the ith word into a list of i-1 words?
• ... the first two words into a list of 0 words?
• ... the first three words into a list of 0 words?
• [Extra credit 10%]... i words into a list of 0 words?