300+ REAL TIME Data Structures & Algorithms Objective Questions & Answers 2023

250+ TOP MCQs on Matrix Multiplication using Recursion and Answers

Data Structures & Algorithms Multiple Choice Questions on “Matrix Multiplication using Recursion”.

1. If Matrix A is of order X*Y and Matrix B is of order M*N, then what is the order of the Matrix A*B given that Y=M?
a) Y*N
b) X*M
c) X*N
d) Y*M
Answer: c
Clarification: The Matrix A*B is of order X*N as it is given that Y=M i.e. number of columns in Matrix A is equal to total number of rows in matrix B. So the Matrix A*B must have X number of rows and N number of columns.

2. How many recursive calls are there in Recursive matrix multiplication through Simple Divide and Conquer Method?
a) 2
b) 6
c) 9
d) 8

Answer: d
Clarification: For the multiplication two square matrix recursively using Simple Divide and Conquer Method, there are 8 recursive calls performed for high time complexity.

3. What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?
a) O(n)
b) O(n²)
c) O(n³)
d) O(n!)

Answer: c
Clarification: The time complexity of recursive multiplication of two square matrices by the Divide and Conquer method is found to be O(n³) since there are total of 8 recursive calls.

4. What is the time complexity of matrix multiplied recursively by Strassen’s Method?
a) O(n^log7)
b) O(n²)
c) O(n³)
d) O(n!)

Answer: a
Clarification: The time complexity of recursive multiplication of two square matrices by Strassen’s Method is found to be O(n^log7) since there are total 7 recursive calls.

5. How many recursive calls are there in Recursive matrix multiplication by Strassen’s Method?
a) 5
b) 7
c) 8
d) 4

Answer: b
Clarification: For the multiplication two square matrix recursively using Strassen’s Method, there are 7 recursive calls performed for high time complexity.

6. Matrix A is of order 3*4 and Matrix B is of order 4*5. How many elements will be there in a matrix A*B multiplied recursively.
a) 12
b) 15
c) 16
d) 20

Answer: b
Clarification: The resultant matrix will be of order 3*5 when multiplied recursively and therefore the matrix will have 3*5=15 elements.

7. If Matrix X is of order A*B and Matrix Y is of order C*D, and B=C then the order of the Matrix X*Y is A*D?
a) True
b) False

Answer: a
Clarification: Given that B=C, so the two matrix can be recursively multiplied. Therefore, the order of the Matrix X*Y is A*D.

8. What is the time complexity of the fastest known matrix multiplication algorithm?
a) O(n^log7)
b) O(n^2.37)
c) O(n³)
d) O(n!)

Answer: b
Clarification: The Coppersmith-Winograd algorithm multiplies the matrices in O(n^2.37) time. Several improvements have been made in the algorithm since 2010.

9. Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?
a) True
b) False

Answer: a
Clarification: Since The Coppersmith-Winograd algorithm multiplies the matrices in O(n^2.37) time. The time complexity of recursive multiplication of two square matrices by Strassen’s Method is found to be O(n^2.80). Therefore, Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity.

and Answers.

250+ TOP MCQs on N Queens Problem and Answers

Data Structures & Algorithms Multiple Choice Questions on “N Queens Problem”.

1. In how many directions do queens attack each other?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: Queens attack each other in three directions- vertical, horizontal and diagonal.

2. Placing n-queens so that no two queens attack each other is called?
a) n-queen’s problem
b) 8-queen’s problem
c) Hamiltonian circuit problem
d) subset sum problem

Answer: a
Clarification: Placing n queens so that no two queens attack each other is n-queens problem. If n=8, it is called as 8-queens problem.

3. Where is the n-queens problem implemented?
a) carom
b) chess
c) ludo
d) cards
Answer: b
Clarification: N-queens problem occurs in chess. It is the problem of placing n- queens in a n*n chess board.

4. Not more than 2 queens can occur in an n-queens problem.
a) true
b) false

Answer: b
Clarification: Unlike a real chess game, n-queens occur in a n-queen problem since it is the problem of dealing with n-queens.

