Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Closest Pair Problem”.

1. Which of the following areas do closest pair problem arise?
a) computational geometry
b) graph colouring problems
c) numerical problems
d) string matching

Answer: a
Clarification: Closest pair problem arises in two most important areas- computational geometry and operational research.

2. Which approach is based on computing the distance between each pair of distinct points and finding a pair with the smallest distance?
a) Brute force
b) Exhaustive search
c) Divide and conquer
d) Branch and bound

Answer: a
Clarification: Brute force is a straight forward approach that solves closest pair problem using that algorithm.

3. What is the runtime efficiency of using brute force technique for the closest pair problem?
a) O(N)
b) O(N log N)
c) O(N²)
d) O(N³ log N)

Answer: c
Clarification: The efficiency of closest pair algorithm by brute force technique is mathematically found to be O(N²).

4. The most important condition for which closest pair is calculated for the points (p_i, p_j) is?
a) i>j
b) i!=j
c) i=j
d) i

Answer: d
Clarification: To avoid computing the distance between the same pair of points twice, we consider only the pair of points (p_i, p_j) for which i

5. What is the basic operation of closest pair algorithm using brute force technique?
a) Euclidean distance
b) Radius
c) Area
d) Manhattan distance

Answer: a
Clarification: The basic operation of closest pair algorithm is Euclidean distance and its formula is given by d=√(x_i-x_j)²+(y_i-y_j)².

6. Which of the following is similar to Euclidean distance?
a) Manhattan distance
b) Pythagoras metric
c) Chebyshev distance
d) Heuristic distance

Answer: b
Clarification: In older times, Euclidean distance metric is also called a Pythagoras metric which is the length of the line segment connecting two points.

7. Which of the following strategies does the following diagram depict?

a) Divide and conquer strategy
b) Brute force
c) Exhaustive search
d) Backtracking

Answer: b
Clarification: Brute force is a straight forward approach to solve critical problems. Here, we use brute force technique to find the closest distance between p1 and p2.

8. Manhattan distance is an alternative way to define a distance between two points.
a) true
b) false
View Answer

Answer: a
Clarification: Manhattan distance is an alternative way to calculate distance. It is the distance between two points measured along axes at right angles.

9. What is the optimal time required for solving the closest pair problem using divide and conquer approach?
a) O(N)
b) O(log N)
c) O(N log N)
d) O(N²)

Answer: c
Clarification: The optimal time for solving using a divide and conquer approach is mathematically found to be O(N log N).

10. In divide and conquer, the time is taken for merging the subproblems is?
a) O(N)
b) O(N log N)
c) O(N²)
d) O(log N)
Answer: b
Clarification: The time taken for merging the smaller subproblems in a divide and conquer approach is mathematically found to be O(N log N).

11. The optimal time obtained through divide and conquer approach using merge sort is the best case efficiency.
a) true
b) false
Answer: a
Clarification: The optimal time obtained through divide and conquer approach is the best class efficiency and it is given by Ω(N log N).

12. Which of the following strategies does the following diagram depict?

a) Brute force
b) Divide and conquer
c) Exhaustive search
d) Branch and bound

Answer: b
Clarification: The above diagram depicts the implementation of divide and conquer. The problem is divided into sub problems and are separated by a line.

13. Which of the points are closer to each other?

a) p1 and p11
b) p3 and p8
c) p2 and p3
d) p9 and p10

Answer: c
Clarification: From symmetry, we determine that the closest pair is p2 and p3. But the exact calculations have to be done using Euclid’s algorithm.

& Algorithms.

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Stable Marriage Problem”.

1. Stable marriage problem is an example of?
a) Branch and bound algorithm
b) Backtracking algorithm
c) Greedy algorithm
d) Divide and conquer algorithm

Answer: b
Clarification: Stable marriage problem is an example for recursive algorithm because it recursively uses backtracking algorithm to find an optimal solution.

