Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Branch and Bound”.

1. Branch and bound is a __________
a) problem solving technique
b) data structure
c) sorting algorithm
d) type of tree

Answer: a
Clarification: Branch and bound is a problem solving technique generally used for solving combinatorial optimization problems. Branch and bound helps in solving them faster.

2. Which of the following is not a branch and bound strategy to generate branches?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
Answer: d
Clarification: LIFO, FIFO and Lowest cost branch and bound are different strategies to generate branches. Lowest cost branch and bound helps us find the lowest cost path.

3. Which data structure is used for implementing a LIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list
Answer: a
Clarification: Stack is the data structure is used for implementing LIFO branch and bound strategy. This leads to depth first search as every branch is explored until a leaf node is discovered.

4. Which data structure is used for implementing a FIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list

Answer: b
Clarification: Queue is the data structure is used for implementing FIFO branch and bound strategy. This leads to breadth first search as every branch at depth is explored first before moving to the nodes at greater depth.

5. Which data structure is most suitable for implementing best first branch and bound strategy?
a) stack
b) queue
c) priority queue
d) linked list

Answer: c
Clarification: Priority Queue is the data structure is used for implementing best first branch and bound strategy. Dijkstra’s algorithm is an example of best first search algorithm.

6. Which of the following branch and bound strategy leads to breadth first search?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
Answer: b
Clarification: LIFO, FIFO and Lowest cost branch and bound are different strategies to generate branches. FIFO branch and bound leads to breadth first search.

7. Which of the following branch and bound strategy leads to depth first search?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound

Answer: a
Clarification: LIFO, FIFO and Lowest cost branch and bound are different strategies to generate branches. LIFO branch and bound leads to depth first search.

8. Both FIFO branch and bound strategy and backtracking leads to depth first search.
a) true
b) false
Answer: b
Clarification: FIFO branch and bound leads to breadth first search. Whereas backtracking leads to depth first search.

9. Both LIFO branch and bound strategy and backtracking leads to depth first search.
a) true
b) false

Answer: a
Clarification: Both backtrackings as well as branch and bound are problem solving algorithms. Both LIFO branch and bound strategy and backtracking leads to depth first search.

10. Choose the correct statement from the following.
a) branch and bound is more efficient than backtracking
b) branch and bound is not suitable where a greedy algorithm is not applicable
c) branch and bound divides a problem into at least 2 new restricted sub problems
d) backtracking divides a problem into at least 2 new restricted sub problems

Answer: c
Clarification: Both backtracking as well as branch and bound are problem solving algorithms. Branch and bound is less efficient than backtracking. Branch and bound divides a problem into at least 2 new restricted sub problems.

11. Which of the following can traverse the state space tree only in DFS manner?
a) branch and bound
b) dynamic programming
c) greedy algorithm
d) backtracking

Answer: d
Clarification: Both backtracking as well as branch and bound are problem solving algorithms. Branch and bound can traverse in DFS as well as BFS manner whereas backtracking only traverses in DFS manner.

& Algorithms.

here is

Data Structures & Algorithms Multiple Choice Questions on “Complete Bipartite Graph”.

1. Which type of graph has all the vertex of the first set connected to all the vertex of the second set?
a) Bipartite
b) Complete Bipartite
c) Cartesian
d) Pie
Answer: b
Clarification: The graph is known as Bipartite if the graph does not contain any odd length cycle in it. The complete bipartite graph has all the vertex of first set connected to all the vertex of second set.

2. Which graph is also known as biclique?
a) Histogram
b) Complete Bipartite
c) Cartesian
d) Tree

Answer: b
Clarification: A graph is known as complete bipartite graph if and only if it has all the vertex of first set connected to all the vertex of second set. Complete Bipartite graph is also known as Biclique.

3. Which term defines all the complete bipartite graph that are trees?
a) Symmetric
b) Anti – Symmetric
c) Circular
d) Stars

Answer: d
Clarification: Star is a complete bipartite graph with one internal node and k leaves. Therefore, all complete bipartite graph which is trees are known as stars in graph theory.

