What's in a query? The space bar on Amit's smart phone is annoyingly small. Due to this when Amit types a query in Google, he often misses all the spaces.

Thus the Google query shows up as a single word with no spaces and only lowercase text characters (e.g. "whatisanalgorithm" instead of "what is an algorithm").

You are the engineer at Google working on the Google search query sanitation group. Your objective is to break such a query string into individual words.

The query string may not even break into individual words that make sense (making this an illegitimate query)! To help with this, you have at your disposal a data structure that contains all permissible words, including all their forms (verbs, tenses, etc.).

This data structure supports an O(1)-time query is Word(word) that answers true or false. Devise a dynamic programming algorithm that will determine if a given single-word- without-space query can be broken down into a legitimate query, and if so, return the resulting multi-word string.

(a) Write a recurrence relation to compute the answer. Argue how this answer contains within it solutions to smaller sub-problems. Briefly justify why your recurrence is correct.

(b) Using your recurrence, design a dynamic programming algorithm to produce a Yes/No" answer to whether the given query can be broken down into words. You may use either a top-down or bottom-up approach.

(c) Extend your solution above so that if a query can be broken down into words, then the algorithm returns those words in order in a list.

For example, "whatisanalgorithm should return "what","is","an","algorithm" 3 . If the query cannot be broken down into words, then your solution should return an empty list. (c) Analyze the running time and space usage of your algorithm in part (c). Extra credit (3+4 points): In many cases it is possible to break down a query multiple ways: in this case your algorithm must favor a query with fewer words (i.e. longer strings).

For example if the query is "amendingconstitution", it can be broken down into "amending constitution" or "am ending constitution". It should return the first. Specify parts (a) and (b) for this problem (to return the breakdown of a query in the fewest number of words).