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.