Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Generating Subsets”.

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) empty set

Answer: b
Clarification: Power set of a set is defined as the set of all subsets. Ex- S={1,2} then P={{},{1},{2}{1,2}}.

2. Number of elements in the power set of set S={1,2,3} will be?
a) 2
b) 4
c) 6
d) 8

Answer: d
Clarification: Power set of a set is defined as the set of all subsets. Number of elements in the power set of a set having n elements is given as 2ⁿ. Thus, here number of elements will be 2³=8.

3. Number of elements in the power set of set S={1,2,2} will be?
a) 2
b) 4
c) 6
d) 8

Answer: c
Clarification: For finding the number of elements in the power set of the given set we need to remove duplicates. So we will be left with 6 unique elements which will be P={{},{1},{2},{1,2},{2,2},{1,2,2}}.

4. Choose the correct statement for the following code segment?

bool check (int N)
{
    if( N & (1 << i) )
        return true;
    else
        return false;
}

a) function returns true if N is odd
b) function returns true if N is even
c) function returns true if ith bit of N is set
d) function returns false if ith bit of N is set

Answer: c
Clarification: As the value of 1 << i is 2ⁱ so the given function checks whether the i^th bit of N is set or not. If it is set then the function returns true.

5. What will be the output for the following code?

#include  
#include  
void PowerSet(char *set, int set_size) 
{ 
	unsigned int pow_size = pow(2, set_size); 
	int count, j; 	
	for(count = 0; count < pow_size; count++) 
	{ 
	     for(j = 0; j < set_size; j++) 
	     { 
 
		if(count & (1<<j)) 
			printf("%c", set[j]); 
	     } 
	     printf(","); 
	} 
} 
int main() 
{ 
	char strset[] = {'a','b','c'}; 
	PowerSet(strset, 3); 
	return 0; 
}

a) a,b,ab,c,ac,bc,abc,
b) a,b,ab,c,ac,bc,abc
c) ,a,b,ab,c,ac,bc,abc,
d) ,abc,bc,ac,c,ab,b,a,
View Answer

Answer: c
Clarification: The given code prints the elements of power set of the given set strset[]. It uses binary counter of appropriate length in order to print corresponding subsets of the given set.

6. What will be the time complexity of the following code?

#include  
#include  
void PowerSet(char *set, int set_size) 
{ 
	unsigned int pow_size = pow(2, set_size); 
	int count, j; 	
	for(count = 0; count < pow_size; count++) 
	{ 
	     for(j = 0; j < set_size; j++) 
	     { 
 
		if(count & (1<<j)) 
			printf("%c", set[j]); 
	     } 
	     printf(","); 
	} 
} 
int main() 
{ 
	char strset[] = {'a','b','c'}; 
	PowerSet(strset, 3); 
	return 0; 
}

a) O(n 2ⁿ)
b) O(n²)
c) O(n log n)
d) O(2ⁿ) (n is the size of set)

Answer: a
Clarification: In the given code we have a nested for loop. In this loop the outer loop runs 2ⁿ times and the inner loop runs n times. So the overall time complexity becomes n2ⁿ.

7. What will be the auxiliary space requirement of the following code?

#include  
#include  
void PowerSet(char *set, int set_size) 
{ 
	unsigned int pow_size = pow(2, set_size); 
	int count, j; 	
	for(count = 0; count < pow_size; count++) 
	{ 
	for(j = 0; j < set_size; j++) 
	{ 		
		if(count & (1<<j)) 
			printf("%c", set[j]); 
	} 
	printf(","); 
	} 
} 
int main() 
{ 
	char strset[] = {'a','b','c'}; 
	PowerSet(strset, 3); 
	return 0; 
}

a) O(n)
b) O(1)
c) O(n log n)
d) O(2ⁿ) (n is the size of set)
View Answer

Answer: b
Clarification: The given code prints the elements of power set of the given set strset[]. As this code does not require any extra space for generating the output so its auxiliary space requirement will be O(1).

8. Which of the following code prints the power set of a given set?
a)