4. How many edges does a n vertex triangle free graph contains?
a) n²
b) n² + 2
c) n² / 4
d) n³

Answer: c
Clarification: A n vertex triangle free graph contains a total of n² / 4 number of edges. This is stated by Mantel’s Theorem which is a special case in Turan’s theorem for r=2.

5. Which graph is used to define the claw free graph?
a) Bipartite Graph
b) Claw Graph
c) Star Graph
d) Cartesian Graph

Answer: b
Clarification: Star is a complete bipartite graph with one internal node and k leaves. Star with three edges is called a claw. Hence this graph is used to define claw free graph.

6. What is testing of a complete bipartite subgraph in a bipartite graph problem called?
a) P Problem
b) P-Complete Problem
c) NP Problem
d) NP-Complete Problem

Answer: d
Clarification: NP stands for nondeterministic polynomial time. In a bipartite graph, the testing of a complete bipartite subgraph in a bipartite graph is an NP-Complete Problem.

7. Which graph cannot contain K3, 3 as a minor of graph?
a) Planar Graph
b) Outer Planar Graph
c) Non Planar Graph
d) Inner Planar Graph
Answer: a
Clarification: Minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. Hence Planar graph cannot contain K3, 3 as a minor graph.

8. Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph?
a) (nm)^1/2
b) (-nm)^1/2
c) 0
d) nm

Answer: d
Clarification: The adjacency matrix is a square matrix that is used to represent a finite graph. Therefore, the Eigen values for the complete bipartite graph is found to be (nm)^1/2, (-nm)^1/2, 0.

9. Which complete graph is not present in minor of Outer Planar Graph?
a) K3, 3
b) K3, 1
c) K3, 2
d) K1, 1

Answer: c
Clarification: Minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. Hence Outer Planar graph cannot contain K3, 2 as a minor graph.

10. Is every complete bipartite graph a Moore Graph.
a) True
b) False

Answer: a
Clarification: In graph theory, Moore graph is defined as a regular graph that has a degree d and diameter k. therefore, every complete bipartite graph is a Moore Graph.

11. What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value?
a) 1
b) n + m – 2
c) 0
d) 2

Answer: b
Clarification: The adjacency matrix is a square matrix that is used to represent a finite graph. The multiplicity of the adjacency matrix off complete bipartite graph with Eigen Value 0 is n + m – 2.

12. Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph?
a) n + m
b) n
c) 0
d) n*m

Answer: d
Clarification: The laplacian matrix is used to represent a finite graph in the mathematical field of Graph Theory. Therefore, the Eigen values for the complete bipartite graph is found to be n + m, n, m, 0.

13. What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value?
a) 1
b) m-1
c) n-1
d) 0

Answer: b
Clarification: The laplacian matrix is used to represent a finite graph in the mathematical field of Graph Theory. The multiplicity of the laplacian matrix of complete bipartite graph with Eigen Value n is m-1.

14. Is it true that every complete bipartite graph is a modular graph.
a) True
b) False

Answer: a
Clarification: Yes, the modular graph in graph theory is defined as an undirected graph in which all three vertices have at least one median vertex. So all complete bipartite graph is called modular graph.

15. How many spanning trees does a complete bipartite graph contain?
a) n^m
b) m^n-1 * n^n-1
c) 1
d) 0
Answer: b
Clarification: Spanning tree of a given graph is defined as the subgraph or the tree with all the given vertices but having minimum number of edges. So, there are a total of m^n-1 * n^n-1 spanning trees for a complete bipartite graph.

Data Structure online quiz on “Largest and Smallest Number in a Linked List using Recursion”.

1. Which of the following methods can be used to find the largest and smallest number in a linked list?
a) Recursion
b) Iteration
c) Both Recursion and iteration
d) Impossible to find the largest and smallest numbers
View Answer

Answer: c
Clarification: Both recursion and iteration can be used to find the largest and smallest number in a linked list.

2. Consider the following code snippet to find the largest element in a linked list:

