250+ TOP MCQs on Quickhull and Answers

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

1. ___________ is a method of constructing a smallest polygon out of n given points.
a) closest pair problem
b) quick hull problem
c) path compression
d) union-by-rank

Answer: b
Clarification: Quick hull is a method of constructing a smallest convex polygon out of n given points in a plane.

2. What is the other name for quick hull problem?
a) convex hull
b) concave hull
c) closest pair
d) path compression
Answer: a
Clarification: The other name for quick hull problem is convex hull problem whereas the closest pair problem is the problem of finding the closest distance between two points.

3. How many approaches can be applied to solve quick hull problem?
a) 1
b) 2
c) 3
d) 4
Answer: b
Clarification: Most commonly, two approaches are adopted to solve quick hull problem- brute force approach and divide and conquer approach.

4. What is the average case complexity of a quick hull algorithm?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)

Answer: b
Clarification: The average case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be O(N log N).

5. What is the worst case complexity of quick hull?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)

Answer: c
Clarification: The worst case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be O(N2).

6. What does the following diagram depict?
quickhull-questions-answers-q6
a) closest pair
b) convex hull
c) concave hull
d) path compression

Answer: b
Clarification: The above diagram is a depiction of convex hull, also known as quick hull, since it encloses n points into a convex polygon.

7. Which of the following statement is not related to quickhull algorithm?
a) finding points with minimum and maximum coordinates
b) dividing the subset of points by a line
c) eliminating points within a formed triangle
d) finding the shortest distance between two points

Answer: d
Clarification: Finding the shortest distance between two points belongs to closest pair algorithm while the rest is quickhull.

8. The quick hull algorithm runs faster if the input uses non- extreme points.
a) true
b) false
View Answer

Answer: a
Clarification: It is proved that the quick hull algorithm runs faster if the input uses non-extreme points and also, if it uses less memory.

9. To which type of problems does quick hull belong to?
a) numerical problems
b) computational geometry
c) graph problems
d) string problems
View Answer

Answer: b
Clarification: Quick hull problem and closest pair algorithms are some of the examples of computational problems.

10. Which of the following algorithms is similar to a quickhull algorithm?
a) merge sort
b) shell sort
c) selection sort
d) quick sort

Answer: d
Clarification: Quickhull algorithm is similar to a quick sort algorithm with respect to the run time average case and worst case efficiencies.

11. Who formulated quick hull algorithm?
a) Eddy
b) Andrew
c) Chan
d) Graham

Answer: a
Clarification: Eddy formulated quick hull algorithm. Graham invented graham scan. Andrew formulated Andrew’s algorithm and Chan invented Chan’s algorithm.

12. The time is taken to find the ‘n’ points that lie in a convex quadrilateral is?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)

Answer: a
Clarification: The time taken to find the ‘n’ points that lie in a convex quadrilateral is mathematically found to be O(N).

here is complete set of 1000+

250+ TOP MCQs on Minimum Cut and Answers

Data Structures & Algorithms Multiple Choice Questions on “Minimum Cut”.

1. Which algorithm is used to solve a minimum cut algorithm?
a) Gale-Shapley algorithm
b) Ford-Fulkerson algorithm
c) Stoer-Wagner algorithm
d) Prim’s algorithm
View Answer

Answer: c
Clarification: Minimum cut algorithm is solved using Stoer-Wagner algorithm. Maximum flow problem is solved using Ford-Fulkerson algorithm. Stable marriage problem is solved using Gale-Shapley algorithm.

2. ___________ is a partition of the vertices of a graph in two disjoint subsets that are joined by atleast one edge.
a) Minimum cut
b) Maximum flow
c) Maximum cut
d) Graph cut

Answer: a
Clarification: Minimum cut is a partition of the vertices in a graph 4. in two disjoint subsets joined by one edge. It is a cut that is minimal in some sense.

3. Minimum cut algorithm comes along with the maximum flow problem.
a) true
b) false