2. Which of the following algorithms does Stable marriage problem uses?
a) Gale-Shapley algorithm
b) Dijkstra’s algorithm
c) Ford-Fulkerson algorithm
d) Prim’s algorithm

Answer: a
Clarification: Stable marriage problem uses Gale-Shapley algorithm. Maximum flow problem uses Ford-Fulkerson algorithm. Prim’s algorithm involves minimum spanning tree.

3. An optimal solution satisfying men’s preferences is said to be?
a) Man optimal
b) Woman optimal
c) Pair optimal
d) Best optimal

Answer: a
Clarification: An optimal solution satisfying men’s preferences are said to be man optimal. An optimal solution satisfying woman’s preferences are said to be woman optimal.

4. When a free man proposes to an available woman, which of the following happens?
a) She will think and decide
b) She will reject
c) She will replace her current mate
d) She will accept

Answer: d
Clarification: When a man proposes to an available woman, she will accept his proposal irrespective of his position on his preference list.

5. If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable.
a) True
b) False

Answer: a
Clarification: If there are n couples such that a man and a woman are not married, and if they prefer each other to their actual partners, the assignment is unstable.

6. How many 2*2 matrices are used in this problem?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: Two 2*2 matrices are used. One for men representing corresponding woman and ranking and the other for women.

7. What happens when a free man approaches a married woman?
a) She simply rejects him
b) She simply replaces her mate with him
c) She goes through her preference list and accordingly, she replaces her current mate with him
d) She accepts his proposal
View Answer

Answer: c
Clarification: If the preference of the man is greater, she replaces her current mate with him, leaving her current mate free.

8. In case of stability, how many symmetric possibilities of trouble can occur?
a) 1
b) 2
c) 4
d) 3

Answer: b
Clarification: Possibilities- There might be a woman pw, preferred to w by m, who herself prefers m to be her husband and the same applies to man as well.

9. Consider the following ranking matrix. Assume that M1 and W2 are married. Now, M2 approaches W2. Which of the following happens?

a) W2 replaces M1 with M2
b) W2 rejects M2
c) W2 accepts both M1 and M2
d) W2 rejects both M1 and M2

Answer: a
Clarification: W2 is married to M1. But the preference of W2 has M2 before M1. Hence, W2 replaces M1 with M2.

10. Consider the following ranking matrix. Assume that M1 and W1 are married and M2 and W3 are married. Now, whom will M3 approach first?

a) W1
b) W2
c) W3
d) All three

Answer: c
Clarification: M3 will approach W3 first. Since W3 is married and since her preference list has her current mate before M3, she rejects his proposal.

11. Who formulated a straight forward backtracking scheme for stable marriage problem?
a) McVitie and Wilson
b) Gale
c) Ford and Fulkerson
d) Dinitz
Answer: a
Clarification: McVitie and Wilson formulated a much faster straight forward backtracking scheme for stable marriage problem. Ford and Fulkerson formulated Maximum flow problem.

12. Can stable marriage cannot be solved using branch and bound algorithm.
a) True
b) False

Answer: b
Clarification: Stable marriage problem can be solved using branch and bound approach because branch and bound follows backtracking scheme with a limitation factor.

13. What is the prime task of the stable marriage problem?
a) To provide man optimal solution
b) To provide woman optimal solution
c) To determine stability of marriage
d) To use backtracking approach

Answer: c
Clarification: The prime task of stable marriage problem is to determine stability of marriage (i.e) finding a man and a woman who prefer each other to others.

14. Which of the following problems is related to stable marriage problem?
a) Choice of school by students
b) N-queen problem
c) Arranging data in a database
d) Knapsack problem

Answer: a
Clarification: Choice of school by students is the most related example in the given set of options since both school and students will have a preference list.

15. What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?
a) O(N)
b) O(N log N)
c) O(N²)
d) O(log N)

Answer: c
Clarification: The time efficiency of Gale-Shapley algorithm is mathematically found to be O(N²) where N denotes stable marriage problem.

Data Structure Multiple Choice Questions on “String Reversal using Recursion”.

