CE100 Algorithms and Programming II

CE100 Algorithms and Programming II

Week-6 (Matrix Chain Order / LCS)

Spring Semester, 2021-2022

Download DOC, SLIDE, PPTX

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Matrix Chain Order / Longest Common Subsequence

Outline

  • Elements of Dynamic Programming
    • Optimal Substructure
    • Overlapping Subproblems
RTEU CE100 Week-6
CE100 Algorithms and Programming II
  • Recursive Matrix Chain Order Memoization
    • Top-Down Approach
    • RMC
    • MemoizedMatrixChain
      • LookupC
    • Dynamic Programming vs Memoization Summary
RTEU CE100 Week-6
CE100 Algorithms and Programming II
  • Dynamic Programming
    • Problem-2 : Longest Common Subsequence
      • Definitions
      • LCS Problem
      • Notations
      • Optimal Substructure of LCS
        • Proof Case-1
        • Proof Case-2
        • Proof Case-3
RTEU CE100 Week-6
CE100 Algorithms and Programming II
  • A recursive solution to subproblems (inefficient)
  • Computing the length of and LCS
    • LCS Data Structure for DP
    • Bottom-Up Computation
  • Constructing and LCS
    • PRINT-LCS
    • Back-pointer space optimization for LCS length
RTEU CE100 Week-6
CE100 Algorithms and Programming II
  • Most Common Dynamic Programming Interview Questions
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Elements of Dynamic Programming

  • When should we look for a DP solution to an optimization problem?
  • Two key ingredients for the problem
    • Optimal substructure
    • Overlapping subproblems
RTEU CE100 Week-6
CE100 Algorithms and Programming II

DP Hallmark #1

  • Optimal Substructure
    • A problem exhibits optimal substructure
      • if an optimal solution to a problem contains within it optimal solutions to subproblems
    • Example: matrix-chain-multiplication
      • Optimal parenthesization of A1A2…AnA_1 A_2 \dots A_n that splits the product between AkA_k and Ak+1A_{k+1}, contains within it optimal soln’s to the problems of parenthesizing A1A2…AkA_1A_2 \dots A_k and Ak+1Ak+2…AnA_{k+1} A_{k+2} \dots A_n
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure

  • Finding a suitable space of subproblems
    • Iterate on subproblem instances
    • Example: matrix-chain-multiplication
      • Iterate and look at the structure of optimal soln’s to subproblems, sub-subproblems, and so forth
      • Discover that all subproblems consists of subchains of ⟨A1,A2,…,An⟩\langle A_1, A_2, \dots , A_n \rangle
      • Thus, the set of chains of the form ⟨Ai,Ai+1,…,Aj⟩\langle A_i,A_{i+1}, \dots , A_j \rangle for 1≤i≤j≤n1 \leq i \leq j \leq n
      • Makes a natural and reasonable space of subproblems
RTEU CE100 Week-6
CE100 Algorithms and Programming II

DP Hallmark #2

  • Overlapping Subproblems
    • Total number of distinct subproblems should be polynomial in the input size
    • When a recursive algorithm revisits the same problem over and over again,
      • We say that the optimization problem has overlapping subproblems
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Overlapping Subproblems

  • DP algorithms typically take advantage of overlapping subproblems
    • by solving each problem once
    • then storing the solutions in a table
      • where it can be looked up when needed
    • using constant time per lookup
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Overlapping Subproblems

  • Recursive matrix-chain order

RMC(p,i,j){if i=j thenreturn 0m[i,j]←∞for k←ito j−1 doq←RMC(p,i,k)+RMC(p,k+1,j)+pi−1pkpjif q<m[i,j] thenm[i,j]←qreturn m[i,j] }\begin{align*} & \text{RMC}(p, i, j) \{ \\[5 pt] & \quad \text{if} \ i = j \ \text{then} \\ & \qquad \text{return} \ 0 \\[5 pt] & \quad m[i, j] \leftarrow \infty \\[5 pt] & \quad \text{for} \ k \leftarrow i \text{to} \ j - 1 \ \text{do} \\ & \qquad q \leftarrow \text{RMC}(p, i, k) + \text{RMC}(p, k+1, j) + p_{i-1} p_k p_j \\[5 pt] & \quad if \ q < m[i, j] \ \text{then} \\ & \qquad m[i, j] \leftarrow q \\[5 pt] & \quad \text{return} \ m[i, j] \ \} \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Direct Recursion: Inefficient!

  • Recursion tree for RMC(p,1,4)RMC(p,1,4)
  • Nodes are labeled with ii and jj values
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Running Time of RMC

T(1)≥1T(1) \geq 1
T(n)≥1+∑k=1n−1(T(k)+T(n−k)+1) for n>1T(n) \geq 1 + \sum \limits_{k=1}^{n-1} (T(k)+T(n-k)+1)\ \text{for} \ n>1

  • For i=1,2,…,ni =1,2, \dots ,n each term T(i)T(i) appears twice
    • Once as T(k)T(k), and once as T(n−k)T(n-k)
  • Collect n−1,n-1, 11’s in the summation together with the front 11

T(n)≥2∑i=1n−1T(i)+n\begin{align*} T(n) \geq 2 \sum \limits_{i=1}^{n-1}T(i)+n \end{align*}

  • Prove that T(n)=Ω(2n)T(n)= \Omega(2n) using the substitution method
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Running Time of RMC: Prove that T(n)=Ω(2n)T(n)= \Omega(2n)

  • Try to show that T(n)≥2n−1T(n) \geq 2^{n-1} (by substitution)
  • Base case: T(1)≥1=20=21−1T(1) \geq 1 = 2^0 = 2^{1-1} for n=1n=1
  • Ind. Hyp.:

T(i)≥2i−1 for all i=1,2,…,n−1 and n≥2T(n)≥2∑i=1n−12i−1+n=2∑i=1n−12i−1+n=2(2n−1−1)+n=2n−1+(2n−1−2+n)⇒T(n)≥2n−1  Q.E.D.\begin{align*} T(i) & \geq 2^{i-1} \ \text{for all} \ i=1, 2, \dots, n-1 \ \text{and} \ n \geq 2 \\ T(n) & \geq 2 \sum \limits_{i=1}^{n-1}2^{i-1} + n \\[15 pt] & = 2 \sum \limits_{i=1}^{n-1} 2^{i-1} + n \\ & = 2(2^{n-1}-1) + n \\ & = 2^{n-1} + (2^{n-1} - 2 + n) \\ & \Rightarrow T(n) \geq 2^{n-1} \ \text{ Q.E.D.} \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Running Time of RMC: T(n)≥2n−1T(n) \geq 2^{n-1}

  • Whenever
    • a recursion tree for the natural recursive solution to a problem contains the same subproblem repeatedly
    • the total number of different subproblems is small
      • it is a good idea to see if DP(Dynamic Programming)DP (Dynamic \ Programming) can be applied
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization

  • Offers the efficiency of the usual DPDP approach while maintaining top-down strategy
  • Idea is to memoize the natural, but inefficient, recursive algorithm
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoized Recursive Algorithm

  • Maintains an entry in a table for the soln to each subproblem
  • Each table entry contains a special value to indicate that the entry has yet to be filled in
  • When the subproblem is first encountered its solution is computed and then stored in the table
  • Each subsequent time that the subproblem encountered the value stored in the table is simply looked up and returned
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoized Recursive Matrix-chain Order

  • Shaded subtrees are looked-up rather than recomputing

