Homework 1

Due Thursday, September 2

- 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.

- Assume your computer can perform 10
^{9}operations per second.(a) What is the largest problem you can solve in an hour if your algorithm takes 3

^{n}operations on problems of size n?(b) What if your algorithm takes 10n

^{2}operations?(c) ...1000 n lg n operations?

- You might not think the difference between n
^{2}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

^{2}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?

- 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. - Rank the following functions by order of growth. That is, find an arrangement g
_{1},g_{2},...,g_{n}of the functions satisfying g_{1}= O(g_{2}), g_{2}= O(g_{3}), etc.n, sqrt n, lg n, lg(lg n), (lg n)

^{2}, n^{2}/lg n, 100^{sqrt n}, 2^{n}, n^{2}. - CLR 1.3-6 p. 15. Explain why or why not.
- CLR 1.3-7 p. 16.
- CLR 1.4-2 p. 17.
- CLR 3.2-1 p. 52.
- CLR 4.3-3 p. 64.
- CLR 12.1-4 p. 221.