Category: Data Structures & Algorithms Objective Questions

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

1. What is meant by integer partition?
a) representing an integer as sum of positive and negative real numbers
b) representing an integer as sum of positive and negative integers
c) representing an integer as sum of positive integers
d) representing an integer as sum of positive real numbers

Answer: c
Clarification: Integer partition is the way of representing an integer as sum of positive integers. Partitions differing only in their order are considered to be same.

2. How many partitions will be formed for the integer 3?
a) 2
b) 3
c) 4
d) 8

Answer: b
Clarification: We need to find the combinations of positive integers which give 3 as their sum. These will be {3}, {2,1}, {1,1,1}. Thus the correct answer is 3.

3. What is meant by number theory?
a) study of integers
b) study of complex numbers
c) numerology
d) theory of origination of mathematics

Answer: a
Clarification: Number theory is a branch of mathematics that deals with the study of integers. Partitioning of a number comes under the study of number theory.

4. Which of the following is true according to Ramanujan’s congruence?
a) No. of partitions are divisible by 5 for a number 3 more than a multiple of 5
b) No. of partitions are divisible by 5 for a number 4 more than a multiple of 5
c) No. of partitions are divisible by 5 for a number 2 more than a multiple of 5
d) No. of partitions are divisible by 5 for a number 1 more than a multiple of 5

Answer: b
Clarification: Ramanujan’s congruence are some relations found for the no. of partitions of an integer. According to it, the number of partitions of an integer is divisible by 5 if that integer is 4 more than a multiple of 5.

5. The no. of partitions of which of the following integer will be divisible by 5?
a) 3
b) 5
c) 9
d) 6

Answer: c
Clarification: According to Ramanujan’s congruence number of partitions of an integer is divisible by 5 if that integer is 4 more than a multiple of 5. So out of the given options 9 is the only integer which satisfies this condition.

6. What is the output of the following code?

#include 
using namespace std;  
void printArray(int p[], int n) 
{ 
	for (int i = 0; i <= n-1; i++) 
	cout << p[i] << " "; 
	cout << endl; 
} 
void func1(int n) 
{ 
	int p[n];  
	int k = 0;  
	p[k] = n; 	
	while (true) 
	{ 		
		printArray(p, k+1); 		
		int rem_val = 0; 
		while (k >= 0 && p[k] == 1) 
		{ 
			rem_val += p[k]; 
			k--; 
		} 
		if (k < 0) return; 	
		p[k]--; 
		rem_val++; 		
		while (rem_val > p[k]) 
		{ 
			p[k+1] = p[k]; 
			rem_val = rem_val - p[k]; 
			k++; 
		} 
		p[k+1] = rem_val; 
		k++; 
	} 
} 
int main() 
{ 
int n=3;
	func1(n);
	return 0; 
}

a)

  3 
  1 2
  1 1 1

b)

  1 1 1
  2 1
  3

c)

  1 1 1
  1 2
  3

d)

   3
   2 1
   1 1 1

Answer: d
Clarification: The given code prints the partition of a number in decreasing order. This code uses the approach of dynamic programming.

7. While generating partitions of integer 3 we consider 2 1 and 1 2 to be different partitions.
a) true
b) false

Answer: b
Clarification: Partitions differing in order are considered to be same. Thus 2 1 and 1 2 are considered to be same when we generate partitions of integer 3.

8. What is the approach implemented in the following code?

#include 
using namespace std;  
void printArray(int p[], int n) 
{ 
	for (int i = 0; i <= n-1; i++) 
	cout << p[i] << " "; 
	cout << endl; 
} 
void func1(int n) 
{ 
	int p[n];  
	int k = 0;  
	p[k] = n; 	
	while (true) 
	{ 		
		printArray(p, k+1); 		
		int rem_val = 0; 
		while (k >= 0 && p[k] == 1) 
		{ 
			rem_val += p[k]; 
			k--; 
		} 
		if (k < 0) return; 	
		p[k]--; 
		rem_val++; 		
		while (rem_val > p[k]) 
		{ 
			p[k+1] = p[k]; 
			rem_val = rem_val - p[k]; 
			k++; 
		} 
		p[k+1] = rem_val; 
		k++; 
	} 
} 
 