MemoizedMatrixChain(p)n←length[p]−1for i←1 to n dofor j←1 to n dom[i,j]←∞return LookupC(p,1,n)⟹⟹LookupC(p,i,j)if m[i,j]=∞ thenif i=j thenm[i,j]←0elsefor k←i to j−1 doq←LookupC(p,i,k)+LookupC(p,k+1,j)+pi−1pkpjif q<m[i,j] thenm[i,j]←qreturn m[i,j]\begin{align*} \begin{aligned} & \text{MemoizedMatrixChain(p)} \\ & \quad n \leftarrow length[p] - 1 \\ & \quad \text{for} \ i \leftarrow 1 \ \text{to} \ n \ \text{do} \\ & \qquad \text{for} \ j \leftarrow 1 \ \text{to} \ n \ \text{do} \\ & \qquad \quad m[i, j] \leftarrow \infty \\ & \quad \text{return} \ \text{LookupC}(p, 1, n) \Longrightarrow \end{aligned} \begin{aligned} & \Longrightarrow \text{LookupC}(p, i, j) \\ & \quad \text{if} \ m[i, j] = \infty \ \text{then} \\ & \qquad \text{if} \ i = j \ \text{then} \\ & \qquad \quad m[i, j] \leftarrow 0 \\ & \qquad \text{else} \\ & \qquad \quad \text{for} \ k \leftarrow i \ \text{to} \ j-1 \ \text{do} \\ & \qquad \quad \quad q \leftarrow \text{LookupC}(p, i, k) + \text{LookupC}(p, k+1, j) + p_{i-1} p_k p_j \\ & \qquad \quad \quad \text{if} \ q < m[i, j] \ \text{then} \\ & \qquad \quad \quad \quad m[i, j] \leftarrow q \\ & \quad \text{return} \ m[i, j] \end{aligned} \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoized Recursive Algorithm

  • The approach assumes that
    • The set of all possible subproblem parameters are known
    • The relation between the table positions and subproblems is established
  • Another approach is to memoize
    • by using hashing with subproblem parameters as key
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Dynamic Programming vs Memoization Summary (1)

  • Matrix-chain multiplication can be solved in O(n3)O(n^3) time
    • by either a top-down memoized recursive algorithm
    • or a bottom-up dynamic programming algorithm
  • Both methods exploit the overlapping subproblems property
    • There are only Θ(n2)\Theta(n^2) different subproblems in total
    • Both methods compute the soln to each problem once
  • Without memoization the natural recursive algorithm runs in exponential time since subproblems are solved repeatedly
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Dynamic Programming vs Memoization Summary (2)

  • In general practice
    • If all subproblems must be solved at once
      • a bottom-up DP algorithm always outperforms a top-down memoized algorithm by a constant factor
    • because, bottom-up DP algorithm
      • Has no overhead for recursion
      • Less overhead for maintaining the table
    • DP: Regular pattern of table accesses can be exploited to reduce the time and/or space requirements even further
    • Memoized: If some problems need not be solved at all, it has the advantage of avoiding solutions to those subproblems
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem 3: Longest Common Subsequence

Definitions

  • A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out

  • Example:

    • X=⟨A,B,C,B,D,A,B⟩X = \langle A, B, C, B, D, A, B \rangle
    • Z=⟨B,C,D,B⟩Z = \langle B, C, D, B \rangle
      • ZZ is a subsequence of XX
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem 3: Longest Common Subsequence

Definitions

  • Formal definition: Given a sequence X=⟨x1,x2,…,xm⟩X = \langle x_1, x_2, \dots , x_m \rangle, sequence Z=⟨z1,z2,…,zk⟩Z = \langle z_1, z_2, \dots, z_k \rangle is a subsequence of XX

    • if ∃\exists a strictly increasing sequence ⟨i1,i2,…,ik⟩\langle i_1, i_2,\dots, i_k \rangle of indices of XX such that xij=zjx_{i_j} = z_j for all j=1,2,…,kj = 1, 2, …, k, where 1≤k≤m1 \leq k \leq m

  • Example: Z=⟨B,C,D,B⟩Z = \langle B,C,D,B \rangle is a subsequence of X=⟨A,B,C,B,D,A,B⟩X = \langle A,B,C,B,D,A,B \rangle with the index sequence ⟨i1,i2,i3,i4⟩=⟨2,3,5,7⟩\langle i_1, i_2, i_3, i_4 \rangle = \langle 2, 3, 5, 7 \rangle

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem 3: Longest Common Subsequence

Definitions

  • If ZZ is a subsequence of both XX and YY, we denote ZZ as a common subsequence of XX and YY.

  • Example:

X=⟨A,B∗,C∗,B,D,A∗,B⟩Y=⟨B∗,D,C∗,A∗,B,A⟩\begin{align*} X &= \langle A,B^*,C^*,B,D,A^*,B \rangle \\ Y &= \langle B^*,D,C^*,A^*,B,A \rangle \end{align*}

  • Z1=⟨B∗,C∗,A∗⟩Z_1 = \langle B^*, C^*, A^* \rangle is a common subsequence (of length 3) of XX and YY.
  • Two longest common subsequence (LCSs) of XX and YY?
    • Z2=⟨B,C,B,A⟩Z2 = \langle B, C, B, A \rangle of length 44
    • Z3=⟨B,D,A,B⟩Z3 = \langle B, D, A, B \rangle of length 44
      • The optimal solution value = 4
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Longest Common Subsequence (LCS) Problem

  • LCS problem: Given two sequences
    • X=⟨x1,x2,…,xm⟩X = \langle x_1, x_2, \dots, x_m \rangle and
    • Y=⟨y1,y2,…,yn⟩Y = \langle y_1, y_2, \dots , y_n \rangle, find the LCS of X&YX \& Y
  • Brute force approach:
    • Enumerate all subsequences of XX
    • Check if each subsequence is also a subsequence of YY
    • Keep track of the LCS
    • What is the complexity?
    • There are 2m2^m subsequences of XX
      • Exponential runtime
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Notation

  • Notation: Let XiX_i denote the ithi^{th} prefix of XX
    • i.e. Xi=⟨x1,x2,…,xi⟩X_i = \langle x_1, x_2, \dots, x_i \rangle
  • Example:

