250+ TOP MCQs on Recursive Insertion Sort and Answers

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Recursive Insertion Sort”.

1. Which of the following is an advantage of recursive insertion sort over its iterative version?
a) it has better time complexity
b) it has better space complexity
c) it is easy to implement
d) it has no significant advantage

Answer: d
Clarification: Recursive insertion sort has no significant advantage over iterative insertion sort. It is just a different way to implement the same.

2. Insertion sort is an online sorting algorithm.
a) true
b) false

Answer: a
Clarification: Insertion sort does not require the entire input data in the beginning itself in order to sort the array. It rather creates a partial solution in every step, so future elements are not required to be considered. Hence it is an online sorting algorithm.

3. What will be the recurrence relation of the code of recursive insertion sort?
a) T(n) = 2T(n/2) + n
b) T(n) = 2T(n/2) + c
c) T(n) = T(n-1) + n
d) T(n) = T(n-1) + c
Answer: c
Clarification: The recurrence relation of the code of recursive insertion sort is T(n) = T(n-1) + n. It can be solved by the method of substitution and is found to be equal to n2.

4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Insertion sort
d) Heap sort
Answer: c
Clarification: Out of the given options insertion sort is the only algorithm which is stable. It is because the elements with identical values appear in the same order in the output array as they were in the input array.

5. Which of the following is a variant of insertion sort?
a) selection sort
b) shell sort
c) odd-even sort
d) stupid sort

Answer: b
Clarification: Shell sort is a variation of insertion sort. It has a better running time in practical applications.

6. Recursive insertion sort is a comparison based sort.
a) True
b) False

Answer: a
Clarification: In insertion sort, we need to compare elements in order to find the minimum element in each iteration. So we can say that it uses comparisons in order to sort the array. Thus it qualifies as a comparison based sort.

7. What is the average case time complexity of recursive insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: c
Clarification: The overall recurrence relation of recursive insertion sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2).

8. What is the best case time complexity of recursive insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: a
Clarification: The best case time complexity of recursive insertion sort is O(n). It occurs in the case when the input is already/almost sorted.

9. What is the worst case time complexity of recursive insertion sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: c
Clarification: The overall recurrence relation of recursive insertion sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2).

10. How many swaps will be required in the worst case to sort an array having n elements using binary insertion sort?
a) n
b) 1
c) n * log n
d) log n
View Answer

Answer: d
Clarification: In a normal insertion sort at most n comparisons are required to sort the array. But if we also implement the concept of a binary sort in insertion sort then we can sort by having log n comparisons only.

11. What will be the base case for the code of recursive insertion sort ?
a)

if(n 

b)

if(n == 0)
return;

c)

if(n 

d)

If(n == 2)
return;

Answer: c
Clarification: The most appropriate condition for the base case of recursive insertion sort is when n is less than or equal 1 then return. It is because we know that an array with only 1 element is always sorted.

 
 

12. What is the auxiliary space complexity of recursive insertion sort?
a) O(n)
b) O(1)
c) O(n log n)
d) O(n2)

Answer: b
Clarification: The auxiliary space required by recursive insertion sort is O(1). So it qualifies as an in place sorting algorithm.

13. Which of the following is an adaptive sorting algorithm?
a) recursive insertion sort
b) merge sort
c) heap sort
d) selection sort

Answer: a
Clarification: Insertion sort is an adaptive algorithm. It is because the time complexity of the algorithm improves when the input array is almost sorted.

14. Which of the following sorting algorithm is in place?
a) recursive insertion sort
b) merge sort
c) radix sort
d) counting sort

Answer: a
Clarification: Out of the given options recursive insertion sort is the only algorithm which is in place. It is because the auxiliary space required by recursive bubble sort is O(1).

15.Choose the correct function for recursive insertion sort?
a)

void RecInsertionSort(int arr[], int n) 
{ 
	if (n <= 1) 
		return; 
	RecInsertionSort( arr, n-1 ); 	
	int key = arr[n-1]; 
	int j = n-2; 	
	while (j >= 0 && arr[j] > key) 
	{ 
		arr[j+1] = arr[j]; 
		j--; 
	} 
	arr[j+1] = key; 
}

b)

