1 Crore+ students have signed up on EduRev. Have you? 
Consider the following recurrence:
Which one of the following is true?
( Putting 2so that we can take log. one more step of recurrence can't change the complexcity
Let X^{n} denote the number of binary strings of length n that contain no consecutive 0s.
Which of the following recurrences does X^{n} satisfy?
0 1 2
01 10 11 3
010 011 101 110 111 5
0101 0110 0111 1010 1011 1101 1110 1111 8
So, x_{n} = x_{n}1 + x_{n}2 (For all the strings ending in 1, we get two new strings and for all strings ending in 0, we get a new string. So, the new set of strings for n+1, will have exactly n strings ending in 1)
x_{5} = 8+5 = 13
Let X_{n} denote the number of binary strings of length n that contain no consecutive 0s.
x_{5} = 8+5 = 13
Number of binary strings of length n that contain no consecutive 0s, following will be the required recurrence relation:
T(n) = T(n1) + T(n2) n>2
base condition T(1) = 2 and T(2) = 3
T(1) =2 There will be 2 strings of length 1, i.e 0 & 1
T(2) =3 There will be 3 strings of length 2, i.e. 01,10,11
T(3) = T(1) + T(2) = 2+3 = 5
T(4) = T(3) + T(2) = 5 + 3 = 8
T(5) = T(4) +T(3) = 8 + 5 = 13
When n = 2^{2k} for some k ≥ 0, the recurrence relation
evaluates to :
If we use Master theorem we get option B. But one must know that Matser theorem is used to find the asymptotic bound and not an EXACT value. And in the question here it explicitly says "evaluates to".
The running time of an algorithm is represented by the following recurrence relation:
Which one of the following represents the time complexity of the algorithm?
To, check Master theorem case 3, we need C>0
So using case three of master theorem
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
Recurrence relation for Towers of Hanoi is
T(1) = 1
T(n) = 2 T( n1 ) +1
So Answer should be (D)
Which one of the following correctly determines the solution of the recurrence relation with T(1) =1?
we can take any ε from 01 for example 0.5 which gives whose proof
is given here: http://math.stackexchange.com/questions/145739/provethatlognosqrtn
Let a_{n} represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a_{n} ?
Counting the number of bit strings NOT containing two consecutive 1's. (It is easy to derive a recurrence relation for the NOT case as shown below.)
0 1
00 01 10  3 (append both 0 and 1 to any string ending in 0, and append 0 to any string ending in 1)
000 001 010 100 101  5 (all strings ending in 0 give two strings and those ending in 1 give 1 string)
0000 0001 0010 0100 0101 1000 1001 1010  8
....
a_{n}' = a_{n1}' + a_{n2}' (where an denote the number of bit strings of length n containing two consecutive 1s)
2^{n}  a_{n} = (2^{n1}  a_{n1}) + (2^{n2}  a_{n2})
a_{n} = 2^{n2}(4  2  1) + a_{n1} + a_{n2}
a_{n} = a_{n1} + a_{n2} + 2^{n2}
Consider the following recursive C function.
void get(int n)
{
if (n<1) return;
get (n1);
get (n3);
printf("%d", n);
}
If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?
T(n) = T(n1) + T(n3) + 2, here T(n) denotes the number of times a recursive call is made for input n. 2 denotes the two direct recursive calls.
T(n<=0) = 0
T(1) = 2
T(2) = 4
T(3) = 6
T(4) = 10
T(5) = 16
T(6) = 24
So, answer is 24 + 1 call from main = 25.
Consider the recurrence function
Then T(n) in terms of θ notation is
Using case 1 of master method ,
Consider the following recurrence relation:
Which of the following statements is TRUE?
The average number of key comparisons required for a successful search for sequential search on n items is
Expected number of comparisons
= 1x Probability of first element be x + 2 x Probability of second element be x + .... +n x Probability of last element be x.
Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search. The program is erroneous.
f (int Y[10] , int x) {
int u, j, k;
i= 0; j = 9;
do {
k = (i+ j) / 2;
if( Y[k] < x) i = k; else j = k;
} while (Y[k] != x) && (i < j)) ;
if(Y[k] == x) printf(" x is in the array ") ;
else printf(" x is not in the array ") ;
}
On which of the following contents of Y and x does the program fail?
when it is option C the control will continue to iterate as i=8 and j=9;
again and again i will be assigned k which itself equals 8 as 8+9/2 being stored in an integer type variable, will evaluate to 8
For option A, with X=9 , k will take the following values:
For option D, with X = 10, k will take the following values:
Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search. The program is erroneous.
f (int Y[10] , int x) {
int u, j, k;
i= 0; j = 9;
do {
k = (i+ j) / 2;
if( Y[k] < x) i = k;else j = k;
} while (Y[k] != x) && (i < j)) ;
if(Y[k] == x) printf(" x is in the array ") ;
else printf(" x is not in the array ") ;
}
The correction needed in the program to make it work properly is
if( Y[k] < x) then i = k + 1;
if given element that we are searching is greater then searching will be continued upper half of array
otherwise j = k  1;
lower half.
Take few case in consideration i.e.
1. all elements are same
2. increasing order with no repeatation
3. increasing order with repeatation.
Suppose you are given an array A with 2n numbers.
The numbers in odd positions are sorted in ascending order, that is,
The numbers in even positions are sorted in descending order, that is,
What is the method you would recommend for determining if a given number is in the array?
We can simply use clever indexing to binary search the element in the odd positions, and in the even positions separately.
This will take O(logn) time andO(1) space in the worst case.
A: Sorting using Quicksort will take O(n^{2}) time.
B: Merging will take O(n) time and O(n) space.
C: Binary search only works on a sorted array.
E: Sequential search will take O(n) time.
3 videos7 docs100 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
3 videos7 docs100 tests