#include
using namespace std; 
void Set(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (index == n) 
        { 
		cout << curr << endl; 
		return; 
	} 	
	Set(str, index , curr + str[index]); 
	Set(str, index + 1, curr); 
}
int main() 
{ 
	string str = "ab"; 
    Set(str); 
	return 0; 
}

b)

#include
using namespace std; 
void Set(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (index == n) 
        { 
		cout << curr << endl; 
		return; 
	} 	
	Set(str, index + 1, curr + str[index]); 
	Set(str, index , curr); 
}
int main() 
{ 
	string str = "ab"; 
    Set(str); 
	return 0; 
}

c)

#include
using namespace std; 
void Set(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (index == n) 
        { 
		cout << curr << endl; 
		return; 
	} 	
	Set(str, index + 1, curr + str[index]); 
	Set(str, index + 1, curr); 
}
int main() 
{ 
	string str = "ab"; 
    Set(str); 
	return 0; 
}

d)

#include
using namespace std; 
void Set(string str, int index = 0, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (index == n) { 
		cout << curr << endl; 
		return; 
	} 
	Set(str, index , curr+str); 
	Set(str, index + 1, curr); 
}
int main() 
{ 
	string str = "ab"; 
    Set(str); 
	return 0; 
}

Answer: c
Clarification: In the correct version we are taking two cases for each element. In the first case the element is included in the subset and in the second case it is not included. So in this manner, we find all the subsets of the given set.

9. The number of elements in the power set increases when there are duplicates present in the set.
a) True
b) False

Answer: b
Clarification: In case when duplicates are present in the set then the number of elements in the power set decreases. It is because we remove subsets with identical elements.

10. What of the following code prints the power set of a given set?
a)

#include  
using namespace std; 
void Set(string str, int ind = -1, 
			string curr = "") 
{ 
	int n = str.size(); 
 
	if (ind == n) 
		return; 
	cout << curr << ","; 
	for (int i = ind+ 1; i < n; i++) 
        { 
		curr += str[i]; 
	    Set(str, i, curr); 
		curr.erase(curr.size() - 1); 
	} 
	return; 
} 
int main() 
{ 
	string str = "abc"; 
    Set(str); 
	return 0; 
}

b)

#include  
using namespace std; 
void Set(string str, int ind = -1, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (ind == 0) 
		return; 
	cout << curr << ","; 
	for (int i = ind+ 1; i < n; i++) 
        { 
		curr += str[i]; 
	    Set(str, i, curr); 
		curr.erase(curr.size() - 1); 
	} 
	return; 
} 
int main() 
{ 
	string str = "abc"; 
    Set(str); 
	return 0; 
}

c)

#include  
using namespace std; 
void Set(string str, int ind = -1, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (ind == n) 
		return; 
	cout << curr << ","; 
	for (int i = ind+ 1; i < n; i++) 
        { 
		curr += str[i]; 
	    Set(str, i, curr); 
		curr.erase(curr.size() -2); 
	} 
	return; 
} 
int main() 
{ 
	string str = "abc"; 
    Set(str); 
	return 0; 
}

d)

#include  
using namespace std; 
void Set(string str, int ind = -1, 
			string curr = "") 
{ 
	int n = str.size(); 
	if (ind == n) 
		return; 	
	cout << str << ","; 
	for (int i = ind+ 1; i < n; i++) 
        { 
		curr += str[i]; 
	    Set(str, i, curr); 
		curr.erase(curr.size() - 1); 
	} 
	return; 
} 
int main() 
{ 
	string str = "abc"; 
    Set(str); 
	return 0; 
}

Answer: a
Clarification: In the correct version of the code we are fixing a prefix and generate all corresponding subsets. Then after all subsets with a prefix are generated, we replace last character with one of the remaining character.

Data Structures & Algorithms Multiple Choice Questions on “Bellman-Ford Algorithm”.

1. The Bellmann Ford algorithm returns _______ value.
a) Boolean
b) Integer
c) String
d) Double