void RecInsertionSort(int arr[], int n) 
{ 
 
	if (n < 1) 
		return; 
 
	RecInsertionSort( arr, n-1 ); 
 
	int key = arr[n-1]; 
	int j = n-2; 
 
	while (j >= 0 || arr[j] > key) 
	{ 
		arr[j+1] = arr[j]; 
		j--; 
	} 
	arr[j] = key; 
}

c)

void RecInsertionSort(int arr[], int n) 
{ 
 
	if (n <1) 
		return; 
	RecInsertionSort( arr, n-1 ); 
 
	int key = arr[n-1]; 
	int j = n-2; 
 
	while (j >= 0 && arr[j] > key) 
	{ 
		arr[j+1] = arr[j]; 
		j--; 
	} 
	arr[j] = key; 
}

d)

void RecInsertionSort(int arr[], int n) 
{ 
 
	if (n <= 1) 
		return; 
 
	RecInsertionSort( arr, n-1 ); 
 
	int key = arr[n-1]; 
	int j = n-1; 
 
	while (j >= 0 || arr[j] > key) 
	{ 
		arr[j+1] = arr[j]; 
		j--; 
	} 
	arr[j+1] = key; 
}

Answer: a
Clarification: The base case of recursive bubble sort should be when n equal or less than 1 then return. Also we need to insert the element being chosen as key at its correct position in the sorted array to its left. All this needs to be done in a recursive code.

 
 

& Algorithms.

and Answers.

250+ TOP MCQs on Chan’s Algorithm and Answers

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

1. Chan’s algorithm is used for computing _________
a) Closest distance between two points
b) Convex hull
c) Area of a polygon
d) Shortest path between two points

Answer: b
Clarification: Chan’s algorithm is an output-sensitive algorithm used to compute the convex hull set of n points in a 2D or 3D space. Closest pair algorithm is used to compute the closest distance between two points.

2. What is the running time of Chan’s algorithm?
a) O(log n)
b) O(n log n)
c) O(n log h)
d) O(log h)

Answer: c
Clarification: The running time of Chan’s algorithm is calculated to be O(n log h) where h is the number of vertices of the convex hull.

3. Who formulated Chan’s algorithm?
a) Timothy
b) Kirkpatrick
c) Frank Nielsen
d) Seidel
Answer: a
Clarification: Chan’s algorithm was formulated by Timothy Chan. Kirkpatrick and Seidel formulated the Kirkpatrick-Seidel algorithm. Frank Nielsen developed a paradigm relating to Chan’s algorithm.

4. The running time of Chan’s algorithm is obtained from combining two algorithms.
a) True
b) False
Answer: a
Clarification: The O(n log h) running time of Chan’s algorithm is obtained by combining the running time of Graham’s scan [O(n log n)] and Jarvis match [O(nh)].

5. Which of the following is called the “ultimate planar convex hull algorithm”?
a) Chan’s algorithm
b) Kirkpatrick-Seidel algorithm
c) Gift wrapping algorithm
d) Jarvis algorithm

Answer: b
Clarification: Kirkpatrick-Seidel algorithm is called as the ultimate planar convex hull algorithm. Its running time is the same as that of Chan’s algorithm (i.e.) O(n log h).

6. Which of the following algorithms is the simplest?
a) Chan’s algorithm
b) Kirkpatrick-Seidel algorithm
c) Gift wrapping algorithm
d) Jarvis algorithm

Answer: a
Clarification: Chan’s algorithm is very practical for moderate sized problems whereas Kirkpatrick-Seidel algorithm is not. Although, they both have the same running time. Gift wrapping algorithm is a non-output sensitive algorithm and has a longer running time.

7. What is the running time of Hershberger algorithm?
a) O(log n)
b) O(n log n)
c) O(n log h)
d) O(log h)

Answer: b
Clarification: Hershberger’s algorithm is an output sensitive algorithm whose running time was originally O(n log n). He used Chan’s algorithm to speed up to O(n log h) where h is the number of edges.

8. Which of the following statements is not a part of Chan’s algorithm?
a) eliminate points not in the hull
b) recompute convex hull from scratch
c) merge previously calculated convex hull
d) reuse convex hull from the previous iteration

Answer: b
Clarification: Chan’s algorithm implies that the convex hulls of larger points can be arrived at by merging previously calculated convex hulls. It makes the algorithm simpler instead of recomputing every time from scratch.