Answer: a
Clarification: Minimum cut algorithm is considered to be an extension of the maximum flow problem. Minimum cut is finding a cut that is minimal.

4. What does the given figure depict?
minimum-cut-questions-answers-q4
a) min cut problem
b) max cut problem
c) maximum flow problem
d) flow graph
View Answer

Answer: a
Clarification: The given figure is a depiction of min cut problem since the graph is partitioned to find the minimum cut.

5. ______________ separates a particular pair of vertices in a graph.
a) line
b) arc
c) cut
d) flow

Answer: c
Clarification: A cut separates a particular pair of vertices in a weighted undirected graph and has minimum possible weight.

6. What is the minimum number of cuts that a graph with ‘n’ vertices can have?
a) n+1
b) n(n-1)
c) n(n+1)/2
d) n(n-1)/2

Answer: c
Clarification: The mathematical formula for a graph with ‘n’ vertices can at the most have n(n-1)/2 distinct vertices.

7. What is the running time of Karger’s algorithm to find the minimum cut in a graph?
a) O(E)
b) O(|V|2)
c) O(V)
d) O(|E|)

Answer: b
Clarification: The running time of Karger’s algorithm to find the minimum cut is mathematically found to be O(|V|2).

8. _____________ is a family of combinatorial optimization problems in which a graph is partitioned into two or more parts with constraints.
a) numerical problems
b) graph partition
c) network problems
d) combinatorial problems

Answer: b
Clarification: Graph partition is a problem in which the graph is partitioned into two or more parts with additional conditions.

9. The weight of the cut is not equal to the maximum flow in a network.
a) true
b) false

Answer: b
Clarification: According to max-flow min-cut theorem, the weight of the cut is equal to the maximum flow that is sent from source to sink.

10. __________ is a data structure used to collect a system of cuts for solving min-cut problem.
a) Gomory-Hu tree
b) Gomory-Hu graph
c) Dancing tree
d) AA tree

Answer: a
Clarification: Gomory-Hu tree is a weighted tree that contains the minimum cuts for all pairs in a graph. It is constructed in |V|-1 max-flow computations.

11. In how many ways can a Gomory-Hu tree be implemented?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: Gomory-Hu tree can be implemented in two ways- sequential and parallel.

12. The running time of implementing naïve solution to min-cut problem is?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Answer: d
Clarification: The running time of min-cut algorithm using naïve implementation is mathematically found to be O(N2).

13. What is the running time of implementing a min-cut algorithm using bidirected edges in a graph?
a) O(N)
b) O(N log N)
c) O(N4)
d) O(N2)
Answer: c
Clarification: The running time of a min-cut algorithm using Ford-Fulkerson method of making edges birected in a graph is mathematically found to be O(N4).

14. Which one of the following is not an application of max-flow min-cut algorithm?
a) network reliability
b) closest pair
c) network connectivity
d) bipartite matching

Answer: b
Clarification: Network reliability, connectivity and bipartite matching are all applications of min-cut algorithm whereas closest pair is a different kind of problem.

15. What is the minimum cut of the following network?
minimum-cut-questions-answers-q15
a) ({1,3},{4,3},{4,5})
b) ({1,2},{2,3},{4,5})
c) ({1,0},{4,3},{4,2})
d) ({1,2},{3,2},{4,5})

Answer: a
Clarification: The minimum cut of the given graph network is found to be ({1,3},{4,3},{4,5}) and its capacity is 23.

complete set of 1000+

250+ TOP MCQs on Length of a Linked List using Recursion and Answers

Basic Data Structure Questions and Answers on “Length of a Linked List using Recursion”.

1. Consider the following iterative implementation used to find the length of a linked list:

struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(_____)
      {
          len++;
          temp = temp->next;
      }
      return len;
}

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

Answer: c
Clarification: The condition “temp != 0” should be checked to complete the above code.

