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

What to Hand In

The assignment has two due dates. The first is Wednesday Nov 2 prior to 8am. The second is Wednesday Nov 9, prior to midnight.

For Nov 2

30% of the grade
Send email to me -- or slide under my door -- a one page (max) English language description of each of the methods believe you will write to complete this assignment. Do not write code. You may phrase your descriptions as pseudocode if that makes you comfortable, but I would prefer plain english. Be precise. I expect that some of your instructions will need adjustment when you actually write code. That is OK. This part of the assignment will be graded on the basis of instruction clarity and plausible correctness. Your description should include the isInEnglish function.

I encourage you to read your instructions out loud to yourself and try to do exactly what you instructions say to do. (I will.) This may be hand written or typed.

I will do my best to get you feedback by Sunday night so that you will have my comments on your plan when you start writing code.

For Nov 9

70% of the grade
The actual programming assignment. I am aware that the midterm is on Nov 3. Instructions for submission follow the usual pattern and are given at the end of this web page.

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 reducible. For instance, suppose that the main function for your program is in the file Reduction.java:

		java Reduction core head flawed 
		core -- yes
		head -- yes
		flawed -- no

The output of your program need not match this sample, but the answers must be easily recognizable.

For this program you will need two utility methods. First, a method that determines if 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 do this task, you need a list of English words. One is available at

	https://cs.brynmawr.edu/cs151/Data/Hw7/words.txt

This is a list of about 200,000 english words (it is essentially the Scrabble dictionary). This file is organized identically to the Gibbon and Scott texts of homework 6, so your experience with that homework should help.

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

The second utility method you will need is one that removes a specified character from a string. Rather than having you struggle with doing so (or copy something off the web), 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 bounds, 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 reducibility from the command line.
Be able to check if a word is in english based on its presence in the file words.txt
Read the file words.txt exactly 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 previous assignments and labs) that shows the output of your program on a representative set of inputs. This file need not be large.

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=7
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