> For the complete documentation index, see [llms.txt](https://2ood.gitbook.io/2ood-knowledge-base/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://2ood.gitbook.io/2ood-knowledge-base/lecture-notes/algorithms/2023-11-01.md).

# 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)*k*j$
* 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.