9. Which of the following factors account more to the cost of Chan’s algorithm?
a) computing a single convex hull
b) locating points that constitute a hull
c) computing convex hull in groups
d) merging convex hulls
Answer: c
Clarification: The majority of the cost of the algorithm lies in the pre-processing (i.e.) computing convex hull in groups. To reduce cost, we reuse convex hulls from previous iterations.

10. Chan’s algorithm can be used to compute the lower envelope of a trapezoid.
a) true
b) false
Answer: a
Clarification: An extension of Chan’s algorithm can be used for proving solutions to complex problems like computing the lower envelope L(S) where S is a set of ‘n’ line segments in a trapezoid.

250+ TOP MCQs on Vertex Coloring and Answers

Data Structures & Algorithms Multiple Choice Questions on “Vertex Coloring”.

1. Which of the following is not a type of graph in computer science?
a) undirected graph
b) bar graph
c) directed graph
d) weighted graph

Answer: b
Clarification: According to the graph theory a graph is the collection of dots and lines. A bar graph is not a type of graph in computer science.

2. What is vertex coloring of a graph?
a) A condition where any two vertices having a common edge should not have same color
b) A condition where any two vertices having a common edge should always have same color
c) A condition where all vertices should have a different color
d) A condition where all vertices should have same color

Answer: a
Clarification: The condition for vertex coloring of a graph is that two vertices which share a common edge should not have the same color. If it uses k colors in the process then it is called k coloring of graph.

3. How many edges will a tree consisting of N nodes have?
a) Log(N)
b) N
c) N – 1
d) N + 1

Answer: c
Clarification: In order to have a fully connected tree it must have N-1 edges. So the correct answer will be N-1.

4. Minimum number of unique colors required for vertex coloring of a graph is called?
a) vertex matching
b) chromatic index
c) chromatic number
d) color number

Answer: c
Clarification: The minimum number of colors required for proper vertex coloring of graph is called chromatic number whereas the minimum number of colors required for proper edge coloring of graph is called chromatic index of a graph.

5. How many unique colors will be required for proper vertex coloring of an empty graph having n vertices?
a) 0
b) 1
c) 2
d) n
View Answer

Answer: b
Clarification: An empty graph is a graph without any edges. So the number of unique colors required for proper coloring of the graph will be 1.

6. How many unique colors will be required for proper vertex coloring of a bipartite graph having n vertices?
a) 0
b) 1
c) 2
d) n
View Answer

Answer: c
Clarification: A bipartite graph is a graph such that no two vertices of the same set are adjacent to each other. So the number of unique colors required for proper coloring of the graph will be 2.

7. Which of the following is an NP complete problem?
a) Hamiltonian cycle
b) Travelling salesman problem
c) Calculating chromatic number of graph
d) Finding maximum element in an array

Answer: c
Clarification: Calculating the chromatic number of a graph is an NP complete problem as a chromatic number of an arbitrary graph cannot be determined by using any convenient method.

8. How many unique colors will be required for proper vertex coloring of a line graph having n vertices?
a) 0
b) 1
c) 2
d) n

Answer: d
Clarification: A line graph of a simple graph is obtained by connecting two vertices with an edge. So the number of unique colors required for proper coloring of the graph will be n.

9. How many unique colors will be required for proper vertex coloring of a complete graph having n vertices?
a) 0
b) 1
c) n
d) n!

Answer: c
Clarification: A complete graph is the one in which each vertex is directly connected with all other vertices with an edge. So the number of unique colors required for proper coloring of the graph will be n.

10. Minimum number of colors required for proper edge coloring of a graph is called?
a) Chromatic color
b) Chromatic index
c) Edge matching
d) Color number

Answer: b
Clarification: The minimum number of colors required for proper edge coloring of graph is called chromatic index. It is also known as edge chromatic number.

11. What will be the chromatic number of the following graph?
vertex-coloring-multiple-choice-questions-answers-mcqs-q11
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Clarification: The given graph will only require 2 unique colors so that no two vertices connected by a common edge will have the same color. All nodes will have the same color except the central node.

12. How many unique colors will be required for vertex coloring of the following graph?
vertex-coloring-multiple-choice-questions-answers-mcqs-q12
a) 2
b) 3
c) 4
d) 5

Answer: c
Clarification: The given graph will require 4 unique colors so that no two vertices connected by a common edge will have the same color. So its chromatic number will be 4.

13. How many unique colors will be required for vertex coloring of the following graph?
vertex-coloring-multiple-choice-questions-answers-mcqs-q13
a) 2
b) 3
c) 4
d) 5

