We want to devise a dynamic programming algorithm for 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 find 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 theres no such way. Your task is to implement a dynamic programming solution in the following ways:

iterative bottom-up version

recursive memoized version

The program will read a text file from standard input. The name of the dictionary file should be hardwired in the code. We will be testing your program on a file named diction10k.txt, and your program will be tested in a directory containing that file.

SAMPLE INPUT:

The first 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

In C, C++, or Python please.

Assume that the original sequence of words had no other punctuation (such as periods), no capital letters, and no proper namesall the words will be available in a dictionary file that will be provided to you. Let the input string be x = x122...In. We define the subproblem split(i) as that of determining whether it is possible to correctly add spaces to Lili+1...In. Let dict(w) be the function that will look up a provided word in the dictionary, and return true if and only if the word w is in it. A recurrence relation is given below: : s true if i=n +1 1 V1=i[dict(tili+1...X;) A split(j +1)] otherwise Obviously, split(i) only finds out whether there's a sequence of valid words or not. Your pro- gram must also find at least one such sequence. Assume that the original sequence of words had no other punctuation (such as periods), no capital letters, and no proper namesall the words will be available in a dictionary file that will be provided to you. Let the input string be x = x122...In. We define the subproblem split(i) as that of determining whether it is possible to correctly add spaces to Lili+1...In. Let dict(w) be the function that will look up a provided word in the dictionary, and return true if and only if the word w is in it. A recurrence relation is given below: : s true if i=n +1 1 V1=i[dict(tili+1...X;) A split(j +1)] otherwise Obviously, split(i) only finds out whether there's a sequence of valid words or not. Your pro- gram must also find at least one such sequence