struct Node{
   int val;
   struct Node *next;
}*head;
int get_max()
{
      struct Node* temp = head->next;
	  int max_num = temp->val;
	  while(______)
	  {
	        if(temp->val > max_num)
		    max_num = temp->val;
		temp = temp->next;
	  }
	  return max_num;
}

Which of the following lines should be inserted to complete the above code?
a) temp->next != 0
b) temp != 0
c) head->next != 0
d) head != 0

Answer: b
Clarification: The line “temp != 0” should be inserted to complete the above code.

3. Consider the following code snippet to find the smallest element in a linked list:

struct Node
{
     int val;
     struct Node* next;
}*head;
int get_min()
{
      struct Node* temp = head->next;
	  int min_num = temp->val;
	  while(temp != 0)
	  {
	       if(_________)
		    min_num = temp->val;
		temp = temp->next;
	  }
	  return min_num;
}

Which of the following lines should be inserted to complete the above code?
a) temp > min_num
b) val > min_min
c) temp->val < min_num
d) temp->val > min_num

Answer: c
Clarification: The line “temp->val = min_num” should be inserted to complete the above code.

4. What is the output of the following code:

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int get_max()
{
      struct Node* temp = head->next;
	  int max_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val > max_num)
		    max_num = temp->val;
		temp = head->next;
	  }
	  return max_num;
}
int main()
{
      int n = 9, arr[9] ={5,1,3,4,5,2,3,3,1},i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head -> next =0;
      temp = head;
      for(i=0;i<n;i++)
      {
          newNode =(struct Node*)malloc(sizeof(struct Node));
          newNode->next = 0;
          newNode->val = arr[i];
          temp->next =newNode;
          temp = temp->next;
      }
      int max_num = get_max();
      printf("%d %d",max_num);
      return 0;
}

a) 5
b) 1
c) runtime error
d) garbage value

Answer: c
Clarification: The variable temp will always point to the first element in the linked list due to the line “temp = head->next” in the while loop. So, it will be an infinite while loop and the program will produce a runtime error.

5. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int get_max()
{
      struct Node* temp = head->next;
	  int max_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val > max_num)
		    max_num = temp->val;
		temp = temp->next;
	  }
	  return max_num;
}
int get_min()
{
      struct Node* temp = head->next;
	  int min_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val < min_num)
		    min_num = temp->val;
		temp = temp->next;
	  }
	  return min_num;
}
int main()
{
      int i, n = 9, arr[9] ={8,3,3,4,5,2,5,6,7};
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head -> next =0;
      temp = head;
      for(i=0;i<n;i++)
      {
          newNode =(struct Node*)malloc(sizeof(struct Node));
          newNode->next = 0;
          newNode->val = arr[i];
          temp->next =newNode;
          temp = temp->next;
      }
      int max_num = get_max();
      int min_num = get_min();
      printf("%d %d",max_num,min_num);
      return 0;
}

a) 2 2
b) 8 8
c) 2 8
d) 8 2
View Answer

Answer: d
Clarification: The program prints the largest and smallest elements in the linked list, which are 8 and 2 respectively.

6. What is the time complexity of the following iterative code used to find the smallest and largest element in a linked list?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int get_max()
{
      struct Node* temp = head->next;
	  int max_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val > max_num)
		    max_num = temp->val;
		temp = temp->next;
	  }
	  return max_num;
}
int get_min()
{
      struct Node* temp = head->next;
	  int min_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val < min_num)
		    min_num = temp->val;
		temp = temp->next;
	  }
	  return min_num;
}
int main()
{
      int i, n = 9, arr[9] ={8,3,3,4,5,2,5,6,7};
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head -> next =0;
      temp = head;
      for(i=0;i<n;i++)
      {
          newNode =(struct Node*)malloc(sizeof(struct Node));
          newNode->next = 0;
          newNode->val = arr[i];
          temp->next =newNode;
          temp = temp->next;
      }
      int max_num = get_max();
      int min_num = get_min();
      printf("%d %d",max_num,min_num);
      return 0;
}

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

Answer: b
Clarification: The time complexity of the above iterative code used to find the largest and smallest element in a linked list is O(n).

