algo_lec10

 

Today's Topics

Example 5. Revisit Chained Matrix Multiplication

Example 6. Edit distance

---

Example 5. Revisit Chained Matrix Multiplication

- 목표: 행렬 곱셈의 순서를 바꿔 곱셈 연산 수를 최소화

 

- How many distinct arrangements of n pairs of left-right parentheses are there all of which does?

- The n-th Catalan number, C(n)

• C(1) = 1, ()
• C(2) = 2 ()() and (())
• C(3) = 5 ()()(), ()(()),(())(),((()))

At very last step, we compute (Ai × Ai+1 × ... × Ak) × (Ak+1 × ... × Aj) at some point k, i ≤ k < j
So, the chain is split into these two subchains,
that is, find the minimum number of multiplications for (Ai × Ai+1 × ... × Ak) and the one for (Ak+1 × ... × Aj). 
Thus, Cost(Ai...j) = min_k ( Cost(Ai...k) + Cost(Ak+1...j) + pi-1 * pk * pj )

Establish recursive property:

If i=j, then 0
If i<j, m[i][j] = min(m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]) 

[예시] A_1: 30x1, A_2: 1x40, A_3: 40x10, A_4: 10x25 

(A₂×A₃) × (A₄): 400 + 0 + 1×10×25 = 400 + 250 = 650
(A₁) × (A₂×A₃×A₄): 0 + 650 + 30×1×25 = 650 + 750 = 1400
→ 최소 곱셈 수: 1400

• m[1][3] = min( (A₁)×(A₂×A₃), (A₁×A₂)×(A₃) ) = min(0 + 400 + 30×1×10, 1200 + 0 + 30×40×10)
• m[2][4] = min( (A₂)×(A₃×A₄), (A₂×A₃)×(A₄) ) = min(0 + 10,000 + 1×40×25, 400 + 0 + 1×10×25)
• m[1][4] = (A₁) × (A₂×A₃×A₄) = m[1][1] + m[2][4] + p₀×p₁×p₄ = 0 + 650 + 30×1×25 = 1400

- 시간 복잡도: O(n^3), 공간 복잡도: O(n^2)

---

Example 6: Edit distance

- 정의: 문자열 S를 T로 바꾸기 위해 필요한 최소 편집 연산 수 (삽입, 삭제, 치환)

- Example (S='agaatgca', T='acaagrga')

The # of edit operations = 4

Compute the edit distance between cat and cake.

[step1] Create the table with rows(' ','c','a','t') and columns(' ','c','a','k','e') and compute edit distance when one side is  null.

[step2] If the characters are same, take the value on left above

[step3] For other cases, take the minimum on values on left-above, left, and above and then increment by 1.

두 문자의 비교 결과가 서로 다를 때 (si ≠ tj) 이 경우에는 3가지 연산 중 하나를 선택:
1) 삽입 (Insert): 왼쪽 값 → d[i][j-1]
2) 삭제 (Delete): 위쪽 값 → d[i-1][j]
3) 교체 (Replace): 대각선 왼쪽 위 값 → d[i-1][j-1]
이 셋 중 가장 작은 값을 선택하고 +1을 더함 → 편집 연산 1회를 추가 의미.

 

d[8][8] = 3 이라는 뜻은: S = agaattgca를 T = acaagtga로 바꾸려면 최소 3번의 편집 연산이 필요.

 

- 점화식:
    d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + t[i][j])
    where t[i][j] = 0 if s[i] == t[j], else 1

- 초기값: d[i][0] = i, d[0][j] = j

 

- Time complexity and Space complexity: O(mn), m은 S의 길이, n은 T의 길이