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