7. Consider the following recursive implementation to find the largest element in a linked list:

struct Node
{
     int val;
     struct Node* next;
}*head;
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int recursive_get_max(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return max_of_two(______, _______);
}

Which of the following arguments should be passed to the function max_of two() to complete the above code?
a) temp->val,recursive_get_max(temp->next)
b) temp, temp->next
c) temp->val, temp->next->val
d) temp->next->val, temp

Answer: a
Clarification: The arguments {temp->val,recursive_get_max(temp->next)} should be passed to the function max_of_two() to complete the above code.

8. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int recursive_get_max(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return max_of_two(temp->val,recursive_get_max(temp->next));
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_get_min(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return min_of_two(temp->val,recursive_get_min(temp->next));
}
int main()
{
     int n = 9, arr[9] ={1,3,2,4,5,0,5,6,7},i;
     struct Node *temp, *newNode;
     head = (struct Node*)malloc(sizeof(struct Node));
     head -> next =0;
     temp = head;
     for(i=0;i<n;i++)
     {
           newNode =(struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next =newNode;
           temp = temp->next;
     }
     int max_num = recursive_get_max(head->next);
     int min_num = recursive_get_min(head->next);
     printf("%d %d",max_num,min_num);
     return 0;
}

a) 7 1
b) 0 7
c) 7 0
d) 1 1

Answer: c
Clarification: The program prints the largest and the smallest elements in the linked list, which are 7 and 0 respectively.

9. What is the time complexity of the recursive implementation used to find the largest and smallest element in a linked list?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int recursive_get_max(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return max_of_two(temp->val,recursive_get_max(temp->next));
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_get_min(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return min_of_two(temp->val,recursive_get_min(temp->next));
}
int main()
{
     int n = 9, arr[9] ={1,3,2,4,5,0,5,6,7},i;
     struct Node *temp, *newNode;
     head = (struct Node*)malloc(sizeof(struct Node));
     head -> next =0;
     temp = head;
     for(i=0;i<n;i++)
     {
           newNode =(struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next =newNode;
           temp = temp->next;
     }
     int max_num = recursive_get_max(head->next);
     int min_num = recursive_get_min(head->next);
     printf("%d %d",max_num,min_num);
     return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
Answer: b
Clarification: The time complexity of the above recursive implementation used to find the largest and smallest element in linked list is O(n).

10. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_get_min(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return min_of_two(temp->val,recursive_get_min(temp->next));
}
int main()
{
     int n = 5, arr[5] ={1,1,1,1,1},i;
     struct Node *temp, *newNode;
     head = (struct Node*)malloc(sizeof(struct Node));
     head -> next =0;
     temp = head;
     for(i=0;i<n;i++)
     {
           newNode =(struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next =newNode;
           temp = temp->next;
     }
     int min_num = recursive_get_min(head->next);
     printf("%d",min_num);
     return 0;
}

a) 1
b) 0
c) compile time error
d) runtime error

Answer: a
Clarification: The program prints the smallest element in the linked list, which is 1.

11. How many times will the function recursive_get_min() be called when the following code is executed?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_get_min(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return min_of_two(temp->val,recursive_get_min(temp->next));
}
int main()
{
     int n = 5, arr[5] ={1,1,1,1,1},i;
     struct Node *temp, *newNode;
     head = (struct Node*)malloc(sizeof(struct Node));
     head -> next =0;
     temp = head;
     for(i=0;i<n;i++)
     {
           newNode =(struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next =newNode;
           temp = temp->next;
     }
     int min_num = recursive_get_min(head->next);
     printf("%d",min_num);
     return 0;
}

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

Answer: b
Clarification: The function recursive_get_min() will be called 5 times when the above code is executed.

Data Structure Multiple Choice Questions on “Maximum Sum of Continuous Subarray – 1”.

1. Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?
a) Dynamic programming
b) Two for loops (naive method)
c) Divide and conquer
d) Dynamic programming, naïve method and Divide and conquer methods

Answer: d
Clarification: Dynamic programming, naïve method and Divide and conquer methods can be used to solve the maximum sub array sum problem.

