Homework 1


The homework is due at the beginning of class on Thursday, March 12.
  1. Manipulating log's:
    Convert

          7log3n

    into the form of a polynomial, in other words in the form nc for a constant c.
    Some examples of the correct form are n3, n10, or nlog23
  2. For the following functions,
            is (1) f(n)=O(g(n))?, is (2) g(n)=O(f(n))?, (3) both (1) and (2) are true.
                (All log's are base 2, unless otherwise specified.)
    1. f(n) = 100n + logn, g(n) = n + (logn)2
    2. f(n) = log(2n), g(n) = log10(10000n)
    3. f(n) = 10logn, g(n) = log(n5)
    4. f(n) = (logn)2, g(n) = 100log(n10)
    5. f(n) = (logn)logn, g(n) = n100
    6. f(n) = n2, g(n)=23logn
    7. f(n) = 2n, g(n)=3n
    8. f(n) = 100 n  , g(n)=5logn
  3. Problem 2.4 from [DPV] (Choose from 3 algorithms)
        (You can use the Master theorem where applicable.)
  4. Problem 2.12 from [DPV] (Printing lines)
        (You can use the Master theorem where applicable.)
  5. Solving recurrences:
    Problem 2.5 parts a, c, d, i, j from [DPV]
          You just need to solve them in O() notation (not Θ() notation).
          Where appropriate, you need to express your answer as a polynomial, in other words in the form nc for a constant c.
                For example, if you have a solution in the form 7log3n then you need to reexpress it as in the practice problems,
                but if you have a solution such as O(2n) then that is OK as is.
          You need to show your work for solving the recurrence.
          You can use the Master Theorem to check your work, but you will
          get zero credit if you just apply it without showing work for solving the recurrence.
          You might want to do the other parts as practice.