Download DOC, SLIDE, PPTX
compute m[i,i+1]{m[1,2],m[2,3],…,m[n−1,n]}⏟(n−1) values{ℓ=2for i=1 to n−1 do m[i,i+1]=∞for k=i to i do ⋮compute m[i,i+2]{m[1,3],m[2,4],…,m[n−2,n]}⏟(n−2) values{ℓ=3for i=1 to n−2 do m[i,i+2]=∞for k=i to i+1 do ⋮compute m[i,i+3]{m[1,4],m[2,5],…,m[n−3,n]}⏟(n−3) values{ℓ=4for i=1 to n−3 do m[i,i+3]=∞for k=i to i+2 do ⋮\begin{align} \begin{aligned} \text{compute } m[i,i+1] \\ \underbrace{ \{ m[1,2],m[2,3], \dots ,m[n-1,n]\} }_{(n-1) \text{ values}} \end{aligned} & \begin{cases} & \ell=2 \\ & \text{for } i=1 \text{ to } n-1 \text{ do } \\ & \quad m[i,i+1]=\infty \\ & \quad \quad \text{for } k=i \text{ to } i \text{ do } \\ & \quad \quad \quad \vdots \end{cases} \\ \begin{aligned} \text{compute } m[i,i+2] \\ \underbrace{ \{ m[1,3],m[2,4], \dots ,m[n-2,n]\} }_{(n-2) \text{ values}} \end{aligned} & \begin{cases} & \ell=3 \\ & \text{for } i=1 \text{ to } n-2 \text{ do } \\ & \quad m[i,i+2]=\infty \\ & \quad \quad \text{for } k=i \text{ to } i+1 \text{ do } \\ & \quad \quad \quad \vdots \end{cases} \\ \begin{aligned} \text{compute } m[i,i+3] \\ \underbrace{ \{ m[1,4],m[2,5], \dots ,m[n-3,n]\} }_{(n-3) \text{ values}} \end{aligned} & \begin{cases} & \ell=4 \\ & \text{for } i=1 \text{ to } n-3 \text{ do } \\ & \quad m[i,i+3]=\infty \\ & \quad \quad \text{for } k=i \text{ to } i+2 \text{ do } \\ & \quad \quad \quad \vdots \end{cases} \end{align} compute m[i,i+1](n−1) values{m[1,2],m[2,3],…,m[n−1,n]}compute m[i,i+2](n−2) values{m[1,3],m[2,4],…,m[n−2,n]}compute m[i,i+3](n−3) values{m[1,4],m[2,5],…,m[n−3,n]}⎩⎨⎧ℓ=2for i=1 to n−1 do m[i,i+1]=∞for k=i to i do ⋮⎩⎨⎧ℓ=3for i=1 to n−2 do m[i,i+2]=∞for k=i to i+1 do ⋮⎩⎨⎧ℓ=4for i=1 to n−3 do m[i,i+3]=∞for k=i to i+2 do ⋮
OPTIMAL-BST-COST(p,n)for i←1 to n doc[i,i−1]←0c[i,i]←p[i]R[i,j]←iPS[1]←p[1]⟸PS[i]→ prefix-sum (i):Sum of all p[j] values for j≤ifor i←2 to n doPS[i]←p[i]+PS[i−1]⟸compute the prefix sumfor d←1 to n−1 do⟸BSTs with d+1 consecutive keysfor i←1 to n–d doj←i+dc[i,j]←∞for r←i to j doq←min{c[i,r−1]+c[r+1,j]}+PS[j]–PS[i−1]}if q<c[i,j] thenc[i,j]←qR[i,j]←rreturn c[1,n],R\begin{align*} & \text{OPTIMAL-BST-COST} (p, n) \\ & \quad \text{for} \ i \leftarrow 1 \ \text{to} \ n \ \text{do} \\ & \qquad c[i, i-1] \leftarrow 0 \\ & \qquad c[i, i] \leftarrow p[i] \\ & \qquad R[i, j] \leftarrow i \\ & \quad PS[1] \leftarrow p[1] \Longleftarrow PS[i] \rightarrow \text{ prefix-sum } (i): \text{Sum of all} \ p[j] \ \text{values for} \ j \leq i \\ & \quad \text{for} \ i \leftarrow 2 \ \text{to} \ n \ \text{do} \\ & \qquad PS[i] \leftarrow p[i] + PS[i-1] \Longleftarrow \text{compute the prefix sum} \\ & \quad \text{for} \ d \leftarrow 1 \ \text{to} \ n−1 \ \text{do} \Longleftarrow \text{BSTs with} \ d+1 \ \text{consecutive keys} \\ & \qquad \text{for} \ i \leftarrow 1 \ \text{to} \ n – d \ \text{do} \\ & \qquad \quad j \leftarrow i + d \\ & \qquad \quad c[i, j] \leftarrow \infty \\ & \qquad \quad \text{for} \ r \leftarrow i \ \text{to} \ j \ \text{do} \\ & \qquad \qquad q \leftarrow min\{c[i,r-1] + c[r+1, j]\} + PS[j] – PS[i-1]\} \\ & \qquad \qquad \text{if} \ q < c[i, j] \ \text{then} \\ & \qquad \qquad \quad c[i, j] \leftarrow q \\ & \qquad \qquad \quad R[i, j] \leftarrow r \\ & \quad \text{return} \ c[1, n], R \end{align*} OPTIMAL-BST-COST(p,n)for i←1 to n doc[i,i−1]←0c[i,i]←p[i]R[i,j]←iPS[1]←p[1]⟸PS[i]→ prefix-sum (i):Sum of all p[j] values for j≤ifor i←2 to n doPS[i]←p[i]+PS[i−1]⟸compute the prefix sumfor d←1 to n−1 do⟸BSTs with d+1 consecutive keysfor i←1 to n–d doj←i+dc[i,j]←∞for r←i to j doq←min{c[i,r−1]+c[r+1,j]}+PS[j]–PS[i−1]}if q<c[i,j] thenc[i,j]←qR[i,j]←rreturn c[1,n],R
TODO UPDATE CONTENT FOR YOUR COURSE NOTES
End−Of−Week−8−ModuleEnd-Of-Week-8-ModuleEnd−Of−Week−8−Module