Answer: a
Clarification: The Bellmann Ford algorithm returns Boolean value whether there is a negative weight cycle that is reachable from the source.

2. Bellmann ford algorithm provides solution for ____________ problems.
a) All pair shortest path
b) Sorting
c) Network flow
d) Single source shortest path

Answer: d
Clarification: Bellmann ford algorithm is used for finding solutions for single source shortest path problems. If the graph has no negative cycles that are reachable from the source then the algorithm produces the shortest paths and their weights.

3. Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.
a) True
b) False
Answer: a
Clarification: Bellmann Ford algorithm returns true if the graph does not have any negative weight cycles and returns false when the graph has negative weight cycles.

4. How many solution/solutions are available for a graph having negative weight cycle?
a) One solution
b) Two solutions
c) No solution
d) Infinite solutions

Answer: c
Clarification: If the graph has any negative weight cycle then the algorithm indicates that no solution exists for that graph.

5. What is the running time of Bellmann Ford Algorithm?
a) O(V)
b) O(V²)
c) O(ElogV)
d) O(VE)
View Answer

Answer: d
Clarification: Bellmann Ford algorithm runs in time O(VE), since the initialization takes O(V) for each of V-1 passes and the for loop in the algorithm takes O(E) time. Hence the total time taken by the algorithm is O(VE).

6. How many times the for loop in the Bellmann Ford Algorithm gets executed?
a) V times
b) V-1
c) E
d) E-1

Answer: b
Clarification: The for loop in the Bellmann Ford Algorithm gets executed for V-1 times. After making V-1 passes, the algorithm checks for a negative weight cycle and returns appropriate boolean value.

7. Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm.
a) True
b) False
Answer: a
Clarification: The running time of Bellmann Ford Algorithm is O(VE) whereas Dijikstra’s Algorithm has running time of only O(V²).

8. Identify the correct Bellmann Ford Algorithm.
a)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   for each edge (u,v) in E[g]
	do if d[v]>d[u]+w(u,v)
		then return False
   return True

b)

for i=1 to V[g]-1
       for each edge (u,v) in E[g]
	do if d[v]>d[u]+w(u,v)
		then return False
    return True

c)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   for each edge (u,v) in E[g]
	do if d[v]<d[u]+w(u,v)
		then return true
   return True

d)

for i=1 to V[g]-1
	do for each edge (u,v) in E[g]
		do Relax(u,v,w)
   return True

Answer: a
Clarification: After initialization, the algorithm makes v-1 passes over the edges of the graph. Each pass is one iteration of the for loop and consists of relaxing each edge of the graph once. Then it checks for the negative weight cycle and returns an appropriate Boolean value.

9. What is the basic principle behind Bellmann Ford Algorithm?
a) Interpolation
b) Extrapolation
c) Regression
d) Relaxation

Answer: d
Clarification: Relaxation methods which are also called as iterative methods in which an approximation to the correct distance is replaced progressively by more accurate values till an optimum solution is found.

10. Bellmann Ford Algorithm can be applied for _____________
a) Undirected and weighted graphs
b) Undirected and unweighted graphs
c) Directed and weighted graphs
d) All directed graphs

Answer: c
Clarification: Bellmann Ford Algorithm can be applied for all directed and weighted graphs. The weight function in the graph may either be positive or negative.

11. Bellmann Ford algorithm was first proposed by ________
a) Richard Bellmann
b) Alfonso Shimbe
c) Lester Ford Jr
d) Edward F. Moore

Answer: b
Clarification: Alfonso Shimbe proposed Bellmann Ford algorithm in the year 1955. Later it was published by Richard Bellmann in 1957 and Lester Ford Jr in the year 1956. Hence it is called Bellmann Ford Algorithm.

12. Consider the following graph. What is the minimum cost to travel from node A to node C?

a) 5
b) 2
c) 1
d) 3
View Answer

Answer: b
Clarification: The minimum cost to travel from node A to node C is 2.
A-D, cost=1
D-B, cost=-2
B-C, cost=3
Hence the total cost is 2.

