CS 410 Fall 99
Homework 1
Due Thursday, September 2

Reading

• Review CLR Chapter 1. Most of this material should be familiar from CS211/212.
• Review CLR Chapters 3, 5, 6.1-6.4. Most of this material should be familiar from CS280.
• Read CLR Chapters 2, 4, 11, 7.

Written Exercises

1. Assume your computer can perform 10⁹ operations per second.

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

   (b) What if your algorithm takes 10n² operations?

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

2. You might not think the difference between n² 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 n² 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(n^k) for fixed constant k

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

   (c) log_a n = Theta(log_b n) for any positive constants a, b.

4. Rank the following functions by order of growth. That is, find an arrangement g₁,g₂,...,g_n of the functions satisfying g₁ = O(g₂), g₂ = O(g₃), etc.

   n, sqrt n, lg n, lg(lg n), (lg n)², n²/lg n, 100^{sqrt n}, 2ⁿ, n².

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.