$(1$ points$)$ Write the pseudocode for this problem using a Divide and Conquer $($recursive$)$

approach. Solutions using other approaches or providing code instead of pseudocode will

not receive credit. No exceptions!

$(1$ point$)$ Create a visualization of the recursion tree generated by your pseudocode for

the following input: $P=[10,30,5,60,20]$

$(1$ points$)$ Analyize your pseudocode, create a recurrence relation for your pseudocode

and compute the Theta time complexity of the recurrence relation provided.$(3$ points$)$ You are given a sequence of matrices $A_0,A_1,$dots,$A_i,$dots,$A_n$ where each matrix $A_i$ has

dimensions $p_{i-1}{p}_i.$ Your task is to determine the minimum number of scalar multiplications

needed to multiply the entire sequence of matrices using a divide$-$and$-$conquer approach

Input: an array $P$ of size $n+1$ where $P[i]$ represents the number of rows in matrix $A_i$ and

$P[i+1]$ represents the number of columns in matrix $A_i$

Output: The minimum number of scalar multiplications required to multiply the entire chain

of matrices.

Example:

Input: $P=[10,30,5,60]$

Explanation: you need to multiply $3$ matrices $A_1(1030),A_2(305),A_3(560)$

There are two possible ways to parenthesize the matrix multiplication:

$*(A_1{A}_2)A_3$

First multiply $A_1(1030)A_2(305),$ this requires $10305=1500$ scalar

multiplications

Then multiply, $A_3(560),$ this requires $10560=3000$ scalar multiplications

Total Cost: $1500+3000=4500$

$A_1(A_2{A}_3)$

First multiply $A_2(305)A_3(560),$ this requires $30560=9000$ scalar

multiplications

Then multiply, $A_1(1030),$ this requires $103060=18000$ scalar multi$-$

plications

Total Cost: $9000+18000=27000$

Output: The minimum cost of matrix multiplication is $4500$ scalar multiplications cor$-$

responding to $(A_1{A}_2)A_3$