Recurrences

Question 1

Let an represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for an?

A
an-2 + an-1 + 2n-2
B
an-2 + 2an-1 + 2n-2
C
2an-2 + an-1 + 2n-2
D
2an-2 + 2an-1 + 2n-2
Question 1 Explanation: 
For string of length 1, there is '0' consecutive 1's.
So, a1 = 0
For string of length 2,
a2 = 1
Similarly, a3 = 3
a4 = 8
Only (A) will satisfy the above values.
Question 2
Suppose c = 〈c[0], ... , c[k – 1]〉 is an array of length k, where all the entries are from the set {0, 1}. For any positive integers a and n, consider the following pseudocode.
DOSOMETHING (c, a, n)
z ← 1
for i ← 0 to k – 1
do z ← z2 mod n
if c[i] = 1
then z ← (z × a) mod n
return z
If k = 4, c = 〈1, 0, 1, 1〉, a = 2 and n = 8, then the output of DOSOMETHING(c, a, n) is
A
0
B
1
C
2
D
3
Question 3

The equality above remains correct if X is replace by
A
Only I
B
Only II
C
I or III or IV but not II
D
II or III or IV but not I
Question 4

Let xn denote the number of binary strings of length n that contain no consecutive 0s.

Which of the following recurrences does xn satisfy?

A
xn = 2xn-1
B
xn = x⌊n/2⌋+1
C
xn = x⌊n/2⌋+n
D
xn = xn-1+xn-2
Question 4 Explanation: 
xn = number of binary strings of length n that contains non-consecutive 0’s.
⇒ Let us consider n=1
Possible binary strings: 0, 1
So, x1 = 2
⇒ For n = 2;
Possible strings are,
010
110
111
011
101
So, x3 = 5
⇒ For n=4,
Possible strings are
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
0 1 1 0
0 1 0 1
1 0 1 0
1 1 1 1

So,
x4=8,
Hence, for all values of x4 above only option (D) satisfies.
Question 5

Let xn denote the number of binary strings of length n that contain no consecutive 0s.

The value of x5 is

A
5
B
7
C
8
D
16
Question 5 Explanation: 
From above question we have found that equation,
xn = xn-1 + xn-2
satisfies.
And also we have found the value of x4 and x3 for the above equation.
So, according to the equation the value of x5 will be,
x5 = x3 + x4
= 5 + 8
= 13
Hence , none of the given option is correct.
Question 6

The recurrence equation

   T(1) = 1
   T(n) = 2T(n - 1) + n, n ≥ 2 

evaluates to

A
2n+1 – n – 2
B
2n – n
C
2n+1 – 2n – 2
D
2n + n
Question 6 Explanation: 
T(1) =1
T(n) = 2T(n-1) + n
T(2) = 2T(1) + 2 = 2 + 2 = 4
T(3) = 2T(2) + n = 2(4) + 3 = 11
T(4) = 2T(3) + 4 = 22 + 4 = 26
Let check with the options:
Option A:
n=4
24+1 - 4 - 2
32 - 6
26 (✔️)
Option B:
n=4
2n-n
24-4
12(✖️)
Option C:
n=4
24+1 - 2(4) - 8
32 - 10
22(✖️)
Option D:
n=4
2n - n
24 - 4
12(✖️)
Question 7

Consider the following recurrence relation

T(1) = 1 
T(n+1) = T(n) + ⌊√n+1⌋ for all n≥1 

The value of T(m2) for m ≥ 1 is

A
B
C
D
Question 7 Explanation: 

Considering floor value for square root of numbers.
Successive root number of numbers are in the series 3, 5, 7, ... like 3 numbers from 1... 4, 5 numbers 5-9 and so on.
Question 8

The solution to the recurrence equation T(2k) = 3 T(2k-1) + 1, T(1)=1, is:

A
B
C
D
Question 8 Explanation: 
T(2k) = 3T(2k-1) + 1
T(1)=1
k=0; T(1) = 3T(2-1)+1
k=1; T(2) = 3T(20)+1 = 3(1)+1 = 4
k=2; T(4) = 3T(21)+1 = 3(4)+1 = 13
k=3; T(8) = 3T(22)+1 = 3(13)+1 = 40
k=4; T(16) = 3T(23)+1 = 3(40)+1 = 121
Simply go through the options.
Option B:
k=4 ⇒ (34+1-1)/2
⇒ (243-1)/2
⇒ 121
Question 9

The Fibonacci sequence {f1,f2,f3,...,fn} is defined by the following recurrence:

   fn+2 = fn+1 + fn, n ≥ 1; f2=1 : f1=1 

Prove by induction that every third element of the sequence is even.

A
Theory Explanation.
Question 10

For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1.

Then T(n) is

A
θ(loga logb n)
B
θ(logb loga n)
C
θ(log2 log2 n)
D
θ(logab n)
Question 10 Explanation: 
T(n) = T(n1/a+1, T(b) = 1
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
Question 11

(a) Use the patterns given to prove that


(You are not permitted to employ induction)

(b) Use the result obtained in (a) to prove that

A
Theory Explanation.
Question 12
For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:

Which one of the following options is correct about the recurrence T(n)?
A
B
C
D
Question 12 Explanation: 
There are 12 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access