1. Consider the following iterative implementation used to reverse a string:

#include
#include
void reverse_string(char *s)
{
     int len = strlen(s);
     int i,j;
     i=0;
     j=len-1;
     while(______)
     {
         char tmp = s[i];
         s[i] = s[j];
         s[j] = tmp;
         i++;
         j--;
     }
}

Which of the following lines should be inserted to complete the above code?
a) i > j
b) i < len
c) j > 0
d) i < j
Answer: d
Clarification: The line “i < j” should be inserted to complete the above code.

2. What is the output of the following code?

#include
#include
void reverse_string(char *s)
{
     int len = strlen(s);
     int i,j;
     i=0;
     j=len-1;
     while(i < j)
     {
         char tmp = s[i];
         s[i] = s[j];
         s[j] = tmp;
         i++;
         j--;
     }
}
int main()
{
      char s[100] = "reverse";
      reverse_string(s);
      printf("%s",s);
      return 0;
}

a) ersevre
b) esrever
c) eserver
d) eresevr

Answer: b
Clarification: The program reverses the string “reverse” and prints “esrever”.

3. What is the time complexity of the above code used to reverse a string?
a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
Answer: b
Clarification: The time complexity of the above code used to reverse a string is O(n).

4. What does the following code do?

#include
#include
void reverse_string(char *s)
{
     int len = strlen(s);
     int i,j;
     i=0;
     j=len-1;
     while(i < j)
     {
         char tmp = s[i];
         s[i] = s[j];
         s[j] = tmp;
         i++;
         j--;
     }
}
int main()
{
      char s[100] = "abcdefg";
      char t[100];
      strcpy(t,s);
      reverse_string(s);
      if(strcmp(t,s) == 0)
        printf("Yes");
      else
        printf("No");
      return 0;
}

a) Copies a string to another string
b) Compares two strings
c) Reverses a string
d) Checks if a string is a palindrome

Answer: d
Clarification: The main purpose of the above code is to check if a string is a palindrome.

5. What is the output of the following code?

#include
#include
void reverse_string(char *s)
{
     int len = strlen(s);
     int i,j;
     i=0;
     j=len-1;
     while(i < j)
     {
         char tmp = s[i];
         s[i] = s[j];
         s[j] = tmp;
         i++;
         j--;
     }
}
int main()
{
      char s[100] = "rotator";
      char t[100];
      strcpy(t,s);
      reverse_string(s);
      if(strcmp(t,s) == 0)
        printf("Yes");
      else
        printf("No");
      return 0;
}

a) Yes
b) No
c) Runtime error
d) Compile time error

Answer: a
Clarification: The program checks if a string is a palindrome. Since the string rotator is a palindrome, it prints “yes”.

6. Consider the following recursive implementation used to reverse a string:

void recursive_reverse_string(char *s, int left, int right)
{
     if(left < right)
     {
         char tmp = s[left];
         s[left] = s[right];
         s[right] = tmp;
         _________;
     }
}

Which of the following lines should be inserted to complete the above code?
a) recursive_reverse_string(s, left+1, right+1)
b) recursive_reverse_string(s, left-1, right-1)
c) recursive_reverse_string(s, left+1, right-1)
d) recursive_reverse_string(s, left-1, right+1)

Answer: c
Clarification: The line “recursive_reverse_string(s, left+1, right-1)” should be inserted to complete the above code.

7. What is the output of the following code?

#include
#include
void recursive_reverse_string(char *s, int left, int right)
{
     if(left < right)
     {
         char tmp = s[left];
         s[left] = s[right];
         s[right] = tmp;
         recursive_reverse_string(s, left+1, right-1);
     }
}
int main()
{
     char s[100] = "recursion";
     int len = strlen(s);
     recursive_reverse_string(s,0,len-1);
     printf("%s",s);
     return 0;
}

a) recursion
b) nsoirucer
c) noisrcuer
d) noisrucer
Answer: d
Clarification: The program prints the reversed string of “recursion”, which is “noisrucer”.