13. In the given graph, identify the path that has minimum cost to travel from node a to node f.

a) a-b-c-f
b) a-d-e-f
c) a-d-b-c-f
d) a-d-b-c-e-f

Answer: d
Clarification: The minimum cost taken by the path a-d-b-c-e-f is 4.
a-d, cost=2
d-b, cost=-2
b-c, cost=1
c-e, cost= 2
e-f, cost=1
Hence the total cost is 4.

14. Bellmann Ford Algorithm is an example for ____________
a) Dynamic Programming
b) Greedy Algorithms
c) Linear Programming
d) Branch and Bound

Answer: a
Clarification: In Bellmann Ford Algorithm the shortest paths are calculated in bottom up manner which is similar to other dynamic programming problems.

15. A graph is said to have a negative weight cycle when?
a) The graph has 1 negative weighted edge
b) The graph has a cycle
c) The total weight of the graph is negative
d) The graph has 1 or more negative weighted edges

Answer: c
Clarification: When the total weight of the graph sums up to a negative number then the graph is said to have a negative weight cycle. Bellmann Ford Algorithm provides no solution for such graphs.

Data Structures & Algorithms Multiple Choice Questions on “GCD and LCM using Recursion – 1”.

1. Which of the following is not another name for GCD(Greatest Common Divisor)?
a) LCM
b) GCM
c) GCF
d) HCF

Answer: a
Clarification: : LCM (Least Common Multiple) and GCD are not same. GCM (Greatest Common Measure), GCF (Greatest Common Factor), HCF (Highest Common Factor) are other names for GCD.

2. What is the GCD of 8 and 12?
a) 8
b) 12
c) 2
d) 4

Answer: d
Clarification: GCD is largest positive integer that divides each of the integer. So the GCD of 8 and 12 is 4.

3. If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72?
a) 24
b) 2
c) 3
d) 16

Answer: d
Clarification: As A * B = GCD (A, B) * LCM (A, B). So B = (144 * 8)/72 = 16.

4. Which of the following is also known as GCD?
a) Highest Common Divisor
b) Highest Common Multiple
c) Highest Common Measure
d) Lowest Common Multiple
Answer: a
Clarification: GCM (Greatest Common Measure), GCF (Greatest Common Factor), HCF (Highest Common Factor) and HCF (Highest Common Divisor) are also known as GCD.

5. Which of the following is coprime number?
a) 54 and 24
b) 4 and 8
c) 6 and 12
d) 9 and 28
Answer: d
Clarification: Coprime numbers have GCD 1. So 9 and 28 are coprime numbers. While 54 and 24 have GCD 6, 4 and 8 have GCD 4, 6 and 12 have GCD 6.

6. In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)?
a) Multiplication of A U B terms
b) Multiplication of A ꓵ B terms
c) Multiplication of A*B terms
d) Multiplication of A-B terms

Answer: b
Clarification: In terms of Venn Diagram, the GCD is given by the intersection of two sets. So A ꓵ B gives the GCD. While A U B gives the LCM.

7. What is the GCD according to the given Venn Diagram?

a) 2
b) 3
c) 5
d) 6

Answer: c
Clarification: In terms of Venn Diagram, the GCD is given by the intersection of two sets. So A ꓵ B gives the GCD. While A U B gives the LCM. So here A ꓵ B is 5.

8. What is the GCD of a and b?
a) a + b
b) gcd (a-b, b) if a>b
c) gcd (a+b, a-b)
d) a – b

Answer: b
Clarification: As per Euclid’s Algorithm, gcd (a, b) = gcd (a-b, b) if a > b or gcd (a, b) = gcd (a, b-a) if b > a.

9. What is the GCD of 48, 18, 0?
a) 24
b) 2
c) 3
d) 6

Answer: d
Clarification: GCD is largest positive integer that divides each of the integer. So the GCD of 48, 18, 0 is 6.

10. Is 9 and 28 coprime number?
a) True
b) False