int main() 
{ 
      int n;
      cin>>n;
      func1(n);
      return 0; 
}

a) greedy approach
b) dynamic programming
c) recursion(divide and conquer)
d) backtracking
Answer: b
Clarification: The given code prints the partition of a number in decreasing order. This code uses the approach of dynamic programming. We can also use recursion for fulfilling the same purpose.

9. What will be the output of the following code?

#include
using namespace std;
int list[200];
void func(int n, int m = 0)
{
    int i;
    if(n == 0)
    {
         for(i = 0; i < m; ++i)
         printf("%d ", list[i]);
         printf("n");
         return;
    }
    for(i = n; i > 0; --i)
    {
         if(m == 0 || i <= list[m - 1])
         {
             list[m] = i;
             func(n - i, m + 1);
         }
    }
 
}
int main()
{
	int n=3;
	func(n,0);
	return 0;
}

a)

  3 
  2 1
  1 1 1

b)

  1 1 1
  2 1
  3

c)

  1 1 1
  1 2
  3

d)

   3
   1 2
   1 1 1

Answer: a
Clarification: The given code prints the partition of a number in decreasing order. This code uses the approach of recursion. The same purpose can be fulfilled by using dynamic programming.

10. Which of the following correctly represents the code to print partitions of a number?
a)

#include
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{
 
	if(n==0)
        {
		for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
	for(int i=k;i>0;i--)
        {
		if(i>n)continue; 
		print[idx]=i;					 
		partitn(n-i,i,idx+1);
	}
}
int main()
{
	int n;
	cin>>n;
	partitn(n,n,0);
	return 0;
}

b)

#include
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{	
	if(n==0)
        {
		for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
	for(int i=k;i>0;i--)
        {
		if(i>n)continue; 
		print[idx]=i;					 
		partitn(n-i,i,idx+1);
	}
}
int main()
{
	int n;
	cin>>n;
	partitn(n,0,0);
	return 0;
}

c)

#include
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{	
	if(n==0)
        {
		for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
	for(int i=k;i>0;i--)
        {
		print[idx]=i;					 
		partitn(n-i,i,idx+1);
	}
}
int main()
{
	int n;
	cin>>n;
	partitn(n,0,0);
	return 0;
}

d)

#include
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{	
	if(n==0)
        {
		for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
	for(int i=k;i>0;i--)      
        { 
		print[idx]=i;					 
		partitn(n-i,i,idx+1);
	}
}
int main()
{
	int n;
	cin>>n;
	partitn(n,n,0);
	return 0;
}

Answer: a
Clarification: In the correct code we need to pass n as second argument in the function partitn() and need to check for the condition i>n. The code prints the partitions in decreasing order.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Dijkstra’s Algorithm”.

1. Dijkstra’s Algorithm is used to solve _____________ problems.
a) All pair shortest path
b) Single source shortest path
c) Network flow
d) Sorting

Answer: b
Clarification: Dijkstra’s Algorithm is used for solving single source shortest path problems. In this algorithm, a single node is fixed as a source node and shortest paths from this node to all other nodes in graph is found.

2. Which of the following is the most commonly used data structure for implementing Dijkstra’s Algorithm?
a) Max priority queue
b) Stack
c) Circular queue
d) Min priority queue

Answer: d
Clarification: Minimum priority queue is the most commonly used data structure for implementing Dijkstra’s Algorithm because the required operations to be performed in Dijkstra’s Algorithm match with specialty of a minimum priority queue.

3. What is the time complexity of Dijikstra’s algorithm?
a) O(N)
b) O(N³)
c) O(N²)
d) O(logN)

Answer: c
Clarification: Time complexity of Dijkstra’s algorithm is O(N²) because of the use of doubly nested for loops. It depends on how the table is manipulated.

4. Dijkstra’s Algorithm cannot be applied on ______________
a) Directed and weighted graphs
b) Graphs having negative weight function
c) Unweighted graphs
d) Undirected and unweighted graphs
Answer: b
Clarification: Dijkstra’s Algorithm cannot be applied on graphs having negative weight function because calculation of cost to reach a destination node from the source node becomes complex.

5. What is the pseudo code to compute the shortest path in Dijkstra’s algorithm?
a)