X=⟨A,B,C,B,D,A,B⟩X4=⟨A,B,C,B⟩X0=⟨⟩\begin{align*} X &= \langle A, B, C, B, D, A, B \rangle \\[10 pt] X_4 &= \langle A, B, C, B \rangle \\ X_0 &= \langle \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure of an LCS

  • Let X=<x1,x2,…,xm>X = <x1, x2, …, xm> and Y=⟨y1,y2,…,yn⟩Y = \langle y_1, y_2, \dots, y_n \rangle are given
  • Let Z=⟨z1,z2,…,zk⟩Z = \langle z_1, z_2, \dots, z_k \rangle be an LCS of XX and YY

center

  • Question 1: If xm=ynx_m = y_n, how to define the optimal substructure?
    • We must have zk=xm=ynz_k = x_m = y_n and
    • Zk−1=LCS(Xm−1,Yn−1)Z_{k-1} = \text{LCS}(X_{m-1}, Y_{n-1})
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure of an LCS

  • Let X=<x1,x2,…,xm>X = <x1, x2, …, xm> and Y=⟨y1,y2,…,yn⟩Y = \langle y_1, y_2, \dots, y_n \rangle are given
  • Let Z=⟨z1,z2,…,zk⟩Z = \langle z_1, z_2, \dots, z_k \rangle be an LCS of XX and YY

center

  • Question 2: If xm≠yn and zk≠xmx_m \neq y_n \ \text{and} \ z_k \neq x_m, how to define the optimal substructure?
    • We must have Z=LCS(Xm−1,Y)Z = \text{LCS}(X_{m-1}, Y)
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure of an LCS

  • Let X=<x1,x2,…,xm>X = <x1, x2, …, xm> and Y=⟨y1,y2,…,yn⟩Y = \langle y_1, y_2, \dots, y_n \rangle are given
  • Let Z=⟨z1,z2,…,zk⟩Z = \langle z_1, z_2, \dots, z_k \rangle be an LCS of XX and YY

center

  • Question 3: If xm≠yn and zk≠ynx_m \neq y_n \ \text{and} \ z_k \neq y_n, how to define the optimal substructure?
    • We must have Z=LCS(X,Yn−1)Z = \text{LCS}(X, Y_{n-1})
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Theorem: Optimal Substructure of an LCS

  • Let X=⟨x1,x2,…,xm⟩X = \langle x_1, x_2, \dots, x_m \rangle and Y = <y1, y2, …, yn> are given
  • Let Z=⟨z1,z2,…,zk⟩Z = \langle z_1, z_2, \dots, z_k \rangle be an LCS of XX and YY
  • Theorem: Optimal substructure of an LCS:
    • If xm=ynx_m = y_n
      • then zk=xm=ynz_k = x_m = y_n and Zk−1Z_{k-1} is an LCS of Xm−1X_{m-1} and Yn−1Y_{n-1}
    • If xm≠ynx_m \neq y_n and zk≠xmz_k \neq x_m
      • then ZZ is an LCS of Xm−1X_{m-1} and YY
    • If xm≠ynx_m \neq y_n and zk≠ynz_k \neq y_n
      • then ZZ is an LCS of XX and Yn−1Y_{n-1}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure Theorem (case 1)

  • If xm=ynx_m = y_n then zk=xm=ynz_k = x_m = y_n and Zk−1Z_{k-1} is an LCS of Xm−1X_{m-1} and Yn−1Y_{n-1}

center

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure Theorem (case 2)

  • If xm≠ynx_m \neq y_n and zk≠xmz_k \neq x_m then ZZ is an LCS of Xm−1X_{m-1} and YY

center

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure Theorem (case 3)

  • If xm≠ynx_m \neq y_n and zk≠ynz_k \neq y_n then ZZ is an LCS of XX and Yn−1Y_{n-1}

center

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Proof of Optimal Substructure Theorem (case 1)

  • If xm=ynx_m = y_n then zk=xm=ynz_k = x_m = y_n and Zk−1Z_{k-1} is an LCS of Xm−1X_{m-1} and Yn−1Y_{n-1}
  • Proof: If zk≠xm=ynz_k \neq x_m = y_n then
    • we can append xm=ynx_m = y_n to ZZ to obtain a common subsequence of length k+1⟹k+1 \Longrightarrow contradiction
    • Thus, we must have zk=xm=ynz_k = x_m = y_n
    • Hence, the prefix Zk−1Z_{k-1} is a length-(k−1k-1) CS of Xm−1X_{m-1} and Yn−1Y_{n-1}
  • We have to show that Zk−1Z_{k-1} is in fact an LCS of Xm−1X_{m-1} and Yn−1Y_{n-1}
  • Proof by contradiction:
    • Assume that ∃\exists a CS WW of Xm−1X_{m-1} and Yn−1Y_{n-1} with ∣W∣=k|W| = k
    • Then appending xm=ynx_m = y_n to WW produces a CS of length k+1k+1
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Proof of Optimal Substructure Theorem (case 2)

  • If xm≠ynx_m \neq y_n and zk≠xmz_k \neq x_m then ZZ is an LCS of Xm−1X_{m-1} and YY
  • Proof : If zk≠xmz_k \neq x_m then ZZ is a CS of Xm−1X_{m-1} and YnY_n
    • We have to show that ZZ is in fact an LCS of Xm−1X_{m-1} and YnY_n
  • (Proof by contradiction)
    • Assume that ∃\exists a CS WW of Xm−1X_{m-1} and YnY_n with ∣W∣>k|W| > k
    • Then WW would also be a CS of XX and YY
    • Contradiction to the assumption that
      • ZZ is an LCS of XX and YY with ∣Z∣=k|Z| = k
  • Case 3: Dual of the proof for (case 2)
RTEU CE100 Week-6
CE100 Algorithms and Programming II

