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

Determine the equation of plane - three dimensional space, Determine the eq... Determine the equation of the plane that consists of the points P = (1, -2, 0), Q = (3, 1, 4) and R = (0, -1, 2). Solution To write down the equation of plane there is a re

Problem, if .77x + x = 8966.60, what is the value of x? if .77x + x = 8966.60, what is the value of x?

3rd grade, All about fractions All about fractions

Quadratic equations by completing the square method, Can we solve the Quadr... Can we solve the Quadratic Equations by completing the square method? if yes explain it.

Solve the recurrence relation, Solve the recurrence relation T ... Solve the recurrence relation T (K) = 2T (K-1), T (0) = 1 Ans: The following equation can be written in the subsequent form:  t n - 2t n-1 =  0  Here now su

Differential equations, particular solution of equation y''''-3y''-4y=2sinx... particular solution of equation y''''-3y''-4y=2sinx

Bar Graphs, How do they work? How do they work?

Show that the function f is one-one but not onto, Consider the function f: ... Consider the function f: N → N, where N is the set of natural numbers, defined by f(n) = n 2 +n+1. Show that the function f is one-one but not onto. Ans: To prove that f is one

Logarithm, what is 8e^3x + 4 = 15 what is 8e^3x + 4 = 15

Regression and correlation analysis on income and ex, regression and correl... regression and correlation analysis on income and expenditure