Category: Data Structures & Algorithms Objective Questions

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

1. Strassen’s algorithm is a/an_____________ algorithm.
a) Non- recursive
b) Recursive
c) Approximation
d) Accurate

Answer: b
Clarification: Strassen’s Algorithm for matrix multiplication is a recursive algorithm since the present output depends on previous outputs and inputs.

2. What is the running time of Strassen’s algorithm for matrix multiplication?
a) O(n^2.81)
b) O(n³)
c) O(n^1.8)
d) O(n²)

Answer: a
Clarification: Strassen’s matrix algorithm requires only 7 recursive multiplications of n/2 x n/2 matrix and Theta(n²) scalar additions and subtractions yielding the running time as O(n^2.81).

3. What is the running time of naïve matrix multiplication algorithm?
a) O(n^2.81)
b) O(n⁴)
c) O(n)
d) O(n³)
View Answer

Answer: d
Clarification: The traditional matrix multiplication algorithm takes O(n³) time. The number of recursive multiplications involved in this algorithm is 8.

4. Strassen’s matrix multiplication algorithm follows ___________ technique.
a) Greedy technique
b) Dynamic Programming
c) Divide and Conquer
d) Backtracking

Answer: c
Clarification: Strassen’s matrix multiplication algorithm follows divide and conquer technique. In this algorithm the input matrices are divided into n/2 x n/2 sub matrices and then the recurrence relation is applied.

5. The number of scalar additions and subtractions used in Strassen’s matrix multiplication algorithm is ________
a) O(n^2.81)
b) Theta(n²)
c) Theta(n)
d) O(n³)

Answer: b
Clarification: Using Theta(n²) scalar additions and subtractions, 14 matrices are computed each of which is n/2 x n/2. Then seven matrix products are computed recursively.

6. Running time of Strassen’s algorithm is better than the naïve Theta(n³) method.
a) True
b) False

Answer: a
Clarification: Strassen’s Algorithm requires only 7 recursive multiplications when compared with the naïve Theta(n³) method which reuires 9 recursive multiplications to compute the product.

7. Given the program of naïve method.

for i=1 to n do
   for j=1 to n do
       Z[i][j]=0;
       for k=1 to n do 
            ___________________________

Fill in the blanks with appropriate formula
a) Z[i][j] = Z[i][j] + X[i][k]*Y[k][j]
b) Z[i][j] = Z[i][j] + X[i][k] + Y[k][j]
c) Z[i][j] = Z[i][j] * X[i][k]*Y[k][j]
d) Z[i][j] = Z[i][j] * X[i][k] + Y[k][j]

Answer: a
Clarification: In the naïve method of matrix multiplication the number of iterating statements involved are 3, because of the presence of rows and columns. The element in each row of one matrix is multiplied with each element in the column of the second matrix. The computed value is placed in the new matrix Z[i][j].

8. Who demonstrated the difference in numerical stability?
a) Strassen
b) Bailey
c) Lederman
d) Higham

Answer: d
Clarification: The difference in the numerical stability was demonstrated by Higham. He overemphasized that Strassen’s algorithm is numericaly unstable for some applications.

9. What is the recurrence relation used in Strassen’s algorithm?
a) 7T(n/2) + Theta(n²)
b) 8T(n/2) + Theta(n²)
c) 7T(n/2) + O(n²)
d) 8T(n/2) + O(n²)

Answer: a
Clarification: The recurrence relation used in Strassen’s algorithm is 7T(n/2) + Theta(n²) since there are only 7 recursive multiplications and Theta(n²) scalar additions and subtractions involved for computing the product.

10. Who discussed techniques for reducing the memory requirements for Strassen’s algorithm?
a) Strassen
b) Lederman
c) Bailey
d) Higham
Answer: c
Clarification: The submatrices formed at the levels of recursion consume space. Hence in order to overcome that Bailey discussed techniques for reducing the memory required.

11. What is the formula to calculate the element present in second row, first column of the product matrix?
a) M1+M7
b) M1+M3
c) M2+M4 – M5 + M7
d) M2+M4

Answer: d
Clarification: The element at second row, first column can be found by the formula M2 + M4, where M2 and M4 can be calculated by
M2= (A(2,1) + A(2,2)) B(1,1)
M4=A(2,2)(B(1,2) – B(1,1)).

12. Strassen’s Matrix Algorithm was proposed by _____________
a) Volker Strassen
b) Andrew Strassen
c) Victor Jan
d) Virginia Williams

Answer: a
Clarification: Strassen’s matrix multiplication algorithm was first published by Volker Strassen in the year 1969 and proved that the n³ general matrix multiplication algorithm wasn’t optimal.

13. How many iterating statements are involved in the naïve method of matrix multiplication?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: In the naïve method of matrix multiplication the number of iterating statements involved are 3, because of the presence of rows and columns in a matrix. The element in each row of the first matrix is multiplied with each element in the column of the second matrix.

14. Strassen’s algorithm is quite numerically stable as the naïve method.
a) True
b) False

Answer: b
Clarification: Strassen’s algorithm is too numerically unstable for some applications. The computed result C=AB satisfies the inequality with a unit roundoff error which corresponds to strong stability inequality(obtained by replacing matrix norms with absolute values of the matrix elements).

15. Compute the product matrix using Strassen’s matrix multiplication algorithm.
Given a11=1; a12=3;a21=5;a22=7
b11=8;b12=4;b21=6;b22=2
a) c11=20;c12=12;c21=100;c22=15
b) c11=22;c12=8;c21=90;c22=32
c) c11=15;c12=7;c21=80;c22=34
d) c11=26;c12=10;c21=82;c22=34
Answer: d
Clarification: The solution can be obtained by
C11=1*8 + 3*6 =8+18=26
C12=1*4 + 3*2 =4+6=10
C21=5*8 + 7*6 =40+42=82
C22= 5*4 + 7*2=20+14=34.

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.