A Recursive Solution to Subproblems

  • Theorem implies that there are one or two subproblems to examine
  • if xm=ynx_m = y_n then
    • we must solve the subproblem of finding an LCS of Xm−1&Yn−1X_{m-1} \& Y_{n-1}
    • appending xm=ynx_m = y_n to this LCS yields an LCS of X&YX \& Y
  • else
    • we must solve two subproblems
      • finding an LCS of Xm−1&YX_{m-1} \& Y
      • finding an LCS of X&Yn−1X \& Y_{n-1}
    • longer of these two LCS s is an LCS of X&YX \& Y
  • endif
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Recursive Algorithm (Inefficient)

LCS(X,Y) {m←length[X]n←length[Y]if xm=yn thenZ←LCS(Xm−1,Yn−1)▹solve one subproblemreturn ⟨Z,xm=yn⟩▹append xm=yn to ZelseZ′←LCS(Xm−1,Y)▹solve two subproblemsZ′′←LCS(X,Yn−1)return longer of Z′ and Z′′}\begin{align*} & \text{LCS}(X, Y) \ \{ \\ & \quad m \leftarrow length[X] \\ & \quad n \leftarrow length[Y] \\ & \quad \text{if} \ x_m = y_n \ \text{then} \\ & \qquad Z \leftarrow \text{LCS}(X_{m-1}, Y_{n-1}) \triangleright \text{solve one subproblem} \\ & \qquad \text{return} \ \langle Z, x_m = y_n \rangle \triangleright \text{append} \ x_m = y_n \ \text{to} \ Z \\ & \quad else \\ & \qquad Z^{'} \leftarrow \text{LCS}(X_{m-1}, Y) \triangleright \text{solve two subproblems} \\ & \qquad Z^{''} \leftarrow \text{LCS}(X, Y_{n-1}) \\ & \qquad \text{return longer of} \ Z^{'} \ \text{and} \ Z^{''} \\ & \} \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

A Recursive Solution

  • c[i,j]:c[i, j]: length of an LCS of XiX_i and YjY_j

