Solve all parts and mention each part. Complete all parts on a piece of paper. donot just explain on how to do it$.$ I need final answers for all the parts. Given a $N*N$ Matrix $M$ filled with non$-$negative integers, find all the possible cells $M(i,j)$

where indexes i and j are unique and the sum of those cells is maximized or minimized for all the

possible solutions found.

The formal definition of the problem is the following:

Let $\{P_1,P_2,$dots,$P_k,$dots,$P_n\}$ be a set of solutions for this problem where $P_k=\{\begin{array}{ccc}M(i,& j{)}_1+M(i,& j{)}_2+\end{array}$

$\{$:$M(i,j{)}_3+$dots$+M(i,j{)}_{m-1}+M(i,j{)}_m\}=S$ is a set of coordinates for integers values in a matrix,

and $S$ the sum of those integers for that solution $P_k.$ The $S$ sum is valid only if:

All the indexes i and $j$ for that sum of $P_k$ are unique

The integer in $M(i,j)$ is not zero

Index $j$ in $M(i,j{)}_x$ must be the same as index $i$ in $M(i,j{)}_{x+1}$

Index $i$ in $M(i,j{)}_1$ and index $j$ in $M(i,j{)}_m$ must be zero for all the solutions $P_k$

A possible solution $P_k$ is considered optimal only if the sum $S$ of all its integers is the minimum

or the maximum sum $S$ from all the solutions $P_k$

All the vertices but the source vertex must be visited only once. The source vertex is visited

twice because it plays the role of the source and destination vertex in this algorithm

For example, given the following matrix $M$ filled with integers and zeros find all the possible

results that met the above conditions.

All possible solutions are:

$P=\{M[0][1]+M[1][5]+M[5][4]+M[4][3]+M[3][2]+M[2][0]\}=23$

$P=\{M[0][2]+M[2][3]+M[3][4]+M[4][5]+M[5][1]+M[1][0]\}=23$

$P=\{M[0][2]+M[2][3]+M[3][4]+M[4][1]+M[1][5]+M[5][0]\}=30$

$P=\{M[0][5]+M[5][1]+M[1][4]+M[4][3]+M[3][2]+M[2][0]\}=30$

a$)$ Create a state$-$space tree to design a backtracking algorithm to find all the solutions

for the following matrix $M.$ Note that approaches other than creating a state$-$space tree for

this algorithm won't get credit. Show all your work

b$)$ 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

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

Compute the T$($n$)$ functions from your pseudocode created in problem d$)$ Perform the back$-$substitution to your T$($n$)$ functions and define their Theta time and space complexities

e$)$ 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

f$)$ Create a program, using python programming language, that implements your algorithms $($both of them$).$ To get credit for this problem students must provide some unit tests to test that your program performs as per your algorithm specifications. Create this program in an online editor and share here the link to your program.