according to the problem $1$ solution complete the all parts and show all the work for each part.

a$)$ Create a state$-$space tree to design a Branch && Bound algorithm to find all the solutions for the matrix given in problem #$1$ Note that approaches other than creating a state$-$space tree for this algorithm won$$t get credit. Show all your work

Find the complexity and time complexity of your backtracking algorithm. Show all your work to get credit.

b$)$Compute the T$($n$)$ functions from your pseudocode created in problem $3$

c$)$ Perform the back$-$substitution to your T$($n$)$ functions and define their Theta time and space complexities

d$)$Backtracking Algorithm for Matrix M

Given Matrix M:

$,20,22,21,15,16$

$20,,20,14,17,13$

$22,20,,23,19,11$

$21,14,23,,17,16$

$15,17,19,17,,16$

$16,13,11,16,16,$

State$-$Space Tree:

Root Node: Start from any cell and explore all paths.

Optimal Path Calculation $($Example$)$:

Path: $[M[0][1],M[1][5],M[5][4],M[4][3],M[3][2],M[2][0]]$

Sum: $20+13+16+17+23+22=111$

All Possible Solutions and Sums:

$P=\{M[0][1]+M[1][5]+M[5][4]+M[4][3]+M[3][2]+M[2][0]\}=20+13+16+17+23+22=111$

$P=\{M[0][2]+M[2][3]+M[3][4]+M[4][5]+M[5][1]+M[1][0]\}=22+23+17+16+13+20=111$

$P=\{M[0][5]+M[5][1]+M[1][4]+M[4][3]+M[3][2]+M[2][0]\}=16+13+17+17+23+22=108$ Explain $($in plain English$)$ if you think that there is a way to optimize the two algorithms covered in this homework. If not, then explain why