Exercise 4.4: Search a matrix Given a matrix (2D array) with n integers, search for a target value x, efficiently, i.e.,

[answerhappygod]

Exercise 4.4: Search a matrix Given a matrix (2D array) with nintegers, search for a target value x, efficiently, i.e., returnwhether x exists in the matrix (true/false). Assumptions: • Eachrow is sorted in ascending order • Each column is sorted inascending order
In what follows, we will call a matrix any matrix that satisfiesthe conditions shown in the image above. We will addittionallyassume, that the matrix may have missing numerical elements. Inthis case, the cell fill be filled with the special value INF whichis larger than any number (like infinity in mathematics). If a rowcontains an INF value this must be the last value, and if a columncontains an INF value this must be the last value as well. Forexample, if a matrix contains a single INF value (and the rest isfilled with numbers) the INF value must be located in the bottomrow of the rightmost column. If a matrix contains no numbers (a.k.aempty matrix), it will be filled only with INF values. In the forma warmup exercise, draw a 4 × 4 matrix containing elements {9, 16,3, 2, 4, 8, 5, 14, 12}.
1. Develop an efficient algorithm called popmin(A, n) where A isa nonempty n × n matrix which returns the smallest element of A(which by definition is the element located in row 1, column 1)preserving the properties of the matrix as described above. Sincewe are removing a number from the matrix, 2 the matrix after theoperation will contain one more INF value. Hint: Think ofBuildMaxHeap and don’t forget to use recursion! The requiredoperation must occur in place, that is no additional matrix (oradditional array of any kind) can be used.
2. Develop an eficient algorithm insert(A, n, value) where A isa nonfull matrix (i.e. a matrix satisfying the above conditions,containin at least one INF value), and value a number to beinsterted. The insertion must occur in place, that is no additionalmatrix (or additional array of any kind) can be used.
3. Using no other sorting method, but the algorithms developedin previous parts of this exercise (if needed), develop analgorithm that sorts n 2 numbers in O(n 3 ) time. You must use a n× n matrix as desribed above.