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