8. How many times is the function recursive_reverse_string() called when the following code is executed?

#include
#include
void recursive_reverse_string(char *s, int left, int right)
{
     if(left < right)
     {
         char tmp = s[left];
         s[left] = s[right];
         s[right] = tmp;
         recursive_reverse_string(s, left+1, right-1);
     }
}
int main()
{
     char s[100] = "madam";
     int len = strlen(s);
     recursive_reverse_string(s,0,len-1);
     printf("%s",s);
     return 0;
}

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

Answer: a
Clarification: The function recursive_reverse_string() is called 3 times when the above code is executed.

9. What is the time complexity of the above recursive implementation used to reverse a string?
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 reverse a string is O(n).

10. In which of the following cases is the reversal of a string not equal to the original string?
a) Palindromic strings
b) Strings of length 1
c) Empty String
d) Strings of length 2

Answer: d
Clarification: String “ab” is a string of length 2 whose reversal is not the same as the given one. Palindromic Strings, String of length 1 and Empty Strings case – the reversal is the same as the one given.

Data Structures & Algorithms Multiple Choice Questions on “Fractional Knapsack Problem”.

1. Fractional knapsack problem is also known as __________
a) 0/1 knapsack problem
b) Continuous knapsack problem
c) Divisible knapsack problem
d) Non continuous knapsack problem
View Answer

Answer: b
Clarification: Fractional knapsack problem is also called continuous knapsack problem. Fractional knapsack is solved using dynamic programming.

2. Fractional knapsack problem is solved most efficiently by which of the following algorithm?
a) Divide and conquer
b) Dynamic programming
c) Greedy algorithm
d) Backtracking

Answer: c
Clarification: Greedy algorithm is used to solve this problem. We first sort items according to their value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. At the end, we add the next item as much as we can.

3. What is the objective of the knapsack problem?
a) To get maximum total value in the knapsack
b) To get minimum total value in the knapsack
c) To get maximum weight in the knapsack
d) To get minimum weight in the knapsack
Answer: a
Clarification: The objective is to fill the knapsack of some given volume with different materials such that the value of selected items is maximized.

4. Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
a) In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible
b) Both are the same
c) 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming
d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible

Answer: d
Clarification: In fractional knapsack problem we can partially include an item into the knapsack whereas in 0/1 knapsack we have to either include or exclude the item wholly.

5. Time complexity of fractional knapsack problem is ____________
a) O(n log n)
b) O(n)
c) O(n²)
d) O(nW)

Answer: a
Clarification: As the main time taking a step is of sorting so it defines the time complexity of our code. So the time complexity will be O(n log n) if we use quick sort for sorting.

6. Fractional knapsack problem can be solved in time O(n).
a) True
b) False

Answer: a
Clarification: It is possible to solve the problem in O(n) time by adapting the algorithm for finding weighted medians.

7. Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.
a) 60
b) 80
c) 100
d) 40

Answer: a
Clarification: The value/weight ratio are-{2,3,4}. So we include the second and third items wholly into the knapsack. This leaves only 5 units of volume for the first item. So we include the first item partially.
Final value = 20+30+(40/4)=60.

8. The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
a) True
b) False

Answer: a
Clarification: As fractional knapsack gives extra liberty to include the object partially which is not possible with 0/1 knapsack, thus we get better results with a fractional knapsack.

9. The main time taking step in fractional knapsack problem is ___________
a) Breaking items into fraction
b) Adding items into knapsack
c) Sorting
d) Looping through sorted items

Answer: c
Clarification: The main time taking step is to sort the items according to their value/weight ratio. It defines the time complexity of the code.

10. Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.
a) 100, 80
b) 110, 70
c) 130, 110
d) 110, 80

Answer: d
Clarification: Assuming items to be divisible-
The value/weight ratio are {3, 2, 4}.So we include third and first items wholly. So, now only 15 units of volume are left for second item. So we include it partially.
Final volume = 20+60+50x(15/25)=80+30=110
Assuming items to be indivisible- In this case we will have to leave one item due to insufficient capacity.
Final volume = 60 + 20 = 80.

