Mini #1, 15451 Spring 2006
                 ==========================

This mini is due via *email* to your TA, by midnight Tuesday January
24th.  Please use the subject line "15-451 MINI #1" in your email.
(The TA email addresses are dgolovin AT cs.cmu.edu, and leak AT cs.cmu.edu.)

Problem 1: For each pair <f,g> of functions below, list which of the
following are true: f(n) = o(g(n)), f(n) = Theta(g(n)), or g(n) =
o(f(n)).

   (a) f(n) = n^n, g(n) = n!

   (b) f(n) = n^2, g(n) = n*(lg(n))^2.  (i.e. n log squared n)

   (c) f(n) = 2^(sqrt(log_2(n))),  n^(1/10)

Problem 2: Alice and Bob have saved up $10000 in the form of
pennies. They deposit this money into a savings account at a bank that
pays 3% interest, compounded annually. How much will be in the account
after 30 years?

Problem 3: Charlie manages the security of a network. It has to be
said that he does this rather badly. He sets up a system in which a
valid password consists of a string of length n from the alphabet
0...9 that contains exactly two 0s.  How many valid passwords are
there of length n?

Problem 4: In big-O notation, what is the running time of an algorithm
described by the recurrences:

  (a)  T(n) = 16 T(n/2) + 128 n
  (b)  T(n) = 16 T(n/4) + 128 n^2
  (c)  T(n) = 16 T(n/4) + 128 n^3