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

Triangles, CM and RN are resp. the medians of triangle ABC and Triangle PQR... CM and RN are resp. the medians of triangle ABC and Triangle PQR.if triangle ABC similar to Triangle PQR TRIANGLE AMC SIMILAR TO PNR

Class 10, chapter permutation & combination ex :4.6 chapter permutation & combination ex :4.6

Factorization, factorize the following algebraic expressions factorize the following algebraic expressions

Statistics, A researcher is investigating the effectiveness of a new medica... A researcher is investigating the effectiveness of a new medication for lowering blood pressure for individuals with systolic pressure greater than 140. For this population, systol

Function evalaution, how do we solve function evaluation f(x) how do we solve function evaluation f(x)

Solving an equation using multiplication and division, Solving an equation ... Solving an equation using Multiplication and Division       A variable is a symbol that represents a number. Usually we use the letters like n , t , or x for variables. For

System of differential equations for the population, Write down the system ... Write down the system of differential equations for the population of both predators and prey by using the assumptions above. Solution We will start off through letting that

What is deductive reasoning, What is Deductive Reasoning ? Geometry is... What is Deductive Reasoning ? Geometry is based on a deductive structure -- a system of thought in which conclusions are justified by means of previously assumed or proved sta

digraph of r, Let R be the relation on S = {1, 3, 6, 9, 27} defined by aRb... Let R be the relation on S = {1, 3, 6, 9, 27} defined by aRb iff a|b. (a) Write down the matrix of R. (b) Draw the digraph of R. (c) Explain whether R is reflexive, irrere

Sas, can you tell me how to find the "x" and the "y" when trying to find if... can you tell me how to find the "x" and the "y" when trying to find if two triangles are smiliar