LCS= LONGES COMMON SUBSEQUENCE Give a recursive version of LCS-LENGTH with memor

Question

LCS= LONGES COMMON SUBSEQUENCE

Give 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

• Browse (All)
• Browse L
• Subjects

---