Given a N N M atrix M filled with positive integers, find all the…
Question Answered step-by-step Given a N N M atrix M filled with positive integers, find all the… Given a N ? N M atrix M filled with positive 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 {P1, P2, …, Pk, …, Pn} be a set of solutions for this problem where Pk = {M(i, j)1+M(i, j)2+ M(i, j)3 + … + 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 Pk. The S sum is valid only if: 1. All the indexes i and j for that sum of Pk are unique 2. The integer in M(i, j) is not zero 3. Index j in M(i, j)x must be the same as index i in M(i, j)x+1 4. Index i in M(i, j)1 and index j in M(i, j)m must be zero for all the solutions Pk 5. A possible solution Pk is only considered an optimal solution if the sum S of all its integers is the minimum or the maximum sum S from all the solutions Pk 6. 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: 1. P = {M[0][1] + M[1][3] + M[3][2] + M[2][0]} = 15 2. P = {M[0][2] + M[2][3] + M[3][1] + M[1][0]} = 15 As you can see, solutions 1 and 2 met all the conditions above 3 . Based on your backtracking algorithm, create the pseudocode that finds all the solutions for any given matrix M. Note that your pseudocode can be either iterative or recursive. In this assignment, pseudocoding with LaTeX is not mandatory, students can just type the pseudocode. 4. Analyze your backtracking algorithm and find its time and space complexities based on that analysis. Note that if your pseudocode is recursive, you must use the back substitution method first, and then check your time complexity result using the Master Theorem. On the other hand, if your pseudecode is iterative, then you must use a step counting approach. please solve those two question Engineering & Technology Computer Science CSC 510 Share QuestionEmailCopy link Comments (0)
