# Project #56988 - Algorithms

Given the recurrence relation

T(n) = {T(n-1) + 2T(n-2)    n >= 3

{11                        n = 2

{7                          n = 1

a) show that (1) has the solution T(n) = 3 * 2^n - (-1)^n by mathematical induction.

b) Find a simple function f(n) such that T(n) = theta(f(n)). Here simple means the function is of a simple form, e.g. n^3 rather than 5n^3 - 3n+7. Note that you need to prove both upper bound and lower bound.

---

An array has cells numbereed 0,1,...,n. Starting at cell x, you repeatedly flip coins and move up or down, depending on whether you got heads or tails. (X means increasing on a head). The process stopes when you read 0 or n. The random variable Tx denots the number of flips done before you stop.

a) show that there is a number c < 1 for which Pr[Tx > t] = O(c^t). Using this, show that the infinite sum for E[Tx] converges. (hint: how many times could you go in the same direction without stopping?

b) Find a recurrence relation expressing E[Tx+1 in terms of E[Tx] and E[Tx-1] for 0  < x < n. (Hint: if you are at x, then with equal probability your next location is either x-1 or x + 1)

c) Find the general solution to your recurrence from b.

d) Find a particular solution that matches the requirement that E[T0] = E[Tn] = 0. And show E[Tn/2] = Tehta(n^2). This means you need both an upper and lower bound.

---

(Parameters for linear time selection.) Suppose that

T(n) <= T(an) + T(bn) + cn, for large n

Where a,b,c > 0 and a + b < 1. By following induction we can see that T9n) = O(n), which implies there existis a constant C such that T(n) <= Cn for sufficiently large n. Describe the set of constants C we could get from the induction, in terms of a,b,c.

 Subject Mathematics Due By (Pacific Time) 02/10/2015 12:00 pm
TutorRating
pallavi

Chat Now!

out of 1971 reviews
amosmm

Chat Now!

out of 766 reviews
PhyzKyd

Chat Now!

out of 1164 reviews
rajdeep77

Chat Now!

out of 721 reviews
sctys

Chat Now!

out of 1600 reviews

Chat Now!

out of 770 reviews
topnotcher

Chat Now!

out of 766 reviews
XXXIAO

Chat Now!

out of 680 reviews