0. Define the class of functions Omega(f(n)). 1. Problem 3-2 of CLRS. 2. Suppose you are given strings T[1..n] and P[1..m], with m<=n. You are to find whether P appears as a substring in T, i.e. whether there exists j such that T[j+i]=P[i] for all 1<=i<=m. (a) Give an algorithm from specification. (b) Give a divide and conquer algorithm for solving this problem. Formulate a suitable recurrence and solve it. This algorithm will very likely not run faster than the algorithm in part (a) -- suggesting that divide and conquer doesnt always work better than the obvious algorithm. (Note: in general more credit will be given for faster algorithms, unless you are explicitly told as above). 3. Consider the problem of finding the odd coin out of n coins when you dont know whether the odd coin is heavier or lighter than the rest. You are to identify the odd coin, without necessarily identifying whether the coin is heavier or lighter than the rest. (a) How many instances does this problem have? (b) Is it true that for distinct instances you must reach distinct leaves of your algorithm tree? Explain carefully. (c) Give a lower bound on the number of weighings needed.