5. In n-queen problem, how many values of n does not provide an optimal solution?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: N-queen problem does not provide an optimal solution of only three values of n (i.e.) n=2,3.

6. Which of the following methods can be used to solve n-queen’s problem?
a) greedy algorithm
b) divide and conquer
c) iterative improvement
d) backtracking

Answer: d
Clarification: Of the following given approaches, n-queens problem can be solved using backtracking. It can also be solved using branch and bound.

7. Of the following given options, which one of the following is a correct option that provides an optimal solution for 4-queens problem?
a) (3,1,4,2)
b) (2,3,1,4)
c) (4,3,2,1)
d) (4,2,3,1)

Answer: a
Clarification: Of the following given options for optimal solutions of 4-queens problem, (3, 1, 4, 2) is the right option.

8. How many possible solutions exist for an 8-queen problem?
a) 100
b) 98
c) 92
d) 88
Answer: c
Clarification: For an 8-queen problem, there are 92 possible combinations of optimal solutions.

9. How many possible solutions occur for a 10-queen problem?
a) 850
b) 742
c) 842
d) 724

Answer: d
Clarification: For a 10-queen problem, 724 possible combinations of optimal solutions are available.

10. If n=1, an imaginary solution for the problem exists.
a) true
b) false
Answer: b
Clarification: For n=1, the n-queen problem has a trivial and real solution and it is represented by

11. What is the domination number for 8-queen’s problem?
a) 8
b) 7
c) 6
d) 5

Answer: d
Clarification: The minimum number of queens needed to occupy every square in n-queens problem is called domination number. While n=8, the domination number is 5.

12. Of the following given options, which one of the following does not provides an optimal solution for 8-queens problem?
a) (5,3,8,4,7,1,6,2)
b) (1,6,3,8,3,2,4,7)
c) (4,1,5,8,6,3,7,2)
d) (6,2,7,1,4,8,5,3)

Answer: b
Clarification: The following given options for optimal solutions of 8-queens problem, (1,6,3,8,3,2,4,7) does not provide an optimal solution.

and Answers.

250+ TOP MCQs on Catalan Number using Dynamic Programming

Data Structure Multiple Choice Questions & Answers on “Catalan Number using Dynamic Programming”.

1. Which of the following is NOT a Catalan number?
a) 1
b) 5
c) 14
d) 43

Answer: d
Clarification: Catalan numbers are given by: (2n!)/((n+1)!n!).
For n = 0, we get C0 = 1.
For n = 3, we get C3 = 5.
For n = 4, we get C4 = 14.
For n = 5, we get C3 = 42.

2. Which of the following numbers is the 6th Catalan number?
a) 14
b) 429
c) 132
d) 42

Answer: d
Clarification: Catalan numbers are given by: (2n!)/((n+1)!n!).
First Catalan number is given by n = 0.
So the 6th Catalan number will be given by n = 5, which is 42.

3. Which of the following is not an application of Catalan Numbers?
a) Counting the number of Dyck words
b) Counting the number of expressions containing n pairs of parenthesis
c) Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines
d) Creation of head and tail for a given number of tosses

Answer: d
Clarification: Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines are the applications of Catalan numbers where as creation of head and tails for a given number of tosses is an application of Pascal’s triangle.

4. Which of the following methods can be used to find the nth Catalan number?
a) Recursion
b) Binomial coefficients
c) Dynamic programming
d) Recursion, Binomial Coefficients, Dynamic programming

Answer: d
Clarification: All of the mentioned methods can be used to find the nth Catalan number.

5. The recursive formula for Catalan number is given by Cn = ∑Ci*C(n-i).
Consider the following dynamic programming implementation for Catalan numbers:

#include
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
           ______________________;
     }
     return arr[n-1];
 
}
int main()
{
     int ans, n = 8;
     ans = cat_number(n);
     printf("%dn",ans);
     return 0;
}

Which of the following lines completes the above code?
a) arr[i] = arr[j] * arr[k];
b) arr[j] += arr[i] * arr[k];
c) arr[i] += arr[j] * arr[k].
d) arr[j] = arr[i] * arr[k];

