Reading Assignment: Weiss, Chapters 1 - 3

Problems

(Note that the some web browsers do not display mathmatical equations correctly. If you have problems, you should consult the postscript version of this homework.)

1. This problem gives an orthogonal view of comparative running times from that given in lecture. Be sure to look at the patterns in your table when you have completed it.

   For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds. For large entries (say, those that warrant scientific notation), an estimate is sufficient.

   	1 second	1 minute	1 hour	1 day	1 month	1 year
   150 log2 n
   15 n
   n2
   1/4·2n

2. Weiss, p. 62, problem 2.1.

3. Weiss, p. 62, problem 2.2.

4. Weiss, p. 62, problem 2.4.

5. Weiss, p. 62, problem 2.7, part a.

6. 1. Prove that lnn = O(n^e), for any constant e > 0.
   2. Let f(n) be an arbitrary polynomial of degree k, i.e. there exist constants a₀, a₁, ¼, a_k, with a_k ¹ 0 such that f(n) = a₀ + a₁·n + a₂·n² + ¼+ a_k ·n^k. Prove that f(n) = Q(n^k).

7. You are given a set S of N words. Design a utility that can service anagram queries. Given a word as input, an anagram query returns all anagrams of that word that are in the set S. (For example, if the input is CAT, then the outputs might be ACT and CAT. IF the input is SUBESSENTIAL, then the output might be SUITABLENESS.) Describe concisely and precisely the best algorithm you can for the problem. Consider separately the preprocessing of the set S, which is a one-time cost, and the algorithm for servicing an anagram query. What is the worst-case running time of the preprocessing step (as a function of N, the number of words in the set S, and m, the maximum word length), and what is the worst-case running time of an execution of the anagram utility (as a function of N, the number of words in the set S, k, the number of letters in the input word, and n, the number of anagrams of the input word)? Extra credit will be given if your anagram utility has worst-case running time O(mlog(N) + klogk + n).