Answer: b
Clarification: The given graph will require 3 unique colors because two diagonal vertex are connected to each other directly. So its chromatic number will be 3.

14. Vertex coloring and chromatic number are one and the same.
a) True
b) False
View Answer

Answer: b
Clarification: Vertex coloring of a graph is an assignment of colors to the vertices of a graph such that no two adjacent vertices have the same color. Whereas chromatic number refers to the minimum number of unique colors required for vertex coloring of the graph.

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

Data Structure Multiple Choice Questions on “Length of a String using Recursion”.

1. Consider the following iterative implementation to find the length of the string:

#include
int get_len(char *s)
{
      int len = 0;
      while(________)
        len++;
      return len;
}
int main()
{
      char *s = "harsh";
      int len = get_len(s);
      printf("%d",len);
      return 0;
}

Which of the following lines should be inserted to complete the above code?
a) s[len-1] != 0
b) s[len+1] != 0
c) s[len] != ‘ ’
d) s[len] == ‘ ’

Answer: c
Clarification: The line “s[len] != ‘ ′” should be inserted to complete the above code.

2. What is the output of the following code?

#include
int get_len(char *s)
{
      int len = 0;
      while(s[len] != ' ')
        len++;
      return len;
}
int main()
{
      char *s = "lengthofstring";
      int len = get_len(s);
      printf("%d",len);
      return 0;
}

a) 14
b) 0
c) Compile time error
d) Runtime error

Answer: a
Clarification: The program prints the length of the string “lengthofstring”, which is 14.

3. What is the time complexity of the following code used to find the length of the string?

#include
int get_len(char *s)
{
      int len = 0;
      while(s[len] != ' ')
        len++;
      return len;
}
int main()
{
      char *s = "lengthofstring";
      int len = get_len(s);
      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 code used to find the length of the string is O(n).

4. What is the output of the following code?

#include
int get_len(char *s)
{
      int len = 0;
      while(s[len] != ' ')
        len++;
      return len;
}
int main()
{
      char *s = "";
      int len = get_len(s);
      printf("%d",len);
      return 0;
}

a) 0
b) 1
c) Runtime error
d) Garbage value
Answer: a
Clarification: The program prints the length of an empty string, which is 0.

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

#include
int get_len(char *s)
{
      int len = 0;
      while(s[len] != ' ')
        len++;
      return len;
}
int main()
{
      char *s = "";
      int len = get_len(s);
      printf("%d",len);
      return 0;
}

a) if(string[len] == 1) return 1
b) if(string[len+1] == 1) return 1
c) if(string[len] == ‘ ’) return 0
d) if(string[len] == ‘ ’) return 1

Answer: c
Clarification: “if(string[len] == ‘ ’) return 0” can be used as base case in the recursive implementation used to find the length of the string.

6. Consider the following recursive implementation used to find the length of a string:

#include
int recursive_get_len(char *s, int len)
{
      if(s[len] == 0)
        return 0;
      return ________;
}
int main()
{
      char *s = "abcdef";
      int len = recursive_get_len(s,0);
      printf("%d",len);
      return 0;
}

Which of the following lines should be inserted to complete the above code?
a) 1
b) len
c) recursive_get_len(s, len+1)
d) 1 + recursive_get_len(s, len+1)

Answer: d
Clarification: The line “1 + recursive_get_len(s, len+1)” should be inserted to complete the code.

7. What is the output of the following code?

#include
int recursive_get_len(char *s, int len)
{
      if(s[len] == 0)
        return 0;
      return 1 + recursive_get_len(s, len+1);
}
int main()
{
      char *s = "abcdef";
      int len = recursive_get_len(s,0);
      printf("%d",len);
      return 0;
}

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

Answer: b
Clarification: The above code prints the length of the string “abcdef”, which is 6.

8. What is the time complexity of the following recursive implementation used to find the length of the string?

#include
int recursive_get_len(char *s, int len)
{
      if(s[len] == 0)
        return 0;
      return 1 + recursive_get_len(s, len+1);
}
int main()
{
      char *s = "abcdef";
      int len = recursive_get_len(s,0);
      printf("%d",len);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Answer: b
Clarification: The time complexity of the above recursive implementation used to find the length of the string is O(n).

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

#include
int recursive_get_len(char *s, int len)
{
      if(s[len] == 0)
        return 0;
      return 1 + recursive_get_len(s, len+1);
}
int main()
{
      char *s = "adghjkl";
      int len = recursive_get_len(s,0);
      printf("%d",len);
      return 0;
}

a) 6
b) 7
c) 8
d) 9
Answer: c
Clarification: The function recursive_get_len() is called 8 times when the above code is executed.