Answer: c
Clarification: The line arr[i] += arr[j] * arr[k] reflects the recursive formula Cn = ∑Ci*C(n-i).

6. Which of the following implementations of Catalan numbers has the smallest time complexity?
a) Dynamic programming
b) Binomial coefficients
c) Recursion
d) All have equal time complexity

Answer: b
Clarification: The time complexities are as follows:
Dynamic programming: O(n²)
Recursion: Exponential
Binomial coefficients: O(n).

7. What is the output of the following code?

#include
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
         arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 8;
     ans = cat_number(n);
     printf("%dn",ans);
     return 0;
}

a) 42
b) 132
c) 429
d) 1430

Answer: c
Clarification: The program prints the 8th Catalan number, which is 429.

8. Which of the following implementations of Catalan numbers has the largest space complexity(Don’t consider the stack space)?
a) Dynamic programming
b) Binomial coefficients
c) Recursion
d) All have equal space complexities

Answer: a
Clarification: The space complexities are as follows:
Dynamic programming: O(n)
Recursion: O(1)
Binomial coefficients: O(1).

9. What will be the value stored in arr[5] when the following code is executed?

#include
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
          arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 10;
     ans = cat_number(n);
     printf("%dn",ans);
     return 0;
}

a) 14
b) 42
c) 132
d) 429

Answer: b
Clarification: The 6th Catalan number will be stored in arr[5], which is 42.

10. Which of the following errors will occur when the below code is executed?

#include
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
           arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 100;
     ans = cat_number(n);
     printf("%dn",ans);
     return 0;
}

a) Segmentation fault
b) Array size too large
c) Integer value out of range
d) Array index out of range

Answer: c
Clarification: The 100th Catalan number is too large to be stored in an integer. So, the error produced will be integer value out of range.(It will be a logical error and the compiler wont show it).

250+ TOP MCQs on Playfair Cipher and Answers

Data Structures & Algorithms Multiple Choice Questions on “Playfair Cipher”.

1. What is the alternative name of playfair cipher?
a) Wadsworth’s cipher
b) Wheatstone playfair cipher
c) Playfair rectangle
d) Wheatstone cipher
View Answer

Answer: b
Clarification: Playfair cipher is also known by the name of Wheatstone playfair cipher. It is because it was discovered by Charles Wheatstone but was promoted by Lord Playfair.

2. Playfair cipher is an example of __________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: b
Clarification: Playfair cipher is a substitution cipher. It falls under the category of poly alphabetic cipher as it uses multiple substitution at different positions in order to cipher the plain text.

3. Encryption in Autokey cipher is done using __________
a) a 5×5 table
b) a 13×2 table
c) vigenere table
d) a 6×6 table

Answer: c
Clarification: Encryption of plain text in playfair cipher is done using a 5×5 table. In this table, all the alphabets of the keyword are arranged row wise by eliminating any duplicates then the remaining letters of the alphabet are placed. One of the alphabet has to be omitted in order to fit all the alphabets in the table.

4. Which of the following correctly defines poly graphic substitution cipher?
a) a substitution based cipher which uses multiple substitutions at different positions
b) a substitution based cipher which uses fixed substitution over entire plain text
c) a substitution based cipher in which substitution is performed over a block of letters
d) a transposition based cipher which uses fixed substitution over entire plain text

Answer: c
Clarification: Poly graphic cipher is a type of substitution cipher in which substitution is performed over a block of letters. Playfair cipher is an example of poly graphic cipher.

5. Which of the following was the first diagram substitution cipher?
a) autokey cipher
b) hill cipher
c) one time pad cipher
d) playfair cipher

Answer: d
Clarification: Poly graphic cipher is a type of substitution cipher in which substitution is performed over a block of letters. In diagram substitution, two adjacent letters are substituted simultaneously. Playfair cipher was the first diagram substitution cipher.

6. Which of the following is hardest to break using frequency analysis?
a) Vigenere cipher
b) Autokey cipher
c) Playfair cipher
d) Rotor cipher
View Answer

Answer: c
Clarification: Out of the given options playfair cipher is the hardest cipher to break using frequency analysis. It is because it does not substitute letters of the word individually but it encrypts them in pairs of two.

