Design and Analysis of Algorithms20815 marksNumerical: Edit distanceDP Algorithms
Define order statistics problem. Find the edit distance between 'cat' and 'car' using dynamic programming.
Define order statistics problem. Find the edit distance between 'cat' and 'car' using dynamic programming. [5]
--- Definition: Given a set (or array) $A$ of $n$ elements drawn from a totally ordered set, the $i$-th order statistic is the $i$-th smallest element of $A$. - Input: An array $A$ of $n$ elements and an integer $i$ where $1 \le i \le n$. - Output: The element $e \in A$ that is greater than exact...