10. What is the output of the following code?

#include
int recursive_get_len(char *s, int len)
{
      if(s[len] == 0)
        return 0;
      return 1 + recursive_get_len(s, len+1);
}
int main()
{
      char *s = "123-1-2-3";
      int len = recursive_get_len(s,0);
      printf("%d",len);
      return 0;
}

a) 3
b) 6
c) 9
d) 10
Answer: c
Clarification: The above program prints the length of the string “123-1-2-3”, which is 9.

and Answers.

250+ TOP MCQs on Eight Queens Problem and Answers

Data Structures & Algorithms Multiple Choice Questions on “Eight Queens Problem”.

1. Who published the eight queens puzzle?
a) Max Bezzel
b) Carl
c) Gauss
d) Friedrich

Answer: a
Clarification: The first Eight Queen Puzzle was published by Max Friedrich William Bezzel, who was a chess composer by profession in 1848. He was a German chess composer and the first person to publish the puzzle.

2. When was the Eight Queen Puzzle published?
a) 1846
b) 1847
c) 1848
d) 1849

Answer: c
Clarification: The first Eight Queen Puzzle was published by Max Friedrich William Bezzel, who was a German chess composer by profession. He published the puzzle in 1848.

3. Who published the first solution of the eight queens puzzle?
a) Franz Nauck
b) Max Bezzel
c) Carl
d) Friedrich

Answer: a
Clarification: The first solution to the Eight Queen Puzzle was given by Franz Nauck in 1850. While the first Eight Queen Puzzle was published by Max Friedrich William Bezzel, who was a German chess composer.

4. When was the first solution to Eight Queen Puzzle published?
a) 1850
b) 1847
c) 1848
d) 1849

Answer: a
Clarification: The first solution to the Eight Queen Puzzle was given by Franz Nauck in 1850. Max Friedrich William Bezzel, who was a German chess composer by profession published the puzzle in 1848.

5. Who published the extended version of eight queens puzzle?
a) Franz Nauck
b) Max Bezzel
c) Carl
d) Friedrich

Answer: a
Clarification: The first extended version to the Eight Queen Puzzle was given by Franz Nauck in 1850. Max Friedrich William Bezzel published the puzzle in 1848.

6. For how many queens was the extended version of Eight Queen Puzzle applicable for n*n squares?
a) 5
b) 6
c) 8
d) n

Answer: d
Clarification: The extended version given by Franz Nauck of the Eight Queen Puzzle was for n queens on n*n square chessboard. Earlier the puzzle was proposed with 8 queens on 8*8 board.

7. Who was the first person to find the solution of Eight Queen Puzzle using determinant?
a) Max Bezzel
b) Frank Nauck
c) Gunther
d) Friedrich

Answer: c
Clarification: S. Gunther was the first person to propose a solution to the eight queen puzzle using determinant. Max Friedrich William Bezzel published the puzzle and the first solution to the Eight Queen Puzzle was given by Franz Nauck.

8. Who proposed the depth first backtracking algorithm?
a) Edsger Dijkshtra
b) Max Bezzel
c) Frank Nauck
d) Carl Friedrich

Answer: a
Clarification: In 1972, depth first backtracking algorithm was proposed by Edsger Dijkshtra to illustrate the Eight Queen Puzzle. Max Friedrich William Bezzel published the puzzle and the first solution to the Eight Queen Puzzle was given by Franz Nauck.

9. How many solutions are there for 8 queens on 8*8 board?
a) 12
b) 91
c) 92
d) 93

Answer: c
Clarification: For 8*8 chess board with 8 queens there are total of 92 solutions for the puzzle. There are total of 12 fundamental solutions to the eight queen puzzle.

10. Who publish the bitwise operation method to solve the eight queen puzzle?
a) Zongyan Qiu
b) Martin Richard
c) Max Bezzel
d) Frank Nauck

Answer: a
Clarification: The first person to publish the bitwise operation method to solve the eight queen puzzle was Zongyan Qiu. After him, it was published by Martin Richard.