2. Find the maximum sub-array sum for the given elements.
{2, -1, 3, -4, 1, -2, -1, 5, -4}
a) 3
b) 5
c) 8
d) 6
View Answer

Answer: b
Clarification: The maximum sub-array sum is 5.

3. Find the maximum sub-array sum for the given elements.
{-2, -1, -3, -4, -1, -2, -1, -5, -4}
a) -3
b) 5
c) 3
d) -1

Answer: d
Clarification: All the elements are negative. So, the maximum sub-array sum will be equal to the largest element. The largest element is -1 and therefore, the maximum sub-array sum is -1.

4. Consider the following naive method to find the maximum sub-array sum:

#include
int main()
{
     int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	  tmp_max=0;
	  for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	  {
	       tmp_max +=arr[sub_arr_idx];
	       if(tmp_max > cur_max)
		 _____________;
	  }
     }
     printf("%d",cur_max);
     return 0;
}

Which line should be inserted to complete the above code?
a) tmp_max = cur_max
b) break
c) continue
d) cur_max = tmp_max

Answer: d
Clarification: If the tmp_max element is greater than the cur_max element, we make cur_max equal to tmp_max, i.e. cur_max = tmp_max.

5. What is the time complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

#include
int main()
{
     int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	  tmp_max=0;
	  for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	  {
	       tmp_max +=arr[sub_arr_idx];
	       if(tmp_max > cur_max)
		 _____________;
	  }
     }
     printf("%d",cur_max);
     return 0;
}

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

Answer: a
Clarification: The naive method uses two for loops. The outer loop runs from 0 to n,
i.e. i = 0 : n.
The inner loop runs from i to n, i.e. j = i : n.
Therefore, the inner loop runs:
n times when the outer loop runs the first time.
(n-1) times when the outer loop runs the second time.
:
:
:
2 times when the outer loop runs (n-1)th time.
1 time when the outer loop runs nth time.
Therefore, time complexity = n + (n-1) + (n-2) + …… + 2 + 1 = n * (n + 1) /2 = O(n²).

6. What is the space complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

#include
int main()
{
     int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	  tmp_max=0;
	  for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	  {
	       tmp_max +=arr[sub_arr_idx];
	       if(tmp_max > cur_max)
		 _____________;
	  }
     }
     printf("%d",cur_max);
     return 0;
}

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

Answer: b
Clarification: The naive method uses only a constant space. So, the space complexity is O(1).

7. What is the output of the following naive method used to find the maximum sub-array sum?

#include
int main()
{
     int arr[1000] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	   tmp_max = 0;
	   for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	   {
	        tmp_max += arr[sub_arr_idx];
	        if(tmp_max > cur_max)
	        cur_max = tmp_max;
	   }
     }
     printf("%d",cur_max);
     return 0;
}

a) 6
b) 9
c) 7
d) 4
Answer: c
Clarification: The naive method prints the maximum sub-array sum, which is 7.

8. What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n²)
Answer: c
Clarification: The time complexity of the divide and conquer algorithm used to find the maximum sub-array sum is O(nlogn).

9. What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(1)
c) O(n!)
d) O(n²)
Answer: b
Clarification: The divide and conquer algorithm uses a constant space. So, the space complexity is O(1).

and Answers.

contest

Data Structure Multiple Choice Questions on “Balanced Partition”.

1. Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem?
a) Dynamic programming
b) Recursion
c) Brute force
d) Dynamic programming, Recursion, Brute force

Answer: d
Clarification: All of the mentioned methods can be used to solve the balanced partition problem.

2. In which of the following cases, it is not possible to have two subsets with equal sum?
a) When the number of elements is odd
b) When the number of elements is even
c) When the sum of elements is odd
d) When the sum of elements is even
Answer: c
Clarification: When the sum of all the elements is odd, it is not possible to have two subsets with equal sum.

3. What is the time complexity of the brute force algorithm used to solve the balanced partition problem?
a) O(1)
b) O(n)
c) O(n²)
d) O(2ⁿ)
Answer: d
Clarification: In the brute force implementation, all the possible subsets will be formed. This takes exponential time.