& Algorithms.

Multiple Choice Questions and Answers.

Data Structure Multiple Choice Questions on “Longest Common Subsequence”.

1. Which of the following methods can be used to solve the longest common subsequence problem?
a) Recursion
b) Dynamic programming
c) Both recursion and dynamic programming
d) Greedy algorithm

Answer: c
Clarification: Both recursion and dynamic programming can be used to solve the longest subsequence problem.

2. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?
a) 9
b) 8
c) 7
d) 6
Answer: c
Clarification: The longest common subsequence is “PRTPQRS” and its length is 7.

3. Which of the following problems can be solved using the longest subsequence problem?
a) Longest increasing subsequence
b) Longest palindromic subsequence
c) Longest bitonic subsequence
d) Longest decreasing subsequence
Answer: b
Clarification: To find the longest palindromic subsequence in a given string, reverse the given string and then find the longest common subsequence in the given string and the reversed string.

4. Longest common subsequence is an example of ____________
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer

Answer: b
Clarification: Longest common subsequence is an example of 2D dynamic programming.

5. What is the time complexity of the brute force algorithm used to find the longest common subsequence?
a) O(n)
b) O(n²)
c) O(n³)
d) O(2ⁿ)

Answer: d
Clarification: The time complexity of the brute force algorithm used to find the longest common subsequence is O(2ⁿ).

6. Consider the following dynamic programming implementation of the longest common subsequence problem:

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
            for(j = 1; j <= len2; j++)
            {
                 if(str1[i-1] == str2[j - 1])
                  ______________;
                else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
            }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = " abcedfg", str2[] = "bcdfh";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

Which of the following lines completes the above code?
a) arr[i][j] = 1 + arr[i][j].
b) arr[i][j] = 1 + arr[i – 1][j – 1].
c) arr[i][j] = arr[i – 1][j – 1].
d) arr[i][j] = arr[i][j].

Answer: b
Clarification: The line, arr[i][j] = 1 + arr[i – 1][j – 1] completes the above code.

7. What is the time complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
            for(j = 1; j <= len2; j++)
            {
                 if(str1[i-1] == str2[j - 1])
                  arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
            }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = " abcedfg", str2[] = "bcdfh";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

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

Answer: d
Clarification: The time complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

8. What is the space complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
            for(j = 1; j <= len2; j++)
            {
                 if(str1[i-1] == str2[j - 1])
                  arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
            }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = " abcedfg", str2[] = "bcdfh";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

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

Answer: d
Clarification: The space complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

9. What is the output of the following code?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
          for(j = 1; j <= len2; j++)
          {
              if(str1[i-1] == str2[j - 1])
                  arr[i][j] = 1 + arr[i - 1][j - 1];
              else
                  arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

a) 3
b) 4
c) 5
d) 6
Answer: b
Clarification: The program prints the length of the longest common subsequence, which is 4.

10. Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ?
a) hgmq
b) cfnq
c) bfmq
d) fgmna

Answer: d
Clarification: The length of the longest common subsequence is 4. But ‘fgmna’ is not the longest common subsequence as its length is 5.

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

#include
#include
int max_num(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
           for(j = 1; j <= len2; j++)
           {
                if(str1[i-1] == str2[j - 1])
                    arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                    arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
           }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

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

Answer: a
Clarification: The value stored in arr[2][3] is 1.

12. What is the output of the following code?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
           for(j = 1; j <= len2; j++)
           {
                if(str1[i-1] == str2[j - 1])
                   arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
           }
      }
      return arr[len1][len2];
}
int main()
{
     char str1[] = "abcd", str2[] = "efgh";
     int ans = lcs(str1,str2);
     printf("%d",ans);
     return 0;
}

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

Answer: d
Clarification: The program prints the length of the longest common subsequence, which is 0.