2. What is the output of the following code?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(temp != 0)
      {
          len++;
          temp = temp->next;
      }
      return len;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, 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->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = get_len();
      printf("%d",len);
      return 0;
}

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

Answer: b
Clarification: The program prints the length of the linked list, which is 5.

3. What is the time complexity of the following iterative implementation used to find the length of a linked list?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(temp != 0)
      {
          len++;
          temp = temp->next;
      }
      return len;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, 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->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = get_len();
      printf("%d",len);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(logn)

Answer: b
Clarification: The time complexity of the above iterative implementation used to find the length of a linked list is O(n).

4. What is the output of the following code?

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

a) 0
b) Garbage value
c) Compile time error
d) Runtime error

Answer: a
Clarification: The program prints the length of the linked list, which is 0.

5. Which of the following can be the base case for the recursive implementation used to find the length of linked list?

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

a) if(current_node == 0) return 1
b) if(current_node->next == 0) return 1
c) if(current_node->next == 0) return 0
d) if(current_node == 0) return 0

Answer: d
Clarification: The line “if(current_node == 0) return 0” can be used as a base case in the recursive implementation used to find the length of a linked list. Note: The line “if(current_node->next == 0) return 1” cannot be used because it won’t work when the length of the linked list is zero.

6. Which of the following lines should be inserted to complete the following recursive implementation used to find the length of a linked list?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return _____;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, 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->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

a) recursive_get_len(current_node)
b) 1 + recursive_get_len(current_node)
c) recursive_get_len(current_node->next)
d) 1 + recursive_get_len(current_node->next)

Answer: d
Clarification: The line “1 + recursive_get_len(current_node->next)” should be inserted to complete the above code.

7. What is the output of the following code?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5,0}, n = 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->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

a) 6
b) 7
c) 8
d) 9
Answer: b
Clarification: The program prints the length of the linked list, which is 7.

8. What is the time complexity of the following code used to find the length of a linked list?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5,0}, n = 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->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Answer: b
Clarification: To find the length of the linked list, the program iterates over the linked list once. So, the time complexity of the above code is O(n).

9. What is the output of the following code?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5}, n = 6, 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->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

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

Answer: b
Clarification: The program prints the length of the linked list, which is 6.

10. How many times is the function recursive_get_len() called when the following code is executed?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5}, n = 6, 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->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

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

Answer: c
Clarification: The function is called “len + 1” times. Since the length of the linked list in the above code is 6, the function is called 6 + 1 = 7 times.

and Answers.

250+ TOP MCQs on Backtracking and Answers

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

1. Which of the problems cannot be solved by backtracking method?
a) n-queen problem
b) subset sum problem
c) hamiltonian circuit problem
d) travelling salesman problem

Answer: d
Clarification: N-queen problem, subset sum problem, Hamiltonian circuit problems can be solved by backtracking method whereas travelling salesman problem is solved by Branch and bound method.

2. Backtracking algorithm is implemented by constructing a tree of choices called as?
a) State-space tree
b) State-chart tree
c) Node tree
d) Backtracking tree
Answer: a
Clarification: Backtracking problem is solved by constructing a tree of choices called as the state-space tree. Its root represents an initial state before the search for a solution begins.

3. What happens when the backtracking algorithm reaches a complete solution?
a) It backtracks to the root
b) It continues searching for other possible solutions
c) It traverses from a different route
d) Recursively traverses through the same route

Answer: b
Clarification: When we reach a final solution using a backtracking algorithm, we either stop or continue searching for other possible solutions.

4. A node is said to be ____________ if it has a possibility of reaching a complete solution.
a) Non-promising
b) Promising
c) Succeeding
d) Preceding

Answer: b
Clarification: If a node has a possibility of reaching the final solution, it is called a promising node. Otherwise, it is non-promising.

5. In what manner is a state-space tree for a backtracking algorithm constructed?
a) Depth-first search
b) Breadth-first search
c) Twice around the tree
d) Nearest neighbour first