Answer: a
Clarification: Coprime numbers have GCD 1. So 9 and 28 are coprime numbers.

11. If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called?
a) Bezout’s Identity
b) Multiplicative Identity
c) Sum of Product
d) Product of Sum

Answer: a
Clarification: If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then the expression is called Bezout’s Identity and p, q can be calculated by extended form of Euclidean algorithm.

12. Is gcd an associative function.
a) True
b) False

Answer: a
Clarification: The gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).

13. Which is the correct term of the given relation, gcd (a, b) * lcm (a, b) =?
a) |a*b|
b) a + b
c) a – b
d) a / b

Answer: a
Clarification: The gcd is closely related to lcm as gcd (a, b) * lcm (a, b) = |a*b|.

14. Who gave the expression for the probability and expected value of gcd?
a) James E. Nymann
b) Riemann
c) Thomae
d) Euler

Answer: a
Clarification: In the year 1972, James E. Nymann showed some result to show the probability and expected value of gcd.

15. What is the computational complexity of Binary GCD algorithm where a and b are integers?
a) O (log a + log b)²)
b) O (log (a + b))
c) O (log ab)
d) O (log a-b)

Answer: a
Clarification: From the Binary GCD algorithm, it is found that the computational complexity is O (log a + log b)²) as the total number of steps in the execution is at most the total sum of number of bits of a and b.

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Towers of Hanoi using Recursion”.

1. What is the objective of tower of hanoi puzzle?
a) To move all disks to some other rod by following rules
b) To divide the disks equally among the three rods by following rules
c) To move all disks to some other rod in random order
d) To divide the disks equally among three rods in random order
Answer: a
Clarification: Objective of tower of hanoi problem is to move all disks to some other rod by following the following rules-1) Only one disk can be moved at a time. 2) Disk can only be moved if it is the uppermost disk of the stack. 3) No disk should be placed over a smaller disk.

2. Which of the following is NOT a rule of tower of hanoi puzzle?
a) No disk should be placed over a smaller disk
b) Disk can only be moved if it is the uppermost disk of the stack
c) No disk should be placed over a larger disk
d) Only one disk can be moved at a time
Answer: c
Clarification: The rule is to not put a disk over a smaller one. Putting a smaller disk over larger one is allowed.

3. The time complexity of the solution tower of hanoi problem using recursion is _________
a) O(n²)
b) O(2ⁿ)
c) O(n log n)
d) O(n)
Answer: b
Clarification: Time complexity of the problem can be found out by solving the recurrence relation: T(n)=2T(n-1)+c. Result of this relation is found to be equal to 2ⁿ. It can be solved using substitution.

4. Recurrence equation formed for the tower of hanoi problem is given by _________
a) T(n) = 2T(n-1)+n
b) T(n) = 2T(n/2)+c
c) T(n) = 2T(n-1)+c
d) T(n) = 2T(n/2)+n

Answer: c
Clarification: As there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence relation will be given by T(n) = 2T(n-1)+c.

5. Minimum number of moves required to solve a tower of hanoi problem with n disks is __________
a) 2ⁿ
b) 2ⁿ-1
c) n²
d) n²-1

Answer: b
Clarification: Minimum number of moves can be calculated by solving the recurrence relation – T(n)=2T(n-1)+c. Alternatively we can observe the pattern formed by the series of number of moves 1,3,7,15…..Either way it turn out to be equal to 2ⁿ-1.

6. Space complexity of recursive solution of tower of hanoi puzzle is ________
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: b
Clarification: Space complexity of tower of hanoi problem can be found out by solving the recurrence relation T(n)=T(n-1)+c. Result of this relation is found out to be n. It can be solved using substitution.

7. Which of the following functions correctly represent the solution to tower of hanoi puzzle?
a)

void ToH(int n,int a,int b,int c)
{
   If(n>0)
   {
       ToH(n-1,a,c,b);
       cout<<”move a disk from” <<a<<” to”<< c;
       ToH(n-1,b,a,c);
   }
}

b)