contest

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

1. Which of the following cipher does not require a key for encrypting plain text?
a) atbash cipher
b) affine cipher
c) playfair cipher
d) vigenere cipher

Answer: a
Clarification: Out of the given options only atbash cipher does not require a key for encryption. Atbash cipher is an example of a substitution cipher.

2. Atbash cipher was originally used for encrypting _____________
a) english alphabet
b) greek alphabet
c) hebrew alphabet
d) hindi alphabet

Answer: c
Clarification: Atbash cipher was originally built to encrypt hebrew alphabet. But it can be used to encrypt any type of alphabets.

3. Which of the following cipher is a special case of affine cipher?
a) Vigenere cipher
b) Autokey cipher
c) Atbash cipher
d) Hill cipher
Answer: c
Clarification: Atbash cipher is a special case of affine cipher. We have to assume a=b=25 as the key in affine cipher to get the same encryption.

4. Choose the weakest cipher from the following?
a) vigenere cipher
b) rail fence cipher
c) hill cipher
d) atbash cipher
Answer: d
Clarification: Atbash cipher is the weakest cipher out of the given options. This is because it is a simple mono alphabetic substitution cipher with almost no security. It can be cracked without even knowing which technique has been used for encryption.

5. Which of the following is a mono alphabetic substitution cipher?
a) vigenere cipher
b) one time pad cipher
c) play fair cipher
d) atbash cipher

Answer: d
Clarification: Atbash cipher is the only mono alphabetic substitution cipher out of the given options. All the remaining options fall under the category of poly alphabetic cipher.

6. Atbash cipher is less secure than affine cipher.
a) True
b) False

Answer: a
Clarification: Affine cipher is more secure as compared to pigpen cipher. Atbash cipher is a special case of affine cipher and can be cracked without even knowing which technique has been used for encryption.

7. Atbash cipher is an example of?
a) Mono alphabetic substitution cipher
b) Transposition cipher
c) Poly alphabetic substitution cipher
d) Geometric substitution cipher

A - Z	  J - Q	    S - H
B - Y	  K - P	    T - G
C - X	  L - O	    U - F
D - W	  M - N	    V - E
E - V	  N - M	    W - D
F - U	  O - L	    X - C
G - T	  P - K	    Y - B
H - S	  Q - J	    Z - A
I - R	  R - I

8. Atbash cipher cannot be cracked until the exact type of encryption of ciphered text is known.
a) True
b) False

Answer: b
Clarification: Atbash cipher is a very weak cipher. It can be easily broken without even knowing the exact technique which has been used for encryption. We can just assume the ciphered text to be a substitution cipher in order to crack it.

9. What will be the ciphered text corresponding to plain text “SECRET” if atbash cipher is used for encryption?
a) VHIXVG
b) HVXIVG
c) HXVIVG
d) VIHXIV

A - Z	  J - Q	    S - H
B - Y	  K - P	    T - G
C - X	  L - O	    U - F
D - W	  M - N	    V - E
E - V	  N - M	    W - D
F - U	  O - L	    X - C
G - T	  P - K	    Y - B
H - S	  Q - J	    Z - A
I - R	  R - I

10. What will be the plain text corresponding to ciphered text “MAO” if atbash cipher is used for encryption?
a) NZL
b) IND
c) AUS
d) ENG

A - Z	  J - Q	    S - H
B - Y	  K - P	    T - G
C - X	  L - O	    U - F
D - W	  M - N	    V - E
E - V	  N - M	    W - D
F - U	  O - L	    X - C
G - T	  P - K	    Y - B
H - S	  Q - J	    Z - A
I - R     R - I

11. Which of the following is not true about atbash cipher?
a) it is a mono alphabetic substitution cipher
b) it can only be used to encrypt hebrew alphabet
c) it is a special case of affine cipher
d) it is weaker than playfair cipher

Answer: b
Clarification: Atbash cipher was originally built to encrypt hebrew alphabet. But it can be used to encrypt any type of alphabets.