Q1) The space bar has stopped working on Katt's cellphone, so that now the words in his mail messages all run together with no spaces. Actually, the punctuation marks aren't working either.

So Katt wishes you to create an algorithm that, given a string X, determines efficiently how many ways X can be broken up into a sequence of words. You may use Katt's word tester as a "black box" subroutine, so that given a pair i and j ≥ i, you can test in constant time whether xixi+1 · · · xj is a valid word.
Also analyze the running time of your algorithm.