Answer: a
Clarification: A state-space tree for a backtracking algorithm is constructed in the manner of depth-first search so that it is easy to look into.

6. The leaves in a state-space tree represent only complete solutions.
a) true
b) false

Answer: b
Clarification: The leaves in a state space tree can either represent non-promising dead ends or complete solutions found by the algorithm.

7. In general, backtracking can be used to solve?
a) Numerical problems
b) Exhaustive search
c) Combinatorial problems
d) Graph coloring problems

Answer: c
Clarification: Backtracking approach is used to solve complex combinatorial problems which cannot be solved by exhaustive search algorithms.

8. Which one of the following is an application of the backtracking algorithm?
a) Finding the shortest path
b) Finding the efficient quantity to shop
c) Ludo
d) Crossword

Answer: d
Clarification: Crossword puzzles are based on backtracking approach whereas the rest are travelling salesman problem, knapsack problem and dice game.

9. Backtracking algorithm is faster than the brute force technique
a) true
b) false

Answer: a
Clarification: Backtracking is faster than brute force approach since it can remove a large set of answers in one test.

10. Which of the following logical programming languages is not based on backtracking?
a) Icon
b) Prolog
c) Planner
d) Fortran

Answer: d
Clarification: Backtracking algorithm form the basis for icon, planner and prolog whereas fortran is an ancient assembly language used in second generation computers.

11. The problem of finding a list of integers in a given specific range that meets certain conditions is called?
a) Subset sum problem
b) Constraint satisfaction problem
c) Hamiltonian circuit problem
d) Travelling salesman problem

Answer: b
Clarification: Constraint satisfaction problem is the problem of finding a list of integers under given constraints. Constraint satisfaction problem is solved using a backtracking approach.

12. Who coined the term ‘backtracking’?
a) Lehmer
b) Donald
c) Ross
d) Ford

Answer: a
Clarification: D.H. Lehmer was the first person to coin the term backtracking. Initially, the backtracking facility was provided using SNOBOL.

13. ___________ enumerates a list of promising nodes that could be computed to give the possible solutions of a given problem.
a) Exhaustive search
b) Brute force
c) Backtracking
d) Divide and conquer
Answer: c
Clarification: Backtracking is a general algorithm that evaluates partially constructed candidates that can be developed further without violating problem constraints.

14. The problem of finding a subset of positive integers whose sum is equal to a given positive integer is called as?
a) n- queen problem
b) subset sum problem
c) knapsack problem
d) hamiltonian circuit problem

Answer: b
Clarification: Subset sum problem is the problem of finding a subset using the backtracking algorithm when summed, equals a given integer.

15. The problem of placing n queens in a chessboard such that no two queens attack each other is called as?
a) n-queen problem
b) eight queens puzzle
c) four queens puzzle
d) 1-queen problem

Answer: a
Clarification: The problem of placing n-queens in a chessboard such that no two queens are vertical or horizontal or diagonal to each other is an n-queen problem. The problem only exists for n = 1, 4, 8.

and Answers.

250+ TOP MCQs on Edit Distance Problem and Answers

Data Structure Multiple Choice Questions on “Edit Distance Problem”.

1. Which of the following methods can be used to solve the edit distance problem?
a) Recursion
b) Dynamic programming
c) Both dynamic programming and recursion
d) Greedy Algorithm
Answer: c
Clarification: Both dynamic programming and recursion can be used to solve the edit distance problem.

2. The edit distance satisfies the axioms of a metric when the costs are non-negative.
a) True
b) False

Answer: a
Clarification: d(s,s) = 0, since each string can be transformed into itself without any change.
d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.
d(s1, s2) = d(s2, s1)
d(s1, s3) <= d(s1, s2) + d(s2, s3)
Thus, the edit distance satisfies the axioms of a metric.

3. Which of the following is an application of the edit distance problem?
a) Approximate string matching
b) Spelling correction
c) Similarity of DNA
d) Approximate string matching, Spelling Correction and Similarity of DNA

