CS 410 Fall 99
Homework 1
Due Thursday, September 2


Written Exercises

  1. Assume your computer can perform 109 operations per second.

    (a) What is the largest problem you can solve in an hour if your algorithm takes 3n operations on problems of size n?

    (b) What if your algorithm takes 10n2 operations?

    (c) ...1000 n lg n operations?

  2. You might not think the difference between n2 and n lg n is such a big deal, but consider this. The human genome is a sequence of roughly 3.5 billion nucleotides, each of which is one of four types A,C,G,T. Representing each of A,C,G,T as a string of 2 bits, the entire genome string would take up roughly .875 gigabytes of storage, thus would fit comfortably on a laptop hard disk.

    (a) Say you wanted to analyze the genome using the computer of exercise 1 running a naive string matching algorithm known to take n2 operations on inputs of length n. Comment on the feasibility of this.

    (b) Suppose that by using a more appropriate data structure, your algorithm could perform the same task using only n lg n operations on inputs of length n. What then?

  3. Prove the following facts:

    (a) (n choose k) = Theta(nk) for fixed constant k

    (b) lg (n!) = Theta(n lg n) (Hint: use Stirling's formula)

    (c) loga n = Theta(logb n) for any positive constants a, b.

  4. Rank the following functions by order of growth. That is, find an arrangement g1,g2,...,gn of the functions satisfying g1 = O(g2), g2 = O(g3), etc.

    n, sqrt n, lg n, lg(lg n), (lg n)2, n2/lg n, 100sqrt n, 2n, n2.

  5. CLR 1.3-6 p. 15. Explain why or why not.
  6. CLR 1.3-7 p. 16.
  7. CLR 1.4-2 p. 17.
  8. CLR 3.2-1 p. 52.
  9. CLR 4.3-3 p. 64.
  10. CLR 12.1-4 p. 221.