## CS 151 - Introduction to Data Structures

### Recursion and the Word Reduction problem

The "word reduction" problem is as follows: given an english word can you remove one letter and still have an english word. Further, can you do this repeatedly until only a 2 letter word remains? If you can do so, output a "yes", otherwise output "no" (true or false would also be OK).

For example, the word "cored" can be reduced as follows: core, ore, or. Likewise "head" can be reduced (had, ad) but "flawed" cannot be reduced (you can do awed, awe, we but sadly you never get there as lawed is not a word).

In this assignment you are to write a word reduction program that determines if a word (or words) provided on the command line are reducable. For instance, suppose that the main function for your program in in the file Reduction.java:
```		java Reduction core head flawed
core -- yes
flawed -- no
```
The output of you rprogram need no match this sample, but the answers must be easily recognizable.

For this program you will need a function to determining a string is an english word. For instance you might have an method like
```boolean isInEnglish(String aString)
```
which returns true if the string aString is in the english language and false otherwise.

```	/home/gtowell/Public/151/A06/wordsBigLC.txt
```
which is a list of about 200,000 english words (it is essentially the Scrabble dictionary). This file is organized similarly to janeoneword.txt (one word per line) so your experience reading that file should help you here.

Read the words file into a data structure convenient for use in the isInEnglish method. Improtantly, the isInEnglish method must run in O(1) time.

Another function you will need is one that removes a specified character from a string. Rather than having you struggle with doing so, here it is:

```		/*
* Remove the nth letter from a string
* @param n the index of the char to remove
* @param s the string to remove from
* @return a string, one letter shorter.  if n is
* out of bound, just return the string without its last letter
*/
String removeNchar(int n, String s) {
if (s==null) { return s; }
if (n>0 && n<s.length()-1) {
return s.substring(0,n)+s.substring(n+1);
}
if (n==0)
return s.substring(1);
return s.substring(0, s.length()-1);
}
```

### Requirements

The program must:
• Handle all exceptions gracefully.
• Take a set of words to check for reducability from the command line.
• Be able to check if a word is in english based on its presence in the file wordsBigLC.txt
• Read the file wordsBigLC.txt at most once
• Determine if a word is in english in O(1) time (n is the number of words in the dictionary)
• Return "yes" or "no" (or True/False) for each word to be checked depending on whether there exists a reduction of that word.
• Use recursion with backtracking to search for a reduction.

### What to Turn In

1. All code your wrote or edited, well commented
2. README with the usual information. This file should follow the format of this sample README (https://cs.brynmawr.edu/cs151/README.txt) Within the README file, include a brief (max 1 paragraph) reflection on what went well and/or poorly and why.
3. A "script" file (see assignment 4, and lab 3, Sep 14 ) that shows the output of your program on a representative set of inputs. This file need not be large. Instead of a separate file you might just use cut and paste to put output into your README file.

#### Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer.

The following steps for submission assume that you created a project named AssignmentN in the directory /home/YOU/cs151/

1. For this assignment N=6
2. Put the files described in the "What to turn section" into the project directory
3. Go to the directory /home/YOU/cs151
4. Enter /home/gtowell/bin/submit -c 151 -p N -d AssignmentN