2023-11-01

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time tabulation of MCM

---

Matrix Chain Multiplication

Recursion

algorithm idea development. We build a MCM(arr[], i, j) recursion function.

• i should start from 1, and each i-th matrix $A_{i}$ is arr[i-1] by arr[i] size.

• base case is when i and j are the same. cost is 0.

• iteration of k,

  • k goes from i to j-1.

  • k=j is not possible because the splitting happens like this : $MCM(arr,i,k) + MCM(arr,k+1,j)$

  • cost of breaking at k is $MCM(arr,i,k) + MCM(arr,k+1,j)+ (i-1)kj$

• iterate k, and keep track of the minimum cost.

problems based on MCM

• MCM

• printing MCM

• Evaluate Expression to True/Boolean Paranthesization

• Min/Max value of an Expression ex. 2*3+5 ->2*(3+5)

• Palindrome Partitioning ex. aab-> [["a","a","b"],["aa","b"]]

• Scramble String

• Egg Dropping Problem.

base case on Recursion becomes the initial value of tabulation.