void ToH(int n,int a,int b,int c
{
   If(n>0)
   {
       ToH(n-1,a,b,c);
       cout<<”move a disk from” <<a<<” to”<< c;
       ToH(n-1,b,a,c);
   }
}

c)

void ToH(int n,int a,int b,int c)
{
     If(n>0)
     {
         ToH(n-1,a,c,b);
         cout<<”move a disk from” <<a<<” to”<< c;
         ToH(n-1,a,b,c);
     }
}

d)

void ToH(int n,int a,int b,int c)
{
   If(n>0)
   {
       ToH(n-1,b,a,c);
       cout<<”move a disk from” <<a<<” to”<< c;
       ToH(n-1,a,c,b);
   }
}

Answer: a
Clarification: The first recursive call moves n-1 disks from a to b using c. Then we move a disk from a to c. Finally the second recursive call moves n-1 disks from b to c using a.

8. Recursive solution of tower of hanoi problem is an example of which of the following algorithm?
a) Dynamic programming
b) Backtracking
c) Greedy algorithm
d) Divide and conquer

Answer: d
Clarification: The recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.

9. Tower of hanoi problem can be solved iteratively.
a) True
b) False

Answer: a
Clarification: Iterative solution to tower of hanoi puzzle also exists. Its approach depends on whether the total numbers of disks are even or odd.

10. Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be __________
a) 15 seconds
b) 30 seconds
c) 16 seconds
d) 32 seconds

Answer: b
Clarification: Number of moves = 2⁴-1=16-1=15
Time for 1 move = 2 seconds
Time for 15 moves = 15×2 = 30 seconds.

& Algorithms.

Data Structure Multiple Choice Questions & Answers (MCQs) on “Minimum Number of Jumps”.

1. You are given an array of elements where each array element represents the MAXIMUM number of jumps that can be made in the forward direction from that element. You have to find the minimum number of jumps that are required to reach the end of the array. Which of these methods can be used to solve the problem?
a) Dynamic Programming
b) Greedy Algorithm
c) Recursion
d) Recursion and Dynamic Programming

Answer: d
Clarification: Both recursion and dynamic programming can be used to solve minimum number of jumps problem.

2. Consider the following array:
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: The jumps made will be:{1 -> 2 -> 4 -> 9}. So, the number of jumps is three.

3. Consider the following recursive implementation:

#include
#include
int min_jumps(int *arr, int strt, int end)
{
     int idx;
     if(strt == end)
	return 0;
     if(arr[strt] == 0) // jump cannot be made
	return INT_MAX;
     int min = INT_MAX;
     for(idx = 1; idx <= arr[strt] && strt + idx <= end; idx++)
     {
	  int jumps = min_jumps(____,____,____) + 1;
	  if(jumps < min)
	      min  = jumps;
     }
     return min;
}
int main()
{
     int arr[] ={1, 3, 5, 8, 9, 2, 6, 7, 6},len = 9;
     int ans = min_jumps(arr, 0, len-1);
     printf("%dn",ans);
     return 0;
}

Which of these arguments should be passed by the min_jumps function represented by the blanks?
a) arr, strt + idx, end
b) arr + idx, strt, end
c) arr, strt, end
d) arr, strt, end + idx

Answer: a
Clarification: arr, strt + idx, end should be passed as arguments.

4. For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.
a) True
b) False
Answer: a
Clarification: Consider the array {1,2,3,4,5}. It is possible to reach the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}.
In both the cases the number of jumps is 3, which is minimum. Hence, it is possible to reach the end of the array in multiple ways using minimum number of jumps.

5. What is the output of the following program?

#include
#include
int min_jumps(int *arr, int strt, int end)
{
      int idx;
      if(strt == end)
 	 return 0;
      if(arr[strt] == 0) // jump cannot be made
	 return INT_MAX;
      int min = INT_MAX;
      for(idx = 1; idx <= arr[strt] && strt + idx <= end; idx++)
      {
	   int jumps = min_jumps(arr, strt + idx, end) + 1;
	   if(jumps < min)
	     min  = jumps;
      }
      return min;
}
int main()
{
      int arr[] ={1, 2, 3, 4, 5, 4, 3, 2, 1},len = 9;
      int ans = min_jumps(arr, 0, len-1);
      printf("%dn",ans);
      return 0;
}