if(!T[w].Known)
 	if(T[v].Dist + C(v,w) < T[w].Dist)  {
                 Decrease(T[w].Dist to T[v].Dist +C(v,w));
                T[w].path=v; }

b)

if(T[w].Known)
 	if(T[v].Dist + C(v,w) < T[w].Dist)  {
                 Increase (T[w].Dist to T[v].Dist +C(v,w));
                T[w].path=v; }

c)

if(!T[w].Known)
 	if(T[v].Dist + C(v,w) > T[w].Dist)  {
                 Decrease(T[w].Dist to T[v].Dist +C(v,w);
                  T[w].path=v; }

d)

if(T[w].Known)
 	if(T[v].Dist + C(v,w) < T[w].Dist)  {
                 Increase(T[w].Dist to T[v].Dist);
                T[w].path=v; }

Answer: a
Clarification: If the known value of the adjacent vertex(w) is not set then check whether the sum of distance from source vertex(v) and cost to travel from source to adjacent vertex is less than the existing distance of the adjacent node. If so, perform decrease key operation.

6. How many priority queue operations are involved in Dijkstra’s Algorithm?
a) 1
b) 3
c) 2
d) 4
Answer: b
Clarification: The number of priority queue operations involved is 3. They are insert, extract-min and decrease key.

7. How many times the insert and extract min operations are invoked per vertex?
a) 1
b) 2
c) 3
d) 0

Answer: a
Clarification: Insert and extract min operations are invoked only once per vertex because each vertex is added only once to the set and each edge in the adjacency list is examined only once during the course of algorithm.

8. The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to ___________
a) Total number of vertices
b) Total number of edges
c) Number of vertices – 1
d) Number of edges – 1

Answer: b
Clarification: If the total number of edges in all adjacency list is E, then there will be a total of E number of iterations, hence there will be a total of at most E decrease key operations.

9. What is running time of Dijkstra’s algorithm using Binary min- heap method?
a) O(V)
b) O(VlogV)
c) O(E)
d) O(ElogV)

Answer: d
Clarification: Time required to build a binary min heap is O(V). Each decrease key operation takes O(logV) and there are still at most E such operations. Hence total running time is O(ElogV).

10. The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.
a) True
b) False

Answer: b
Clarification: The number of iterations involved in Bellmann Ford Algorithm is more than that of Dijkstra’s Algorithm.

11. Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V.
a) True
b) False

Answer: a
Clarification: The equality d[u]=delta(s,u) holds good when vertex u is added to set S and this equality is maintained thereafter by the upper bound property.

12. Given pseudo code of Dijkstra’s Algorithm.

//Initialise single source(G,s)
S=0
Q=V[G]
While Q != 0
    Do u=extract-min(Q)
        S=S union {u}
	    For each vertex v in adj[u]
	        Do relax(u,v,w)

What happens when “While Q != 0” is changed to “while Q>1”?
a) While loop gets executed for v times
b) While loop gets executed for v-1 times
c) While loop gets executed only once
d) While loop does not get executed

Answer: b
Clarification: In the normal execution of Dijkstra’s Algorithm, the while loop gets executed V times. The change in the while loop statement causes it to execute only V – 1 times.

13. Consider the following graph.

If b is the source vertex, what is the minimum cost to reach f vertex?
a) 8
b) 9
c) 4
d) 6

Answer: d
Clarification: The minimum cost to reach f vertex from b vertex is 6 by having vertices g and e as intermediates.
b to g, cost is 1
g to e, cost is 4
e to f, cost is 1
hence total cost 1+4+1=6.

14. In the given graph, identify the shortest path having minimum cost to reach vertex E if A is the source vertex.

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

Answer: b
Clarification: The minimum cost required to travel from vertex A to E is via vertex C
A to C, cost= 3
C to E, cost= 2
Hence the total cost is 5.

15. Dijkstra’s Algorithm is the prime example for ___________
a) Greedy algorithm
b) Branch and bound
c) Back tracking
d) Dynamic programming

Answer: a
Clarification: Dijkstra’s Algorithm is the prime example for greedy algorithms because greedy algorithms generally solve a problem in stages by doing what appears to be the best thing at each stage.

and Answers.

contest

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