7. Playfair cipher is harder to crack than keyword cipher.
a) True
b) False
View Answer

Answer: a
Clarification: Keyword cipher is less secure than playfair cipher. It is due to the fact that keyword cipher is mono alphabetic and thus can be cracked using frequency analysis. But playfair cipher being a poly graphic substitution cipher is harder to break using this method.

8. What will be the plain text corresponding to cipher text “BPKYFS” if playfair cipher is used with keyword as “SECRET” (assuming j is combined with i)?
a) INDIAN
b) WORLD
c) DOLLAR
d) HELLO

Answer: c
Clarification: To decrypt the message we follow the reverse procedure. The table is formed in the same manner. Applying this we get the plain text to be “DOLLAR”.

9. What is the rule for encryption in playfair cipher if the letters in a pair are identical?
a) then that pair is neglected
b) a null is added in between the letters
c) one of the identical letter is replaced by some other letter
d) then both of the letters are replaced by the letter appearing just next in the row

Answer: b
Clarification: In playfair cipher if the letters in a pair are identical then a null is added in between the letters. Any letter can be used as a null as long as that letter is not the one being repeated.

10. What is the rule for encryption in playfair cipher if the letters in a pair appear in same row?
a) they are replaced by the letter appearing immediately below them respectively
b) they are replaced by the letter appearing immediately right to them respectively
c) they are replaced by the letter at the corner of the row
d) that pair is neglected

Answer: b
Clarification: If the letters in a pair appear in same row then they are replaced by the letters appearing immediately right to them respectively. If the element to be replaced appears at the corner of the row then we wrap around to the left side of that row.

11. What will be the ciphered text if the string “” is given as input to the code of playfair cipher with keyword as “SECRET” (assuming j is combined with i)?
a) ZHQAPNPAFR
b) AHQAPNPAFR
c) HAQAPNPAFR
d) QHAAPNPAFR

Answer: b
Clarification: For encrypting the plain text using playfair cipher we use a 5×5 table that is constructed by using keyword. Then we apply rules for encryption in order to get the ciphered text. Table is given as under-

S E C R T
A B D F G
H I K L M
N O P Q U
V W X Y Z

12. What is the rule for encryption in playfair cipher if the letters in a pair appear in same column?
a) they are replaced by the letter appearing immediately below them respectively
b) they are replaced by the letter appearing immediately right to them respectively
c) they are replaced by the letters at the corner of the row
d) that pair is neglected

Answer: a
Clarification: If the letters in a pair appear in the same column then they are replaced by the letters appearing immediately below them respectively. If the element to be replaced appears at the corner of the column then we wrap around to the top side of that column.

13. What is the rule for encryption in playfair cipher if the letters in a pair does not appear in same row or column?
a) they are replaced by the letter appearing immediately below them respectively
b) they are replaced by the letter appearing immediately right to them respectively
c) they are replaced by the letter of the same row at the corner of the rectangle defined by the original pair respectively
d) that pair is neglected
Answer: c
Clarification: If the letters in a pair does not appear in same row or column then they are replaced by the letters of the same row at the corner of the rectangle defined by the original pair respectively. The order of letters should be maintained.

& Algorithms.

250+ TOP MCQs on Set Partition Problem and Answers

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Set Partition Problem”.

1. What is meant by the power set of a set?
a) subset of all sets
b) set of all subsets
c) set of particular subsets
d) an empty set

Answer: b
Clarification: Power set of a set is defined as the set of all subsets. Ex- if there is a set S={1,3} then power set of set S will be P={{},{1},{3}{1,3}}.

2. What is the set partition problem?
a) finding a subset of a set that has sum of elements equal to a given number
b) checking for the presence of a subset that has sum of elements equal to a given number
c) checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result
d) finding subsets with equal sum of elements

Answer: c
Clarification: In set partition problem we check whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such subsets are present then we print true otherwise false.