a) 4
b) 5
c) 6
d) 7

Answer: a
Clarification: The program prints the minimum number of jumps required to reach the end of the array. One way reach the end using minimum number of jumps is
{1 -> 2 -> 4 -> 8 -> 9}. So, the number of jumps is 4.

6. For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.
a) True
b) False

Answer: b
Clarification: Consider the array {1,0,2,3,4}.
In this case, only one element is 0 but it is not possible to reach the end of the array.

7. Consider the following dynamic programming implementation of the minimum jumps problem:

#include
#include
int min_jump(int *arr, int len)
{
     int j, idx, jumps[len];
     jumps[len - 1] = 0;
     for(idx = len - 2; idx >= 0; idx--)
     {
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
		 if(jumps[idx + j] + 1 < tmp_min)
		     tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
     }
     return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

Which of the following “for” loops can be used instead of the inner for loop so that the output doesn’t change?
a) for(j = 1; j < arr[idx] + len; j++)
b) for(j = 0; j < arr[idx] – len; j++)
c) for(j = idx + 1; j < len && j <= arr[idx] + idx; j++)
d) No change is required

Answer: d
Clarification: None of the above mentioned “for” loops can be used instead of the inner for loop. Note, for(j = idx + 1; j < len && j <= arr[idx] + idx; j++) covers the same range as the inner for loop but it produces the wrong output because the indexing inside the loops changes as “j” takes different values in the two “for” loops.

8. What is the time complexity of the following dynamic programming implementation used to find the minimum number of jumps?

#include
#include
int min_jump(int *arr, int len)
{
     int j, idx, jumps[len];
     jumps[len - 1] = 0;
     for(idx = len - 2; idx >= 0; idx--)
     {
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
		 if(jumps[idx + j] + 1 < tmp_min)
		     tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
     }
     return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) None of the mentioned

Answer: c
Clarification: The time complexity of the above dynamic programming implementation is O(n²).

9. What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps?

#include
#include
int min_jump(int *arr, int len)
{
     int j, idx, jumps[len];
     jumps[len - 1] = 0;
     for(idx = len - 2; idx >= 0; idx--)
     {
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
		 if(jumps[idx + j] + 1 < tmp_min)
		     tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
     }
     return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(5)

Answer: b
Clarification: The space complexity of the above dynamic programming implementation is O(n).

10. What is the output of the following program?

#include
#include
int min_jump(int *arr, int len)
{
      int j, idx, jumps[len];
      jumps[len - 1] = 0;
      for(idx = len - 2; idx >= 0; idx--)
      {	
	     int tmp_min = INT_MAX;
	     for(j = 1; j <= arr[idx] && idx + j < len; j++)
	     {
		   if(jumps[idx + j] + 1 < tmp_min)
		      tmp_min = jumps[idx + j] + 1;
	     }
	     jumps[idx] = tmp_min;
      }
      return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

a) 7
b) 8
c) 9
d) 10

Answer: b
Clarification: The program prints the minimum jumps required to reach the end of the array, which is 8 and so the output is 8.

11. What is the output of the following program?

#include
#include
int min_jump(int *arr, int len)
{
      int j, idx, jumps[len];
      jumps[len - 1] = 0;
      for(idx = len - 2; idx >= 0; idx--)
      {	
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
	        if(jumps[idx + j] + 1 < tmp_min)
		  tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
      }
      return jumps[0];
}
int main()
{
      int arr[] ={9, 9, 9, 9, 9, 9, 9, 9, 9},len = 9;
      int ans = min_jump(arr,len);
      printf("%dn",ans);
      return 0;
}

a) 1
b) 6
c) 2
d) 7

Answer: a
Clarification: The program prints the minimum jumps required to reach the end of the array, which is 1 and so the output is 1.

