Homework 1
The homework is due at the beginning of class on Thursday, March 12.
-
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
-
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.)
- f(n) = 100n + logn, g(n) = n + (logn)2
- f(n) = log(2n), g(n) = log10(10000n)
- f(n) = 10logn, g(n) = log(n5)
- f(n) = (logn)2, g(n) = 100log(n10)
- f(n) = (logn)logn, g(n) = n100
- f(n) = n2, g(n)=23logn
- f(n) = 2n, g(n)=3n
- f(n) = 100
√ n
,
g(n)=5logn
-
Problem 2.4 from [DPV] (Choose from 3 algorithms)
(You can use the Master theorem where applicable.)
-
Problem 2.12 from [DPV] (Printing lines)
(You can use the Master theorem where applicable.)
-
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.