Answer: d
Clarification: All of the mentioned are the applications of the edit distance problem.

4. In which of the following cases will the edit distance between two strings be zero?
a) When one string is a substring of another
b) When the lengths of the two strings are equal
c) When the two strings are equal
d) The edit distance can never be zero
Answer: c
Clarification: The edit distance will be zero only when the two strings are equal.

5. Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.
a) True
b) False
View Answer

Answer: a
Clarification: Consider the strings “abcd” and “efghi”. The string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. The cost of transformation is 5, which is equal to the length of the larger string.

6. Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
a) 3
b) 4
c) 5
d) 6

Answer: b
Clarification: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. So, the edit distance is 4.

7. Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?
a) 0
b) 4
c) 2
d) 3

Answer: b
Clarification: The empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. Thus, the edit distance is 4.

8. Consider the following dynamic programming implementation of the edit distance problem:

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
               min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
               if(s1[i - 1] == s2[j - 1])
               {
                    if(arr[i-1][j-1] < min)
                       min = arr[i-1][j-1];
               }
               else
               {
                     if(arr[i-1][j-1] + 1 < min)
                         min = arr[i-1][j-1] + 1;
               }
                _____________;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be added to complete the above code?
a) arr[i-1][j] = min
b) arr[i][j-1] = min
c) arr[i-1][j-1] = min
d) arr[i][j] = min

Answer: d
Clarification: The line arr[i][j] = min completes the above code.

9. What is the time complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of two strings?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
               min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
               if(s1[i - 1] == s2[j - 1])
               {
                    if(arr[i-1][j-1] < min)
                       min = arr[i-1][j-1];
               }
               else
               {
                     if(arr[i-1][j-1] + 1 < min)
                         min = arr[i-1][j-1] + 1;
               }
                arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(m + n)
c) O(mn)
d) O(n)

Answer: c
Clarification: The time complexity of the above dynamic programming implementation of the edit distance problem is O(mn).

10. What is the space complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
               min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
               if(s1[i - 1] == s2[j - 1])
               {
                    if(arr[i-1][j-1] < min)
                       min = arr[i-1][j-1];
               }
               else
               {
                     if(arr[i-1][j-1] + 1 < min)
                         min = arr[i-1][j-1] + 1;
               }
                arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(m + n)
c) O(mn)
d) O(n)

Answer: c
Clarification: The space complexity of the above dynamic programming implementation of the edit distance problem is O(mn).

11. What is the output of the following code?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
      arr[i][0] = i;
     for(i = 0; i <= len2; i++)
      arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
              min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
              if(s1[i - 1] == s2[j - 1])
              {
                  if(arr[i-1][j-1] < min)
                      min = arr[i-1][j-1];
              }
              else
              {
                  if(arr[i-1][j-1] + 1 < min)
                     min = arr[i-1][j-1] + 1;
              }
              arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) 1
b) 2
c) 3
d) 4
Answer: d
Clarification: The program prints the edit distance between the strings “abcd” and “defg”, which is 4.

12. What is the value stored in arr[2][2] when the following code is executed?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
      int len1,len2,i,j,min;
      len1 = strlen(s1);
      len2 = strlen(s2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0;i <= len1; i++)
        arr[i][0] = i;
      for(i = 0; i <= len2; i++)
         arr[0][i] = i;
      for(i = 1; i <= len1; i++)
      {
           for(j = 1; j <= len2; j++)
           {
                 min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
                 if(s1[i - 1] == s2[j - 1])
                 {
                      if(arr[i-1][j-1] < min)
                        min = arr[i-1][j-1];
                 }
                 else
                 {
                      if(arr[i-1][j-1] + 1 < min)
                        min = arr[i-1][j-1] + 1;
                 }
                 arr[i][j] = min;
           }
      }
      return arr[len1][len2];
}
int main()
{
      char s1[] = "abcd", s2[] = "defg";
      int ans = edit_distance(s1, s2);
      printf("%d",ans);
      return 0;
}