Data Structures & Algorithms Multiple Choice Questions on “Transposition”.

1. What is the meaning of cipher in computer terminology?
a) an algorithm that performs encryption
b) an algorithm that generates a secret code
c) an algorithm that performs encryption or decryption
d) a secret code

Answer: c
Clarification: Cipher can be defined to be an algorithm that performs encryption or decryption. In cryptography, a set of defined steps are followed to generate ciphers.

2. Which of the following cipher is created by shuffling the letters of a word?
a) substitution cipher
b) transposition cipher
c) mono alphabetic cipher
d) poly alphabetic cipher

Answer: b
Clarification: Types of traditional ciphers- Transposition and substitution cipher. In transposition cipher the letters of the given message are shuffled in a particular order, fixed by a given rule.

3. Which of the following is not a type of transposition cipher?
a) Rail fence cipher
b) Columnar transposition cipher
c) One time pad cipher
d) Route cipher
View Answer

Answer: c
Clarification: Out of the given options only One time pad cipher is not a type of transposition cipher. It is a type of substitution cipher.

4. Which of the following is not a type of mono alphabetic cipher?
a) additive cipher
b) multiplicative cipher
c) afffine cipher
d) hill cipher
View Answer

Answer: d
Clarification: In mono alphabetic cipher each symbol of plain text is replaced by a particular respective symbol in the cipher text. There are three types of mono alphabetic ciphers- additive, multiplicative and affine.

5. Route cipher falls under the category of?
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: c
Clarification: Route cipher is a transposition cipher. It falls under the category of transposition cipher as it encrypts the plain text by rearranging its letters.

6. Which of the following ciphered text would have used transposition cipher for encryption of the plain text “”?
a) SSCMBNUMERY
b) TBMGPVOESZ
c) UCNHQWPFTA
d) SNONRAFUDY

Answer: d
Clarification: We know that transposition cipher encrypts the plain text by shuffling the letters of the plain text. So out of the given options, only “SNONRAFUDY” has the same set of letters as “”.

7. Which of the following is a type of transposition cipher?
a) Rail Fence cipher
b) Hill cipher
c) Rotor cipher
d) One time pad

Answer: a
Clarification: In transposition cipher the letters of the given message are shuffled in a particular order, fixed by a given rule. Two types of transposition cipher are – Rail fence cipher and Columnar transposition cipher.

8. In which of the following cipher the plain text and the ciphered text have same set of letters?
a) one time pad cipher
b) columnar transposition cipher
c) playfair cipher
d) additive cipher

Answer: b
Clarification: In transposition cipher, the letters remain same in ciphered and plain text. Their position is only changed whereas in substitution cipher the letters become different in encrypted text. So columnar transposition cipher will be the correct option.

9. Combining transposition cipher with substitution cipher improves its strength?
a) true
b) false

Answer: a
Clarification: Combining transposition cipher with substitution cipher helps in overcoming its weaknesses. But it causes the cipher to become more laborious to decode and it becomes more prone to errors.

10. What will be the encrypted text corresponding to plain text “” using rail fence cipher with key value given to be 2?
a) SNONRAFUDY
b) SORAFUDYNN
c) SNAUDNORFY
d)

Answer: a
Clarification: For encrypting a plain text using rail fence cipher we use a table having a number of rows equal to key value as shown below. Then we read along the rows to get the ciphered text. So the ciphered text will be “SNONRAFUDY”.

11. What will be the encrypted text corresponding to plain text “” using columnar transposition cipher with the keyword as “GAMES”?
a) SNONRAFUDY
b) SORAFUDYNN
c) SNAUDNORFY
d) ANFRSUNDOY

Answer: d
Clarification: For encrypting using columnar cipher we have to arrange the letters of the plain text in a table which has the same number of columns as the letters of the keyword. Then the letters of the keyword are arranged in alphabetical order and we read along each column.
3 1 4 2 5
G A M E S
S A N F O
U N D R Y
So the ciphered text will be “ANFRSUNDOY”.

contest