LCS= LONGES COMMON SUBSEQUENCE Give a recursive version of LCS-LENGTH with memor
ID: 3620373 • Letter: L
Question
LCS= LONGES COMMON SUBSEQUENCEGive a recursive version of LCS-LENGTH with memorization that runs in
O(mn)time.
(2)
Let k1<k2<k3 be three keys whose probabilities pi for search are:
0.2, 0.1, and 0.3. Suppose that the probabilities qi for every dummy
key di is 0.1.
show the tables e,w, and root as computed by the algorithm for
optimal binary search tress.
and construckt the optimal binary search tree
Explanation / Answer
A memorized version of LCS-LENGTH algorithm is: MEMOIZED-LCS-LENGTH ( ) for i=1 to m for j=1 to n c[i,j] =-1 return LOOKUP-LCS (m, n) LOOKUP-LCS (i,j) if i=0 or j=0 return if c[i,j]< > -1 return c[i,j] if (xi =yj) c[i,j] = LOOKUP-LCS(i-1,j-1) + 1 b[i,j] = result of c[i,j] + xi else if LOOKUP-LCS (i-1,j)>= LOOKUP-LCS (i,j-1) c[i,j] = c[i-1,j] b[i,j] = result of c[i-1,j] else c[i,j] = c[i,j-1] b[i,j] = result of c[i,j-1] return c[i,j]Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.