4. Consider a variation of the balanced partition problem in which we find two subsets such that |S1 – S2| is minimum. Consider the array {1, 2, 3, 4, 5}. Which of the following pairs of subsets is an optimal solution for the above problem?
a) {5, 4} & {3, 2, 1}
b) {5} & {4, 3, 2, 1}
c) {4, 2} & {5, 3, 1}
d) {5, 3} & {4, 2, 1}

Answer: d
Clarification: For S1 = {5, 3} and S2 = {4, 2, 1}, sum(S1) – sum(S2) = 1, which is the optimal solution.

5. Consider the following code:

#include
int balanced_partition(int *arr, int len)
{
     int sm = 0, i, j;
     for(i = 0;i < len; i++)
      sm += arr[i];
     if(sm % 2 != 0)
        return 0;
     int ans[sm/2 + 1][len + 1];
     for(i = 0; i <= len; i++)
      ans[0][i] = 1;
     for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
     for(i = 1; i <= sm/2; i++)
     {
         for(j = 1;j <= len; j++)
         {
             ans[i][j] = ans[i][j-1];
             if(i >= arr[j - 1])
                ans[i][j] = _______________;
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
       printf("false");
     else
       printf("true");
     return 0;
}

Which of the following lines should be inserted to complete the above code?
a) ans[i – arr[j – 1]][j – 1]
b) ans[i][j]
c) ans[i][j] || ans[i – arr[j – 1]][j – 1]
d) ans[i][j] && ans[i – arr[j – 1]][j – 1]

Answer: c
Clarification: The line “ans[i][j] || ans[i – arr[j – 1]][j – 1]” completes the above code.

6. What is the time complexity of the following dynamic programming implementation of the balanced partition problem where “n” is the number of elements and “sum” is their sum?

#include
int balanced_partition(int *arr, int len)
{
     int sm = 0, i, j;
     for(i = 0;i < len; i++)
      sm += arr[i];
     if(sm % 2 != 0)
        return 0;
     int ans[sm/2 + 1][len + 1];
     for(i = 0; i <= len; i++)
      ans[0][i] = 1;
     for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
     for(i = 1; i <= sm/2; i++)
     {
         for(j = 1;j <= len; j++)
         {
             ans[i][j] = ans[i][j-1];
             if(i >= arr[j - 1])
                ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
       printf("false");
     else
       printf("true");
     return 0;
}

a) O(sum)
b) O(n)
c) O(sum * n)
d) O(sum + n)
View Answer

Answer: c
Clarification: The time complexity of the above dynamic programming implementation of the balanced partition problem is O(sum * n).

7. What is the space complexity of the following dynamic programming implementation of the balanced partition problem?

#include
int balanced_partition(int *arr, int len)
{
     int sm = 0, i, j;
     for(i = 0;i < len; i++)
      sm += arr[i];
     if(sm % 2 != 0)
        return 0;
     int ans[sm/2 + 1][len + 1];
     for(i = 0; i <= len; i++)
      ans[0][i] = 1;
     for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
     for(i = 1; i <= sm/2; i++)
     {
         for(j = 1;j <= len; j++)
         {
             ans[i][j] = ans[i][j-1];
             if(i >= arr[j - 1])
                ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
       printf("false");
     else
       printf("true");
     return 0;
}

a) O(sum)
b) O(n)
c) O(sum * n)
d) O(sum + n)

Answer: c
Clarification: The space complexity of the above dynamic programming implementation of the balanced partition problem is O(sum * n).

8. What is the output of the following code?

#include
int balanced_partition(int *arr, int len)
{
      int sm = 0, i, j;
      for(i = 0;i < len; i++)
      sm += arr[i];
      if(sm % 2 != 0)
        return 0;
      int ans[sm/2 + 1][len + 1];
      for(i = 0; i <= len; i++)
      ans[0][i] = 1;
      for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
      for(i = 1; i <= sm/2; i++)
      {
          for(j = 1;j <= len; j++)
          {
              ans[i][j] = ans[i][j-1];
              if(i >= arr[j - 1])
                ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
          }
      }
      return ans[sm/2][len];
}
int main()
{
      int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
      int ans = balanced_partition(arr,len);
      if(ans == 0)
         printf("false");
      else
         printf("true");
      return 0;
}