3. Which of the following is true about the time complexity of the recursive solution of set partition problem?
a) It has an exponential time complexity
b) It has a linear time complexity
c) It has a logarithmic time complexity
d) it has a time complexity of O(n2)
Answer: a
Clarification: Set partition problem has both recursive as well as dynamic programming solution. The recursive solution has an exponential time complexity as it will require to check for all subsets in the worst case.

4. What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
a) O(n)
b) O(sum)
c) O(n²)
d) O(sum*n)

Answer: d
Clarification: Set partition problem has both recursive as well as dynamic programming solution. The dynamic programming solution has a time complexity of O(n*sum) as it as a nested loop with limits from 1 to n and 1 to sum respectively.

5. Set partition problem is an example of NP complete problem.
a) true
b) false

Answer: a
Clarification: Set partition problem takes exponential time when we implement a recursive solution. Set partition problem is known to be a part of NP complete problems.

6. Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity.
a) true
b) false

Answer: b
Clarification: The recursive solution to set partition problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. So dynamic programming solution is faster in terms of time complexity.

7. Which of the following is not true about set partition problem?
a) the recursive solution has a time complexity of O(2n)
b) there is no known solution that takes polynomial time
c) the recursive solution is slower than dynamic programming solution
d) the dynamic programming solution has a time complexity of O(n log n)
View Answer

Answer: d
Clarification: Recursive solution of set partition problem is slower than dynamic problem solution in terms of time complexity. Dynamic programming solution has a time complexity of O(n*sum).

8. Which of the following should be the base case for the recursive solution of a set partition problem?
a)

If(sum%2!=0)
   return false;
if(sum==0)
   return true;

If(sum%2!=0)
   return false;
if(sum==0)
   return true;
if (n ==0 && sum!= 0) 
   return false;

if (n ==0 && sum!= 0) 
    return false;

if(sum
Answer: b
Clarification: In this case, we need to make sure that, the sum does not become 0 and there should be elements left in our array for recursion to happen. Also if the sum of elements of the set is an odd number then that set cannot be partitioned into two subsets with an equal sum so under such a condition false should be returned. 
 
 
9. What will be the output for the given code?


#include  
#include  
bool func1(int arr[], int n, int sum) 
{ 
    if (sum == 0) 
	return true; 
    if (n == 0 && sum != 0) 
	return false; 
    if (arr[n-1] > sum) 
	return func1(arr, n-1, sum); 
    return func1(arr, n-1, sum) || func1(arr, n-1, sum-arr[n-1]); 
} 
bool func (int arr[], int n) 
{ 	
	int sum = 0; 
	for (int i = 0; i < n; i++) 
	sum += arr[i]; 	
	if (sum%2 != 0) 
	return false; 
	return func1 (arr, n, sum/2); 
} 
int main() 
{ 
    int arr[] = {4,6, 12, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    if (func(arr, n) == true) 
	printf("true"); 
    else
	printf("false"); 
    return 0; 
}







a) true
b) false
c) 4 6 2
d) 12

Answer: a
Clarification: The given code represents the recursive approach of solving the set partition problem. The code checks whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such a partition is possible then we print true otherwise false. In this case true should be printed. 
10. What will be the output for the given code?







#include 
bool func (int arr[], int n) 
{ 
	int sum = 0; 
	int i, j; 
	for (i = 0; i < n; i++) 
	sum += arr[i];
	if (sum%2 != 0) 
	return false; 
	bool partition[sum/2+1][n+1]; 
	for (i = 0; i <= n; i++) 
	partition[0][i] = true; 
	for (i = 1; i <= sum/2; i++) 
	partition[i][0] = false;	 
	for (i = 1; i <= sum/2; i++) 
	{ 
	    for (j = 1; j <= n; j++) 
	    { 
		partition[i][j] = partition[i][j-1]; 
		if (i >= arr[j-1]) 
		partition[i][j] = partition[i][j] || partition[i - arr[j-1]][j-1]; 
	    }		 
	}	 
	return partition[sum/2][n]; 
}	
int main() 
{ 
    int arr[] = {3, 3, 4, 4, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    if (func(arr, n) == true) 
	printf("true"); 
    else
	printf("false"); 
    return 0; 
}







a) true
b) false
c) 0
d) error

