2023-11-06

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time

---

Matrix Chain Multiplication

Tabulation

We make two matrices One is for cost tracking, the other is for paranthesis cuttitng index backtracking.

• Cells of i=j, it means one single matrix, so diagonals are zero.

• Each cell means that the minimum cost of $A_{i+1}$ through $A_{j+1}$

• we will calculate first from semidiagonals that are closer to main diagonal, outwards.

• Our final cost will be at [0][n-1] th cell.

• for multiple calculations, you will check possible options and find the minimum.

• At the second matrix, you will write the index you put the paranthesis.

Longest Common Subsequence

What is the common subsequence? character should appear in the same order.

problem statement given two string. find characters that are in the same sequence inside each string, and print the max length of it.

Recursion

we make a function LCS(String x, String y, int n, int m) base case : when $n=0 \text{ or};m=0$ Decreasing function : from last character, move to the next character and reduce the size.

If matched, increase the result +1. If not matched, decrease n or decrease m. choose whichever that gives the longest result.