a) True
b) False
Answer: a
Clarification: The partitions are S1 = {6, 7} and S2 = {1, 3, 4, 5} and the sum of each partition is 13. So, the array can be divided into balanced partitions.

9. What is the value stored in ans[3][3] when the following code is executed?

#include
int balanced_partition(int *arr, int len)
{
     int sm = 0, i, j;
     for(i = 0;i < len; i++)
      sm += arr[i];
     if(sm % 2 != 0)
        return 0;
     int ans[sm/2 + 1][len + 1];
     for(i = 0; i <= len; i++)
      ans[0][i] = 1;
     for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
     for(i = 1; i <= sm/2; i++)
     {
         for(j = 1;j <= len; j++)
         {
             ans[i][j] = ans[i][j-1];
             if(i >= arr[j - 1])
                ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
        printf("false");
     else
        printf("true");
     return 0;
}

a) 0
b) 1
c) -1
d) -2

Answer: b
Clarification: The value stored in ans[3][3] indicates if a sum of 3 can be obtained using a subset of the first 3 elements. Since the sum can be obtained the value stored is 1.

10. What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?
a) 16
b) 32
c) 0
d) 64

Answer: a
Clarification: The sum of all the elements of the array is 32. So, the sum of all the elements of each partition should be 16.

11. What is the output of the following code?

#include
int balanced_partition(int *arr, int len)
{
     int sm = 0, i, j;
     for(i = 0;i < len; i++)
      sm += arr[i];
     if(sm % 2 != 0)
        return 0;
     int ans[sm/2 + 1][len + 1];
     for(i = 0; i <= len; i++)
      ans[0][i] = 1;
     for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
     for(i = 1; i <= sm/2; i++)
     {
         for(j = 1;j <= len; j++)
         {
             ans[i][j] = ans[i][j-1];
             if(i >= arr[j - 1])
                 ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {5, 6, 7, 10, 3, 1}, len = 6;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
       printf("false");
     else
       printf("true");
     return 0;
}

a) True
b) False
View Answer

Answer: a
Clarification: The array can be divided into two partitions S1 = {10, 6} and S2 = {5, 7, 3, 1} and the sum of all the elements of each partition is 16. So, the answer is true.

12. What is the output of the following code?

#include
int balanced_partition(int *arr, int len)
{
     int sm = 0, i, j;
     for(i = 0;i < len; i++)
      sm += arr[i];
     if(sm % 2 != 0)
        return 0;
     int ans[sm/2 + 1][len + 1];
     for(i = 0; i <= len; i++)
      ans[0][i] = 1;
     for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
     for(i = 1; i <= sm/2; i++)
     {
         for(j = 1;j <= len; j++)
         {
             ans[i][j] = ans[i][j-1];
             if(i >= arr[j - 1])
                 ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, len = 9;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
       printf("false");
     else
       printf("true");
     return 0;
}

a) True
b) False
View Answer

Answer: b
Clarification: Since the sum of all the elements of the array is 45, the array cannot be divided into two partitions of equal sum and the answer is false.

& Algorithms.

and Answers.

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

1. Trithemius cipher is an example of ________________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

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

2. Encryption in trithemius cipher is done using _______________
a) trithemius table
b) vigenere cycle
c) tabula recta
d) any table provided by the person performing the encryption

Answer: c
Clarification: Encryption of plain text in trithemius cipher is done by making use of tabula recta. The same table is also used for encryption in vigenere cipher and running key cipher.

3. Which of the following is a modified version of Caesar cipher?
a) vigenere cipher
b) autokey cipher
c) running key cipher
d) trithemius cipher
View Answer

Answer: d
Clarification: If in caesar cipher we consider a shift that increases by 1 by each letter starting at 0 then it is equivalent to trithemius cipher. So trithemius cipher is a special case of caesar cipher.