11. How many fundamental solutions are there for the eight queen puzzle?
a) 92
b) 10
c) 11
d) 12

Answer: d
Clarification: There are total of 12 fundamental solutions to the eight queen puzzle after removing the symmetrical solutions due to rotation. For 8*8 chess board with 8 queens there are total of 92 solutions for the puzzle.

12. Is it possible to have no four queens in a straight line as the part of one of the solution to the eight queen puzzle.
a) True
b) False

Answer: b
Clarification: No three queens lie in a straight line in one of the fundamental solution of the eight queen puzzle.

13. How many fundamental solutions are the for 3 queens on a 3*3 board?
a) 1
b) 12
c) 3
d) 0

Answer: d
Clarification: There are in total zero solution to the 3 queen puzzle for 3*3 chess board. Hence there are no fundamental solutions. For 8*8 chess board with 8 queens there are total of 12 fundamental solutions for the puzzle.

14. The six queen puzzle has a fewer solution than the five queen puzzle.
a) True
b) False

Answer: a
Clarification: There are total 4 solutions for the six queen puzzle and one fundamental solution while there are total of 10 solutions for 5 queen puzzle and 2 fundamental solutions.

15. Which ordered board is the highest enumerated board till now?
a) 25*25
b) 26*26
c) 27*27
d) 28*28

Answer: c
Clarification: The 27*27 board has the highest order board with total 234,907,967,154,122,528 solutions. It also has total of 29,363,495,934,315,694 fundamental solution.

& Algorithms.

250+ TOP MCQs on Wagner-Fischer Algorithm and Answers

Data Structure Multiple Choice Questions & Answers (MCQs) on “Wagner-Fischer Algorithm”.

1. Wagner–Fischer is a ____________ algorithm.
a) Brute force
b) Greedy
c) Dynamic programming
d) Recursive
Answer: c
Clarification: Wagner–Fischer belongs to the dynamic programming type of algorithms.

2. Wagner–Fischer algorithm is used to find ____________
a) Longest common subsequence
b) Longest increasing subsequence
c) Edit distance between two strings
d) Longest decreasing subsequence
Answer: c
Clarification: Wagner–Fischer algorithm is used to find the edit distance between two strings.

3. What is the edit distance between the strings “abcd” and “acbd” when the allowed operations are insertion, deletion and substitution?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: The string “abcd” can be changed to “acbd” by substituting “b” with “c” and “c” with “b”. Thus, the edit distance is 2.

4. For which of the following pairs of strings is the edit distance maximum?
a) sunday & monday
b) monday & tuesday
c) tuesday & wednesday
d) wednesday & thursday

Answer: d
Clarification: The edit distances are 2, 4, 4 and 5 respectively. Hence, the maximum edit distance is between the strings wednesday and thursday.

5. Consider the following implementation of the Wagner–Fischer algorithm:

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)
                      ____________;
              }
              else
              {
                  if(arr[i-1][j-1] + 1 < min)
                      min = arr[i-1][j-1] + 1;
              }
              arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}

Which of the following lines should be inserted to complete the above code?
a) arr[i][j] = min
b) min = arr[i-1][j-1] – 1;
c) min = arr[i-1][j-1].
d) min = arr[i-1][j-1] + 1;
View Answer

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

6. What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?
a) O(1)
b) O(n+m)
c) O(mn)
d) O(nlogm)

Answer: c
Clarification: The time complexity of the Wagner–Fischer algorithm is O(mn).

7. What is the space complexity of the above implementation of Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?
a) O(1)
b) O(n+m)
c) O(mn)
d) O(nlogm)

Answer: c
Clarification: The space complexity of the above Wagner–Fischer algorithm is O(mn).

8. 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[] = "somestring", s2[] = "anotherthing";
      int ans = edit_distance(s1, s2);
      printf("%d",ans);
      return 0;
}

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

Answer: a
Clarification: The program prints the edit distance between the strings “somestring” and “anotherthing”, which is 6.

9. What is the value stored in arr[3][3] when the below 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[] = "somestring", s2[] = "anotherthing";
      int ans = edit_distance(s1, s2);
      printf("%d",ans);
      return 0;
}

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

Answer: c
Clarification: The value stored in arr[3][3] is 3.

10. 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[] = "dcba";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

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

Answer: d
Clarification: The program prints the edit distance between the strings “abcd” and “dcba”, which is 4.

& Algorithms.

and Answers.