1. Consider strings that contain only the characters p, q, r, s and t. a) Find...

Transcribed Image Text:

1. Consider strings that contain only the characters p, q, r, s and t. a) Find a recurrence relation for the number of such strings that contain two consecutive t characters. What are the initial conditions? b) How many such strings of length 4 contain two consecutive t characters? c) Solve the recurrence relation obtained in point a. 2. Use the Master Theorem to get an asymptotic solution (O notation) to the recurrence relation f(n)=8f (n/2) + √n whenever n = 2k, where k is a positive integer greater than 1. 1. Consider strings that contain only the characters p, q, r, s and t. a) Find a recurrence relation for the number of such strings that contain two consecutive t characters. What are the initial conditions? b) How many such strings of length 4 contain two consecutive t characters? c) Solve the recurrence relation obtained in point a. 2. Use the Master Theorem to get an asymptotic solution (O notation) to the recurrence relation f(n)=8f (n/2) + √n whenever n = 2k, where k is a positive integer greater than 1.

Answer rating: 100% (QA)

Answer 1 a Lets define the function Tn as the number of strings of length n that contain two consecutive t characters We can break down the problem into two cases strings that end with t and strings t... View the full answer