Data Structure And Algorithm : Practice Questions and Answers

The line arr[i] += arr[j] * arr[k] reflects the recursive formula (Cn = \sumCi*C(n-i)).

All of the mentioned methods can be used to find the nth Catalan number.

Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines are the applications of Catalan numbers where as creation of head and tails for a given number of tosses is an application of Pascal's triangle.

Catalan numbers are given by: (2n!)/((n+1)!n!).

First Catalan number is given by n = 0.

So the 6th Catalan number will be given by n = 5, which is 42.

Catalan numbers are given by: (2n!)/((n+1)!n!).

For n = 0, we get C0 = 1.

For n = 3, we get C3 = 5.

For n = 4, we get C4 = 14.

For n = 5, we get C3 = 42.

arr[len][len] contains the length of the longest palindromic subsequence. So, len - arr[len][len] gives the minimum number of insertions required to form a palindrome.

A variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.

The given string is already a palindrome. So, no insertions are required.

The string can be converted to "efgfe" by inserting "f" or to "egfge" by inserting "g". Thus, only one insertion is required.

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.

In string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. To convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. Hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.

Dynamic programming and recursion can be used to solve the problem.

Rabin-Karp algorithm was invented by Richard Karp and Michael Rabin in 1987 for pattern searching in strings.

Rabin-Karp uses hashing. Every substring of the text is converted to a hash value and compared with the hash value of the pattern for fast matching.

When the number of valid shifts v is O(1) and q >= m, the matching time O(n) + O(m(v + n/q)) simplifies to O(n+m).

If q is large enough, spurious hits occur infrequently, making the cost of extra checking low.

Since Rabin-Karp is a pattern detection algorithm, it can be applied to detect plagiarism by searching for matching text patterns across documents.

The worst case running time is Theta((n-m+1)m). We write n-m+1 instead of n-m because there are n-m+1 different positions the pattern can start in the text.

Horner's rule is used to evaluate the pattern in Theta(m): p = P[m] + 10(P[m-1] + 10(P[m-2] + ... + 10(P[2] + 10P[1])...)).

Rabin-Karp Algorithm uses elementary number theoretic notions such as the equivalence of two numbers modulo a third number.