1. (‡) Prove asymptotic bounds for the following recursion relations. Tighter bounds will receive more marks. You may use the Master Theorem if it applies.

1. C(n) = 3C(n/2) + n

2. G(n) = G(n - 1) + 1/n

3. I(n) = I(n/2) + n/ lg(n)

2. Define a (p,q)-tree as a rooted tree where every internal node has between p and q (inclusive) children. Use the Master Theorem to give asymptotic bounds for the height of the tree. You can assume both p and q are constants with 2 ≤ p ≤ q.

3. (‡) Dominos

A 2 × 10 rectangle filled with ten dominos, and a 2 × 2 × 10 box filled with ten slabs.

1. A domino is a 2×1 or 1×2 rectangle. How many different ways are there to completely fill a 2 × n rectangle with n dominos?

2. A slab is a three-dimensional box with dimensions 1 × 2 × 2, 2 × 1 × 2, or 2 × 2 × 1. How many different ways are there to fill a 2 × 2 × n box with n slabs? Set up a recurrence relation and give reasonable exponential upper and lower bounds.

Posted Date: 3/19/2013 5:13:49 AM | Location : United States

Ask an Expert

Related Discussions:- Prove asymptotic bounds for recursion relations, Assignment Help, Ask Question on Prove asymptotic bounds for recursion relations, Get Answer, Expert's Help, Prove asymptotic bounds for recursion relations Discussions

Write discussion on Prove asymptotic bounds for recursion relations
Your posts are moderated

Write your message here..

Related Questions

Decision-making under conditions of uncertainty, Decision-Making Under Cond... Decision-Making Under Conditions of Uncertainty With decision making under uncertainty, the decision maker is aware of different possible states of nature, but has insufficient

Calculate the instantaneous rate of change of the volume, Assume that the a... Assume that the amount of air in a balloon after t hours is specified by                                             V (t ) = t 3 - 6t 2 + 35 Calculate the instantaneous

#titldifference between cpm n pert operation research pdfe.., difference be... difference between cpm n pert operation research pdfepted#

Complex eigenvalues, It is the last case that we need to take a look at. Th... It is the last case that we need to take a look at. Throughout this section we will look at solutions to the system, x?' = A x? Here the eigenvalues of the matrix A are compl

Combination, nc6:n-3c3=91:4 nc6:n-3c3=91:4

Algebra, prove That J[i] is an euclidean ring prove That J[i] is an euclidean ring

Course work2 , (b) The arity of an operator in propositional logic is the n... (b) The arity of an operator in propositional logic is the number of propositional variables that it acts on – for example, binary operations (e.g, AND, OR, XOR…) act on two propo

Graphing formulas, how do you graph y+3=-x+3x on a TI-83 graphing calculato... how do you graph y+3=-x+3x on a TI-83 graphing calculator?

INDICES, 8^N*2^2N/4^3N 8^N*2^2N/4^3N

Determine the probability - probability example, Consider two bags, A and B... Consider two bags, A and B, with the following contents Bag A Bag B 3 white marbles 4 white marbles 2 red marbles