cs151 - Recursion

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).

Task

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
		head -- 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.

To help you with this task, I provide the file

	/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

All code your wrote or edited, well commented
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.
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/

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

For more on using the submit script click here