Answer: b
Clarification: The given code represents the dynamic programming approach of solving set partition problem. The code checks whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. If such a partition is possible then we print true otherwise false. In this case, false should be printed. 
11. What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
a) O(n log n)
b) O(n²)
c) O(2ⁿ)
d) O(sum*n)

Answer: d
Clarification: The auxiliary space complexity of set partition problem is required in order to store the partition table. It takes up a space of n*sum, so its auxiliary space requirement becomes O(n*sum).
 & Algorithms.
 and Answers.

250+ TOP MCQs on Uniform Binary Search and Answers

Data Structure Multiple Choice Questions on “Uniform Binary Search”.

1. In which of the cases uniform binary search fails compared to binary search?
a) A table lookup is generally faster than an addition and a shift
b) Many searches will be performed on the same array
c) Many searches will be performed on several arrays of the same length
d) Complexity of code

Answer: d
Clarification: Uniform binary search code is more complex to implement than binary search as it involves mid points to be computed in hand before search.

2. Which of the following is a suitable lookup table that can be used in the uniform binary search?(N is the number of elements in the array and the delta array is global)
a)

public static void make_delta(int N) 
{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N + half) / power;
       } 
       while (delta[i++] != 0);
}

public static void make_delta(int N) 
{
       int power = 0;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N + half) / power;
       } 
       while (delta[i++] != 0);
}

public static void make_delta(int N) 
{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power >>= 1;
            delta[i] = (N + half) / power;
       }
       while (delta[i++] != 0);
}

public static void make_delta(int N) 
{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N - half) / power;
       } 
       while (delta[i++] != 0);
}

Answer: a
Clarification: This provides a single lookup index and the values are dependent on the the number of elements(N) in the array.

3. Given delta[4] is a global array and number of elements in the sorted array is 10, what are the values in the delta array?
a) 4, 3, 1, 0
b) 5, 3, 1, 0
c) 4, 2, 1, 1
d) 5, 2, 1, 1

Answer: b
Clarification: Trace with respect to the make_delta function, always note that the last element is always 0.

4. Choose the appropriate code snippet that performs uniform binary search.
a)

public static int unisearch(int key) 
{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i += delta[++j];
                else
                    i -= delta[++j];
            }
       }
}

public static int unisearch(int key) 
{
       int i = delta[1] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i -= delta[++j];
                else
                    i += delta[++j];
            }
       }
}

public static int unisearch(int key) 
{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i -= delta[++j];
                else
                    i += delta[++j];
            }
       }
}

public static int unisearch(int key) 
{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i += delta[++j];
                else
                    i += delta[++j];
            }
       }
}

Answer: c
Clarification: Unlike the usual binary search which a low, high and a mid variable and every time comparing the key with the mid value, the comparing index is obtained from the lookup delta table, choosing the left or right side of the array is same as with the normal binary search.

5. What is the time complexity of uniform binary search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)

Answer: b
Clarification: With every iteration we are dividing the array into two parts(though not equal halves), the complexity remains same as the normal binary search.

6. Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17 and delta = {5,3,1,0}
How many key comparisons are made?(exclude the comparison used to decide the left or right sub array)
a) 4
b) 3
c) 5
d) 6
Answer: b
Clarification: Tracing with the above code, comparison #1: i=4, comparison #2: i=7, comparison #3: i=8

7. How can Jump Search be improved?
a) Start searching from the end
b) Begin from the kth item, where k is the step size
c) Cannot be improved
d) Step size should be other than sqrt(n)
Answer: b
Clarification: This gives a very slight improvement as you are skipping the first k elements.

8. Which of the following false about Jump Search?
a) Jump Search is better than Linear Search
b) Useful when jumping back is more costly than jumping forward
c) Jump Search is worse than Binary Search
d) Jump search starts from the index 0 even though specified index is k

Answer: d
Clarification: Linear search has O(n) complexity and Binary search has O(logn) complexity, in Jump search you have to jump backwards only once, hence it is preferable if jumping backwards is costly. Jump search starts from index k (specified index) and searches for the element. It won’t start searching from index 0.

contest