a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: The value stored in arr[2][2] when the above code is executed is 2.

13. What is the output of the following code?

#include
#include
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
              min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
              if(s1[i - 1] == s2[j - 1])
              {
                  if(arr[i-1][j-1] < min)
                     min = arr[i-1][j-1];
              }
              else
              {
                  if(arr[i-1][j-1] + 1 < min)
                     min = arr[i-1][j-1] + 1;
              }
              arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "pqrstuv", s2[] = "prstuv";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

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

Answer: a
Clarification: The code prints the edit distance between the two strings, which is 1.

250+ TOP MCQs on Beaufort Cipher and Answers

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

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

Answer: b
Clarification: Beaufort 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 beaufort cipher is done using ____________
a) trithemius table
b) vigenere cycle
c) tabula recta
d) four square table

Answer: c
Clarification: Encryption of plain text in beaufort 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 reciprocal cipher?
a) vigenere cipher
b) autokey cipher
c) running key cipher
d) beaufort cipher

Answer: d
Clarification: A reciprocal cipher is a cipher in which if we try to encrypt the cipher text (using the same cipher) then we gets the plain text as a result. In other words, the process of decryption and encryption is exactly the same.

4. Which of the following is a difference between beaufort cipher and vigenere cipher?
a) they use different tables for encryption
b) vigenere cipher is poly alphabetic whereas beaufort cipher is mono alphabetic
c) vigenere cipher uses a key whereas no key is required for using beaufort cipher
d) they use the same table for encryption, but in a different manner
Answer: d
Clarification: Beaufort cipher is a variation of vigenere cipher. They use the same table i.e. tabula recta for encryption but the table is used in a different manner.

5. Beaufort cipher is a variant of ____________
a) autokey cipher
b) vigenere cipher
c) hill cipher
d) route cipher
Answer: b
Clarification: Beaufort cipher is a variant of vigenere cipher. The difference is that beaufort cipher uses tabula recta in a different manner for encryption.

6. The process of decryption is exactly same as that of encryption in beaufort cipher.
a) True
b) False

Answer: a
Clarification: Beaufort cipher is an example of reciprocal cipher. So that is why the process of decryption is exactly same as that of encryption in beaufort cipher.

7. What will be the plain text corresponding to cipher text “SEDGKG” if beaufort cipher is used with key as “KEY”?
a) PRISON
b) DEATHS
c) SAVEUS
d) ABUSED
Answer: c
Clarification: The process of decryption and encryption are exactly the same in beaufort cipher. So the corresponding plain text would be “SAVEUS”.

8. Beaufort cipher and variant beaufort cipher are same ciphers.
a) True
b) False

Answer: b
Clarification: Beaufort cipher is different from variant beaufort cipher. Variant beaufort cipher is a variant of beaufort cipher.

9. What will be the ciphered text corresponding to “” if beaufort cipher is used for encryption with key as “KEY”?
a) SBPISZTKZH
b) TCQJTAULAI
c) SELFQEXBHM
d) SPBISZKTZH

Answer: c
Clarification: For encrypting plain text choose the first letter of plain text (i.e. S) in the first horizontal row. Then find the first letter of key (i.e. K) in the column obtained in the first step. Finally, choose the leftmost letter of the row (i.e. S) obtained in the previous step. So the corresponding cipher text is “SELFQEXBHM”.

10. What will be the ciphered text corresponding to “ALGORITHM” if beaufort cipher is used for encryption with key as “KEY”?
a) BNJSWOAPV
b) KTSWNQRXM
c) AMIRVNZOU
d) MBPHJSNIU

Answer: b
Clarification: For encrypting plain text choose the first letter of plain text (i.e. A) in the first horizontal row. Then find the first letter of key (i.e. K) in the column obtained in the first step. Finally, choose the leftmost letter of the row (i.e. K) obtained in the previous step. So the corresponding cipher text is “KTSWNQRXM”.

and Answers.