c[i,j]={0if i=0 or j=0c[i−1,j−1]+1if i,j>0 and xi=yjmax{c[i,j−1],c[i−1,j]}if i,j>0 and xi≠yj\begin{align*} c[i,j] = \begin{cases} & 0 & \text{if}& \ i=0 \ \text{or} \ j=0 \\ & c[i-1,j-1]+1 & \text{if}& \ i,j>0 \ \text{and} \ x_i=y_j \\ & \text{max}\{c[i,j-1],c[i-1,j]\} & \text{if}& \ i,j>0 \ \text{and} \ x_i \neq y_j \\ \end{cases} \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS

  • We can easily write an exponential-time recursive algorithm based on the given recurrence. ⟹\Longrightarrow Inefficient!
  • How many distinct subproblems to solve?
    • Θ(mn)\Theta(mn)
  • Overlapping subproblems property: Many subproblems share the same sub-subproblems.
    • e.g. Finding an LCS to Xm−1&YX_{m-1} \& Y and an LCS to X&Yn−1X \& Y_{n-1}
    • has the sub-subproblem of finding an LCS to Xm−1&Yn−1X_{m-1} \& Y_{n-1}
  • Therefore, we can use dynamic programming.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Data Structures

  • Let:
    • c[i,j]:c[i, j]: length of an LCS of XiX_i and YjY_j
    • b[i,j]:b[i, j]: direction towards the table entry corresponding to the optimal subproblem solution chosen when computing c[i,j]c[i, j].
    • Used to simplify the construction of an optimal solution at the end.
  • Maintain the following tables:
    • c[0…m,0…n]c[0 \dots m, 0 \dots n]
    • b[1…m,1…n]b[1 \dots m, 1 \dots n]
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Bottom-up Computation

  • Reminder:

c[i,j]={0if i=0 or j=0c[i−1,j−1]+1if i,j>0 and xi=yjmax{c[i,j−1],c[i−1,j]}if i,j>0 and xi≠yj\begin{align*} c[i,j] = \begin{cases} & 0 & \text{if}& \ i=0 \ \text{or} \ j=0 \\ & c[i-1,j-1]+1 & \text{if}& \ i,j>0 \ \text{and} \ x_i=y_j \\ & \text{max}\{c[i,j-1],c[i-1,j]\} & \text{if}& \ i,j>0 \ \text{and} \ x_i \neq y_j \\ \end{cases} \end{align*}

  • How to choose the order in which we process c[i,j]c[i, j] values?
  • The values for c[i−1,j−1]c[i-1, j-1], c[i,j−1]c[i, j-1], and c[i−1,j]c[i-1,j] must be computed before computing c[i,j]c[i, j].
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Bottom-up Computation

c[i,j]={0if i=0 or j=0c[i−1,j−1]+1if i,j>0 and xi=yjmax{c[i,j−1],c[i−1,j]}if i,j>0 and xi≠yj\begin{align*} c[i,j] = \begin{cases} & 0 & \text{if}& \ i=0 \ \text{or} \ j=0 \\ & c[i-1,j-1]+1 & \text{if}& \ i,j>0 \ \text{and} \ x_i=y_j \\ & \text{max}\{c[i,j-1],c[i-1,j]\} & \text{if}& \ i,j>0 \ \text{and} \ x_i \neq y_j \\ \end{cases} \end{align*}

Need to process:
c[i,j]c[i, j]
after computing:
c[i−1,j−1]c[i-1, j-1],
c[i,j−1]c[i, j-1],
c[i−1,j]c[i-1,j]

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Bottom-up Computation

c[i,j]={0if i=0 or j=0c[i−1,j−1]+1if i,j>0 and xi=yjmax{c[i,j−1],c[i−1,j]}if i,j>0 and xi≠yj\begin{align*} c[i,j] = \begin{cases} & 0 & \text{if}& \ i=0 \ \text{or} \ j=0 \\ & c[i-1,j-1]+1 & \text{if}& \ i,j>0 \ \text{and} \ x_i=y_j \\ & \text{max}\{c[i,j-1],c[i-1,j]\} & \text{if}& \ i,j>0 \ \text{and} \ x_i \neq y_j \\ \end{cases} \end{align*}

⇓\Downarrow

for i←1 to mfor j←1 to n……c[i,j]=⋯\begin{align*} & \text{for} \ i \leftarrow 1 \ \text{to} \ m \\ & \quad \text{for} \ j \leftarrow 1 \ \text{to} \ n \\ & \qquad \dots \\ & \qquad \dots \\ & \qquad c[i, j] = \cdots \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS

Total Runtime=Θ(mn)Total Space=Θ(mn){LCS−LENGTH(X,Y)m←length[X];n←length[Y]for i←0 to m do c[i,0]←0for j←0 to n do c[0,j]←0for i←1 to m dofor j←1 to n doif xi=yj thenc[i,j]←c[i−1,j−1]+1b[i,j]←"↖"else if c[i−1,j]≥c[i,j−1]c[i,j]←c[i−1,j]b[i,j]←"↑"elsec[i,j]←c[i,j−1]b[i,j]←"←"\begin{align*} \frac{\text{Total Runtime} = \Theta(mn)}{\text{Total Space} = \Theta(mn)} \begin{cases} & LCS-LENGTH(X,Y) \\ & \quad m \leftarrow length[X]; n \leftarrow length[Y] \\ & \quad \text{for} \ i \leftarrow 0 \ \text{to} \ m \ \text{do} \ c[i, 0] \leftarrow 0 \\ & \quad \text{for} \ j \leftarrow 0 \ \text{to} \ n \ \text{do} \ c[0, j] \leftarrow 0 \\ & \quad \text{for} \ i \leftarrow 1 \ \text{to} \ m \ \text{do} \\ & \qquad \text{for} \ j \leftarrow 1 \ \text{to} \ n \ \text{do} \\ & \qquad \quad \text{if} \ x_i = y_j \ \text{then} \\ & \qquad \quad \quad c[i, j] \leftarrow c[i-1, j-1]+1 \\ & \qquad \quad \quad b[i, j] \leftarrow " \nwarrow " \\ & \qquad \quad \text{else if} \ c[i - 1, j] \geq c[i, j-1] \\ & \qquad \quad \quad c[i, j] \leftarrow c[i-1, j] \\ & \qquad \quad \quad b[i, j] \leftarrow "\uparrow " \\ & \qquad \quad \text{else} \\ & \qquad \quad \quad c[i, j] \leftarrow c[i, j-1] \\ & \qquad \quad \quad b[i, j] \leftarrow " \leftarrow " \\ \end{cases} \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-1

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-2

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-3

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-4

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-5

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-6

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-7

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-8

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-9

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-10

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-11

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-12

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-13

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

  • Running-time = O(mn)O(mn) since each table entry takes O(1)O(1) time to compute
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Length of an LCS-14

Operation of LCS-LENGTH on the sequences

X=⟨A1,B2,C3,B4,D5,A6,B7⟩Y=⟨B1,D2,C3,A4,B5,A6⟩\begin{align*} X &= \langle \overset{1}{A}, \overset{2}{B}, \overset{3}{C}, \overset{4}{B}, \overset{5}{D}, \overset{6}{A}, \overset{7}{B} \rangle \\ Y &= \langle \overset{1}{B}, \overset{2}{D}, \overset{3}{C}, \overset{4}{A}, \overset{5}{B}, \overset{6}{A} \rangle \end{align*}

  • Running-time = O(mn)O(mn) since each table entry takes O(1)O(1) time to compute

  • LCS of X&Y=⟨B,C,B,A⟩X \& Y = \langle B, C, B, A \rangle

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Constructing an LCS

  • The bb table returned by LCS-LENGTH can be used to quickly construct an LCS of X&YX \& Y
  • Begin at b[m,n]b[m, n] and trace through the table following arrows
  • Whenever you encounter a "↖\nwarrow" in entry b[i,j]b[i, j] it implies that xi=yjx_i = y_j is an element of LCS
  • The elements of LCS are encountered in reverse order
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Constructing an LCS

  • The recursive procedure PRINT-LCS\text{PRINT-LCS} prints out LCS\text{LCS} in proper order
  • This procedure takes O(m+n)O(m+n) time since at least one of ii and jj is decremented in each stage of the recursion

PRINT-LCS(b,X,i,j)if i=0 orj=0 thenreturnif b[i,j]="↖" thenPRINT-LCS(b,X,i−1,j−1)print xielse if b[i,j]="↑" thenPRINT-LCS(b,X,i−1,j)elsePRINT-LCS(b,X,i,j−1)\begin{align*} & \text{PRINT-LCS}(b, X, i, j) \\ & \quad \text{if} \ i = 0 \ \text{or} j = 0 \ \text{then} \\ & \quad \text{return} \\ & \quad \text{if} \ b[i, j] = " \nwarrow " \ \text{then} \\ & \qquad \text{PRINT-LCS}(b, X, i-1, j-1) \\ & \qquad \text{print} \ x_i \\ & \quad \text{else if} \ b[i, j] = " \uparrow " \ \text{then} \\ & \qquad \text{PRINT-LCS}(b, X, i-1, j) \\ & \quad \text{else} \\ & \qquad \text{PRINT-LCS}(b, X, i, j-1) \end{align*}

  • The initial invocation: PRINT-LCS(b,X,length[X],length[Y])\text{PRINT-LCS}(b, X, length[X], length[Y])
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Do we really need the b table (back-pointers)?

  • Question: From which neighbor did we expand to the highlighted cell?
  • Answer: Upper-left neighbor,because X[i]=Y[j]X[i] = Y[j].
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Do we really need the b table (back-pointers)?

  • Question: From which neighbor did we expand to the highlighted cell?
  • Answer: Left neighbor, because X[i]≠Y[j]X[i] \neq Y[j] and LCS[i,j−1]>LCS[i−1,j]LCS[i, j-1] > LCS[i-1, j].
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Do we really need the b table (back-pointers)?

  • Question: From which neighbor did we expand to the highlighted cell?
  • Answer: Upper neighbor,because X[i]≠Y[j]X[i] \neq Y[j] and
    LCS[i,j−1]=LCS[i−1,j]LCS[i, j-1] = LCS[i-1, j].
    (See pseudo-code to see how ties are handled.)
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Improving the Space Requirements

  • We can eliminate the b table altogether
    • each c[i,j]c[i, j] entry depends only on 33 other cc table entries: c[i−1,j−1]c[i-1, j-1], c[i−1,j]c[i-1, j] and c[i,j−1]c[i, j-1]
  • Given the value of c[i,j]c[i, j]:
    • We can determine in O(1)O(1) time which of these 33 values was used to compute c[i,j]c[i, j] without inspecting table bb
    • We save Θ(mn)\Theta(mn) space by this method
    • However, space requirement is still Θ(mn)\Theta(mn) since we need Θ(mn)\Theta(mn) space for the cc table anyway
RTEU CE100 Week-6
CE100 Algorithms and Programming II

What if we store the last 2 rows only?

  • To compute c[i,j]c[i, j], we only need c[i−1,j−1]c[i-1, j-1], c[i−1,j]c[i-1, j],and c[i−1,j−1]c[i-1, j-1]
  • So, we can store only the last two rows.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

What if we store the last 2 rows only?

  • To compute c[i,j]c[i, j], we only need c[i−1,j−1]c[i-1, j-1], c[i−1,j]c[i-1, j], and c[i−1,j−1]c[i-1, j-1]
  • So, we can store only the last two rows.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

What if we store the last 2 rows only?

  • To compute c[i,j]c[i, j], we only need c[i−1,j−1]c[i-1, j-1], c[i−1,j]c[i-1, j], and c[i−1,j−1]c[i-1, j-1]

  • So, we can store only the last two rows.

  • This reduces space complexity from Θ(mn)\Theta(mn) to Θ(n)\Theta(n).

  • Is there a problem with this approach?

RTEU CE100 Week-6
CE100 Algorithms and Programming II

What if we store the last 2 rows only?

  • Is there a problem with this approach?

    • We cannot construct the optimal solution because we cannot backtrace anymore.
    • This approach works if we only need the length of an LCS, not the actual LCS.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem 4 Optimal Binary Search Tree

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Reminder: Binary Search Tree (BST)

center

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Binary Search Tree Example

  • Example: English-to-French translation
    • Organize (English, French) word pairs in a BST
      • Keyword: English word
      • Satellite Data: French word
  • We can search for an English word (node key) efficiently, and return the corresponding French word (satellite data).
RTEU CE100 Week-6
CE100 Algorithms and Programming II

ASCII Table

center

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Binary Search Tree Example

Suppose we know the frequency of each keyword in texts:

begin‾5%,do‾40%,else‾8%,end‾4%,if‾10%,then‾10%,while‾23%,\underset{5\%}{\underline{begin}}, \underset{40\%}{\underline{do}}, \underset{8\%}{\underline{else}}, \underset{4\%}{\underline{end}}, \underset{10\%}{\underline{if}}, \underset{10\%}{\underline{then}}, \underset{23\%}{\underline{while}},

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Cost of a Binary Search Tree

Example: If we search for keyword "while", we need
to access 33 nodes. So, 2323% of the queries will have cost of 33.

Total Cost=∑i(depth(i)+1)freq(i)=1×0.04+2×0.4+2×0.1+3×0.05+3×0.08+3×0.1+3×0.23=2.42\begin{align*} \text{Total Cost} &= \sum \limits_{i}^{}(\text{depth}(i)+1)\text{freq}(i) \\ &= 1 \times 0.04 + 2 \times 0.4 + \\ & 2 \times 0.1 + 3 \times 0.05 + \\ & 3 \times 0.08 + 3 \times 0.1 + \\ & 3 \times 0.23 \\ &= 2.42 \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Cost of a Binary Search Tree

Example: If we search for keyword "while", we need
to access 33 nodes. So, 2323% of the queries will have cost of 33.

Total Cost=∑i(depth(i)+1)freq(i)=1×0.4+2×0.05+2×0.23+3×0.1+4×0.08+4×0.1+5×0.04=2.18\begin{align*} \text{Total Cost} &= \sum \limits_{i}^{}(\text{depth}(i)+1)\text{freq}(i) \\ &= 1 \times 0.4 + 2 \times 0.05 + 2 \times 0.23 + \\ & 3 \times 0.1 + 4 \times 0.08 + \\ & 4 \times 0.1 + 5 \times 0.04 \\ &= 2.18 \end{align*}

  • This is in fact an optimal BST.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Binary Search Tree Problem

  • Given:
    • A collection of nn keys K1<K2<…KnK_1 < K_2 < \dots K_n to be stored in a BST.
    • The corresponding pip_i values for 1≤i≤n1 \leq i \leq n
      • pip_i: probability of searching for key KiK_i
  • Find:
    • An optimal BST with minimum total cost:

Total Cost=∑i(depth(i)+1)freq(i)\begin{align*} \text{Total Cost} &= \sum \limits_{i}^{}(\text{depth}(i)+1)\text{freq}(i) \end{align*}

  • Note: The BST will be static. Only search operations will be performed. No insert, no delete, etc.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Cost of a Binary Search Tree

  • Lemma 1: Let TijTij be a BST containing keys Ki<Ki+1<⋯<KjK_i < K_{i+1} < \dots < K_j. Let TLT_L and TRT_R be the left and right subtrees of TT. Then we have:

cost(Tij)=cost(TL)+cost(TR)+∑h=ijph\begin{align*} \text{cost}(T_{ij})=\text{cost}(T_{L})+\text{cost}(T_{R})+\sum \limits_{h=i}^{j}p_h \end{align*}

Intuition: When we add the root node, the depth of each node in TLT_L and TRT_R increases by 11. So, the cost of node hh increases by php_h. In addition, the cost of root node rr is prp_r. That’s why, we have the last term at the end of the formula above.

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure Property

  • Lemma 2: Optimal substructure property
    • Consider an optimal BST TijT_{ij} for keys Ki<Ki+1<⋯<KjK_i < K_{i+1} < \dots < K_j
    • Let KmK_m be the key at the root of TijT_{ij}
  • Then:
    • Ti,m−1T_{i,m-1} is an optimal BST for subproblem containing keys:
      • Ki<⋯<Km−1K_i < \dots < K_{m-1}
    • Tm+1,jT_{m+1,j} is an optimal BST for subproblem containing keys:
      • Km+1<⋯<KjK_{m+1} < \dots < K_j

cost(Tij)=cost(Ti,m−1)+cost(Tm+1,j)+∑h=ijph\begin{align*} \text{cost}(T_{ij})=\text{cost}(T_{i,m-1})+\text{cost}(T_{m+1,j})+\sum \limits_{h=i}^{j}p_h \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Recursive Formulation

  • Note: We don’t know which root vertex leads to the minimum total cost. So, we need to try each vertex mm, and choose the one with minimum total cost.

  • c[i,j]c[i, j]: cost of an optimal BST TijT_{ij} for the subproblem Ki<⋯<KjK_i < \dots < K_j

c[i,j]={0if i>jmini≤r≤j{c[i,r−1]+c[r+1,j]+Pij}otherwisewhere Pij=∑h=ijph\begin{align*} & c[i,j] = \begin{cases} & 0 & \text{if} \ i>j \\ & \underset{i \leq r \leq j}{\text{min}}\{ c[i,r-1]+c[r+1,j]+P_{ij} \} & \text{otherwise} \\ \end{cases} \\ & \text{where} \ P_{ij}= \sum \limits_{h=i}^{j}p_h \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Bottom-up computation

c[i,j]={0if i>jmini≤r≤j{c[i,r−1]+c[r+1,j]+Pij}otherwise\begin{align*} & c[i,j] = \begin{cases} & 0 & \text{if} \ i>j \\ & \underset{i \leq r \leq j}{\text{min}}\{ c[i,r-1]+c[r+1,j]+P_{ij} \} & \text{otherwise} \\ \end{cases} \end{align*}

  • How to choose the order in which we process c[i,j]c[i, j] values?
  • Before computing c[i,j]c[i, j], we have to make sure that the values for c[i,r−1]c[i, r-1] and c[r+1,j]c[r+1,j] have been computed for all rr.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Bottom-up computation

c[i,j]={0if i>jmini≤r≤j{c[i,r−1]+c[r+1,j]+Pij}otherwise\begin{align*} & c[i,j] = \begin{cases} & 0 & \text{if} \ i>j \\ & \underset{i \leq r \leq j}{\text{min}}\{ c[i,r-1]+c[r+1,j]+P_{ij} \} & \text{otherwise} \\ \end{cases} \end{align*}

  • c[i,j]c[i,j] must be processed after c[i,r−1]c[i,r-1] and c[r+1,j]c[r+1,j]
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Bottom-up computation

c[i,j]={0if i>jmini≤r≤j{c[i,r−1]+c[r+1,j]+Pij}otherwise\begin{align*} & c[i,j] = \begin{cases} & 0 & \text{if} \ i>j \\ & \underset{i \leq r \leq j}{\text{min}}\{ c[i,r-1]+c[r+1,j]+P_{ij} \} & \text{otherwise} \\ \end{cases} \end{align*}

  • If the entries c[i,j]c[i,j] are computed in the shown order, then c[i,r−1]c[i,r-1] and c[r+1,j]c[r+1,j] values are guaranteed to be computed before c[i,j]c[i,j].
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Computing the Optimal BST Cost

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*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Note on Prefix Sum

  • We need PijP_{ij} values for each i,j(1≤i≤n and 1≤j≤n)i, j (1 ≤ i ≤ n \ \text{and} \ 1 ≤ j ≤ n), where:

Pij=∑h=ijph\begin{align*} P_{ij} = \sum \limits_{h=i}^{j}p_h \end{align*}

  • If we compute the summation directly for every (i,j)(i, j) pair, the runtime would be Θ(n3)\Theta(n^3).

  • Instead, we spend O(n)O(n) time in preprocessing to compute the prefix sum array PS. Then we can compute each PijP_{ij} in O(1)O(1) time using PS.

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Note on Prefix Sum

  • In preprocessing, compute for each ii:
    • PS[i]PS[i]: the sum of p[j]p[j] values for 1≤j≤i1 \leq j \leq i
  • Then, we can compute PijP_{ij} in O(1)O(1) time as follows:
    • Pij=PS[i]–PS[j−1]P_{ij} = PS[i] – PS[j-1]
  • Example:

p:0.051 0.022 0.063 0.074 0.205 0.056 0.087 0.028PS:0.051 0.072 0.133 0.204 0.405 0.456 0.537 0.558P27=PS[7]–PS[1]=0.53–0.05=0.48P36=PS[6]–PS[2]=0.45–0.07=0.38\begin{align*} p &: \overset{1}{0.05} \ \overset{2}{0.02} \ \overset{3}{0.06} \ \overset{4}{0.07} \ \overset{5}{0.20} \ \overset{6}{0.05} \ \overset{7}{0.08} \ \overset{8}{0.02} \\ PS &: \overset{1}{0.05} \ \overset{2}{0.07} \ \overset{3}{0.13} \ \overset{4}{0.20} \ \overset{5}{0.40} \ \overset{6}{0.45} \ \overset{7}{0.53} \ \overset{8}{0.55} \\[10 pt] P_{27} &= PS[7] – PS[1] = 0.53 – 0.05 = 0.48 \\ P_{36} &= PS[6] – PS[2] = 0.45 – 0.07 = 0.38 \end{align*}

RTEU CE100 Week-6
CE100 Algorithms and Programming II

REVIEW

Overlapping Subproblems Property in Dynamic Programming

Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Overlapping Subproblems Property in Dynamic Programming

Following are the two main properties of a problem that suggests that the given problem can be solved using Dynamic programming.

  1. Overlapping Subproblems
  2. Optimal Substructure
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Overlapping Subproblems

  • Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems.
  • Dynamic Programming is mainly used when solutions of the same subproblems are needed again and again.
  • In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed.
  • So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Overlapping Subproblems

  • For example, Binary Search doesn’t have common subproblems.
  • If we take an example of following recursive program for Fibonacci Numbers, there are many subproblems that are solved again and again.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Simple Recursion

  • f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)
  • C sample code:
#include <stdio.h>
// a simple recursive program to compute fibonacci numbers
int fib(int n)
{
    if (n <= 1)
        return n;
    else
        return fib(n-1) + fib(n-2);
}

int main()
{
    int n = 5;
    printf("Fibonacci number is %d ", fib(n));
    return 0;
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Simple Recursion

  • Output

    Fibonacci number is 5
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Simple Recursion

  • f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)
/* a simple recursive program for Fibonacci numbers */
public class Fibonacci {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.println(fib(n));
    }

    public static int fib(int n) {
        if (n <= 1)
            return n;

        return fib(n - 1) + fib(n - 2);
    }
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Simple Recursion

  • f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)
public class Fibonacci {
    public static void Main(string[] args) {
        int n = int.Parse(args[0]);
        Console.WriteLine(fib(n));
    }

    public static int fib(int n) {
        if (n <= 1)
            return n;

        return fib(n - 1) + fib(n - 2);
    }
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Recursion tree for execution of fib(5)

                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)
  • We can see that the function fib(3) is being called 2 times.
  • If we would have stored the value of fib(3), then instead of computing it again, we could have reused the old stored value.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Recursion tree for execution of fib(5)

There are following two different ways to store the values so that these values can be reused:

  1. Memoization (Top Down)
  2. Tabulation (Bottom Up)
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • The memoized program for a problem is similar to the recursive version with a small modification that looks into a lookup table before computing solutions.
  • We initialize a lookup array with all initial values as NIL. Whenever we need the solution to a subproblem, we first look into the lookup table.
  • If the precomputed value is there then we return that value, otherwise, we calculate the value and put the result in the lookup table so that it can be reused later.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • Following is the memoized version for the nth Fibonacci Number.
  • C++ Version:
/* C++ program for Memoized version
for nth Fibonacci number */
#include <bits/stdc++.h>
using namespace std;
#define NIL -1
#define MAX 100

int lookup[MAX];
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • C++ Version:
/* Function to initialize NIL
values in lookup table */
void _initialize()
{
    int i;
    for (i = 0; i < MAX; i++)
        lookup[i] = NIL;
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • C++ Version:
/* function for nth Fibonacci number */
int fib(int n)
{
    if (lookup[n] == NIL) {
        if (n <= 1)
            lookup[n] = n;
        else
            lookup[n] = fib(n - 1) + fib(n - 2);
    }

    return lookup[n];
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • C++ Version:
// Driver code
int main()
{
    int n = 40;
    _initialize();
    cout << "Fibonacci number is " << fib(n);
    return 0;
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • Java Version:
/* Java program for Memoized version */
public class Fibonacci {
    final int MAX = 100;
    final int NIL = -1;

    int lookup[] = new int[MAX];

    /* Function to initialize NIL values in lookup table */
    void _initialize()
    {
        for (int i = 0; i < MAX; i++)
            lookup[i] = NIL;
    }
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • Java Version:
    /* function for nth Fibonacci number */
    int fib(int n)
    {
        if (lookup[n] == NIL) {
            if (n <= 1)
                lookup[n] = n;
            else
                lookup[n] = fib(n - 1) + fib(n - 2);
        }
        return lookup[n];
    }
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • Java Version:
    public static void main(String[] args)
    {
        Fibonacci f = new Fibonacci();
        int n = 40;
        f._initialize();
        System.out.println("Fibonacci number is"
                        + " " + f.fib(n));
    }
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • C# Version:
// C# program for Memoized versionof nth Fibonacci number
using System;

class FiboCalcMemoized {

    static int MAX = 100;
    static int NIL = -1;
    static int[] lookup = new int[MAX];

    /* Function to initialize NIL
    values in lookup table */
    static void initialize()
    {
        for (int i = 0; i < MAX; i++)
            lookup[i] = NIL;
    }
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • C# Version:
    /* function for nth Fibonacci number */
    static int fib(int n)
    {
        if (lookup[n] == NIL) {
            if (n <= 1)
                lookup[n] = n;
            else
                lookup[n] = fib(n - 1) + fib(n - 2);
        }
        return lookup[n];
    }
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Memoization (Top Down)

  • C# Version:
    // Driver code
    public static void Main()
    {

        int n = 40;
        initialize();
        Console.Write("Fibonacci number is"
                    + " " + fib(n));
    }
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Tabulation (Bottom Up)

  • The tabulated program for a given problem builds a table in bottom-up fashion and returns the last entry from the table.
  • For example, for the same Fibonacci number,
    • we first calculate fib(0) then fib(1) then fib(2) then fib(3), and so on. So literally, we are building the solutions of subproblems bottom-up.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Tabulation (Bottom Up)

  • C++ Version:
/* C program for Tabulated version */
#include <stdio.h>
int fib(int n)
{
    int f[n + 1];
    int i;
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];

    return f[n];
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Tabulation (Bottom Up)

  • C++ Version:
...
int main()
{
    int n = 9;
    printf("Fibonacci number is %d ", fib(n));
    return 0;
}

Output:

Fibonacci number is 34
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Tabulation (Bottom Up)

  • Java Version:
/* Java program for Tabulated version */
public class Fibonacci {
  public static void main(String[] args)
  {
    int n = 9;
    System.out.println("Fibonacci number is " + fib(n));
  }
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Tabulation (Bottom Up)

  • Java Version:
  /* Function to calculate nth Fibonacci number */
  static int fib(int n)
  {
    int f[] = new int[n + 1];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; i++)
      f[i] = f[i - 1] + f[i - 2];

    return f[n];
  }
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Tabulation (Bottom Up)

  • C# Version:
// C# program for Tabulated version
using System;

class Fibonacci {
    static int fib(int n)
    {
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }

    public static void Main()
    {
        int n = 9;
        Console.Write("Fibonacci number is"
                    + " " + fib(n));
    }
}
RTEU CE100 Week-6
CE100 Algorithms and Programming II
  • Both Tabulated and Memoized store the solutions of subproblems.
  • In Memoized version, the table is filled on demand while in the Tabulated version, starting from the first entry, all entries are filled one by one.
  • Unlike the Tabulated version, all entries of the lookup table are not necessarily filled in Memoized version.
RTEU CE100 Week-6
CE100 Algorithms and Programming II
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure Property in Dynamic Programming

  • A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

  • For example, the Shortest Path problem has following optimal substructure property:

    • If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v. The standard All Pair Shortest Path algorithm like Floyd–Warshall and Single Source Shortest path algorithm for negative weight edges like Bellman–Ford are typical examples of Dynamic Programming.
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure Property in Dynamic Programming

  • On the other hand, the Longest Path problem doesn’t have the Optimal Substructure property. Here by Longest Path we mean longest simple path (path without cycle) between two nodes
RTEU CE100 Week-6
CE100 Algorithms and Programming II

Optimal Substructure Property in Dynamic Programming

  • There are two longest paths from q to t: q→r→t and q→s→t. Unlike shortest paths, these longest paths do not have the optimal substructure property. For example, the longest path q→r→t is not a combination of longest path from q to r and longest path from r to t, because the longest path from q to r is q→s→t→r and the longest path from r to t is r→q→s→t.

center

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Most Common Dynamic Programming Interview Questions

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-1: Longest Increasing Subsequence

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-1: Longest Increasing Subsequence

---

Problem-2: Edit Distance

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-2: Edit Distance (Recursive)

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-2: Edit Distance (DP)

https://www.coursera.org/learn/dna-sequencing

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-2: Edit Distance (DP)

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-2: Edit Distance (Other)

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-3: Partition a set into two subsets such that the difference of subset sums is minimum

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-4: Count number of ways to cover a distance

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-5: Find the longest path in a matrix with given constraints

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-6: Subset Sum Problem

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-7: Optimal Strategy for a Game

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-8: 0-1 Knapsack Problem

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-9: Boolean Parenthesization Problem

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-10: Shortest Common Supersequence

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-11: Partition Problem

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-12: Cutting a Rod

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-13: Coin Change

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-14: Word Break Problem

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-15: Maximum Product Cutting

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-16: Dice Throw

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-16: Dice Throw

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-17: Box Stacking Problem

RTEU CE100 Week-6
CE100 Algorithms and Programming II

Problem-18: Egg Dropping Puzzle

RTEU CE100 Week-6
CE100 Algorithms and Programming II

References

RTEU CE100 Week-6
CE100 Algorithms and Programming II

−End−Of−Week−6−Course−Module−-End-Of-Week-6-Course-Module-

RTEU CE100 Week-6

- Memoization-based solutions will NOT BE ACCEPTED in the exams!