McqMate

Q. |
## In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string. |

A. | true |

B. | false |

C. | answer: b |

D. | explanation: in the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. for example, consider the string “abc”. the string can be converted to “abcba” by inserting “a” and “b”. the number of insertions is two, which is equal to length minus one. |

Answer» B. false | |

Explanation: the string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. thus, only one insertion is required. |

837

0

Do you find this helpful?

6

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?
- Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
- Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
- In which of the following cases the minimum no of insertions to form palindrome is maximum?
- Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
- What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
- For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence?
- 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.
- Which of the following takes O(n) time in worst case in array implementation of stack?
- Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.