Description
We want to devise a dynamic programming solution to the following problem: there is a string of characters which might have been a sequence of words with all the spaces removed, and we want to nd a way, if any, in which to insert spaces that separate valid English words. For example, theyouthevent could be from \the you the vent", \the youth event" or \they out he vent". If the input is theeaglehaslande, then there’s no such way. Your task is to implement a dynamic programming solution in one of two separate ways (both ways for extra credit):
iterative bottom-up version recursive memoized version
Assume that the original sequence of words had no other punctuation (such as periods), no capital letters, and no proper names - all the words will be available in a dictionary le that will be provided to you.
Let the input string be x = x1x2:::xn. We de ne the subproblem split(i) as that of determining whether it is possible to correctly add spaces to xixi+1:::xn. Let dict(w) be the function that will look up a provided word in the dictionary, and return true i the word w is in it. A recurrence relation for split is given below:
split(i) =
true
if i = n + 1
jn=i[dict(xixi+1:::xj ) ^ split(j + 1)]
otherwise
W
Obviously, split(i) only nds out whether there’s a sequence of valid words or not. Your pro-gram must also nd at least one such sequence.
The program will read a text le from standard input. For example, if you have a Java class named dynProg, the command java dynProg < inSample.txt is what you would use to run your program. The name of the dictionary le should be hardwired in the code. We will be testing your program on a le named \diction10k.txt", and your program will be tested in a directory containing that le. Testing will be much simpler if you can submit your program as a single le (and not a zipped directory).
1
Sample Input
The rst line of input is an integer C. This is followed by C lines, each containing a single string, representing a phrase to be tested.
3
theyouthevent
theeaglehaslande
lukelucklikeslakeslukeducklikeslakeslukelucklickslakesluckducklickslakes
Sample Output
phrase number: 1
theyouthevent
iterative attempt:
YES, can be split
the you the vent
memoized attempt:
YES, can be split
the you the vent
phrase number: 2
theeaglehaslande
iterative attempt:
NO, cannot be split
memoized attempt:
NO, cannot be split
phrase number: 3
lukelucklikeslakeslukeducklikeslakeslukelucklickslakesluckducklickslakes
iterative attempt:
YES, can be split
luke luck likes lakes luke duck likes lakes luke luck licks lakes luck duck licks lakes
memoized attempt:
YES, can be split
luke luck likes lakes luke duck likes lakes luke luck licks lakes luck duck licks lakes
2
Submission
Post a copy of your Java, Python, C, or C++ program to Canvas by midnight of the due date of Friday, March 8.
3