4. Which of the following is a difference between trithemius cipher and vigenere cipher?
a) they use different tables for encryption
b) vigenere cipher is poly alphabetic whereas running key cipher is mono alphabetic
c) vigenere cipher uses a key whereas no key is required for using trithemius cipher
d) vigenere cipher is substitution cipher whereas trithemius cipher is transposition cipher

Answer: c
Clarification: Trithemius cipher is a special case of vigenere cipher. The difference is that vigenere cipher uses a different key every time but a fixed key is used by trithemius cipher.

5. Which of the following cipher require the use of tabula recta?
a) hill cipher
b) route cipher
c) rail fence cipher
d) trithemius cipher

Answer: d
Clarification: Ciphers like running key cipher, vigenere cipher, trithemius cipher, etc. makes use of tabula recta. Whereas hill cipher, rail fence cipher and route cipher does not require tabula recta for encryption of plain text.

6. Trithemius cipher is a special case of _______________
a) autokey cipher
b) vigenere cipher
c) hill cipher
d) route cipher

Answer: b
Clarification: Trithemius cipher is a special case of vigenere cipher. The difference is that vigenere cipher uses a different key every time but a fixed key is used by trithemius cipher.

7. Trithemius cipher is harder to crack than vigenere cipher.
a) true
b) false

Answer: b
Clarification: Trithemius cipher is a special case of vigenere cipher with ABCDEFGHIJKLMNOPQRSTUVWXYZ as key. So trithemius cipher is easier to crack as the key being used remains same every time.

8. What will be the plain text corresponding to cipher text “ACCFYX” if trithemius cipher is used?
a) ABACUS
b) ABROAD
c) ABRUPT
d) ABUSED
View Answer

Answer: a
Clarification: Running key cipher is a type of poly alphabetic substitution which uses tabula recta for making substitutions in the plain text. Using the table and key as ABCDEFGHIJKLMNOPQRSTUVWXYZ we find the plain text to be “ABACUS”.

9. Trithemius cipher is harder to crack than caesar cipher.
a) True
b) False
View Answer

Answer: a
Clarification: Trithemius cipher uses a more complex version of caesar cipher. So trithemius cipher is harder to crack as compared to caesar cipher.

10. Which of the following cipher is easiest to crack?
a) vigenere cipher
b) running key cipher
c) trithemius cipher
d) all are equally secure
View Answer

Answer: c
Clarification: Trithemius cipher is a special case of vigenere cipher and running key cipher is a variation of vigenere cipher. If one figures out that the cipher being used is trithemius then it is very easy to crack, unlike running key and vigenere ciphers as these use a secret key for encryption.

11. What will be the ciphered text corresponding to “” if trithemius cipher is used for encryption?
a) SBPISZTKZH
b) TCQJTAULAI
c) TBOGPVOESZ
d) SPBISZKTZH

Answer: a
Clarification: Encryption in trithemius cipher takes place exactly as in vigenere cipher if we consider the key to be ABCDEFGHIJKLMNOPQRSTUVWXYZ. So by using the tabula recta we can find the encrypted text which is “SBPISZTKZH”.

12. What will be the ciphered text corresponding to “ALGORITHM” if trithemius cipher is used for encryption?
a) BNJSWOAPV
b) BMHPSJUIN
c) AMIRVNZOU
d) MBPHJSNIU

Answer: c
Clarification: Encryption in trithemius cipher takes place exactly as in vigenere cipher if we consider the key to be ABCDEFGHIJKLMNOPQRSTUVWXYZ. So by using the tabula recta we can find the encrypted text which is “AMIRVNZOU”.

13. What will be the plain text corresponding to cipher text “RVUVMF” if trithemius cipher is used?
a) RABBIT
b) RUSSIA
c) RANGER
d) FRIEND

Answer: b
Clarification: Trithemius cipher is a type of poly alphabetic substitution which uses tabula recta for making substitutions in the plain text. Using the table and using the key as ABCDEFGHIJKLMNOPQRSTUVWXYZ we find the plain text to be “RUSSIA”.

contest