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

Find out the total number people and the total number car, A national park ... A national park remains track of how many people per car enter the park. Today, 57 cars had 4 people, 61 cars had 2 people, 9 cars had 1 person, and 5 cars had 5 people. What is th

what is probability that point will be chosen from triagle, In the adjoini... In the adjoining figure ABCD is a square with sides of length 6 units points P & Q are the mid points of the sides BC & CD respectively. If a point is selected at random from the i

Mss. Ann, I need marketing management sample assignment as a guide I need marketing management sample assignment as a guide

Operation research, Formulate LLP Formulate LLP

Tangent, construction of tangent when center not known construction of tangent when center not known

College Algebra, I am looking for a tutor in College Algebra I am looking for a tutor in College Algebra

Testing the hypothesis equality of two variances, Testing the hypothesis eq... Testing the hypothesis equality of two variances The test for equality of two population variances is based upon the variances in two independently chosen random samples drawn

Smith keeps track of poor work, Smith keeps track of poor work. Often on af... Smith keeps track of poor work. Often on afternoon it is 5%. If he checks 300 of 7500 instruments what is probability he will find less than 20 substandard?

Metric measurement, what is a liter what is a liter

AREA, How do you find the distributive property any faster? How do you find the distributive property any faster?