2. Develop an eficient algorithm insert (A, n, value) where A is a nonfull ma- trix (i.e. a matrix satisfying the above conditions, containin at least one INF value), and value a number to be insterted. The insertion must occur in place, that is no additional matrix (or additional array of any kind) can be used. 3. Using no other sorting method, but the algorithms developed in previous parts of this exercise (if needed), develop an algorithm that sorts n² numbers in O(n³) time. You must use a n x n matrix as desribed above. Exercise 4.4: Search a matrix 147 11 15 2 58 12 19 369 16 22 10 13 14 17 24 18 21 23 26 30 Given a matrix (2D array) with n integers, search for a target value x, efficiently, i.e., return whether x exists in the matrix (true/false). Assumptions: • Each row is sorted in ascending order Each column is sorted in ascending order In what follows, we will call a matrix any matrix that satisfies the conditions shown in the image above. We will addittionally assume, that the matrix may have missing numerical ele- ments. In this case, the cell fill be filled with the special value INF which is larger than any number (like infinity in mathematics). If a row contains an INF value this must be the last value, and if a column contains an INF value this must be the last value as well. For example, if a matrix contains a single INF value (and the rest is filled with numbers) the INF value must be located in the bottom row of the right- most column. If a matrix contains no numbers (a.k.a empty matrix), it will be filled only with INF values. In the form a warmup exercise, draw a 4 x 4 matrix containing elements {9, 16, 3, 2, 4, 8, 5, 14, 12}. 1. Develop an efficient algorithm called popmin (A, n) where A is a nonempty nx 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. Since we are removing a number from the matrix, the matrix after the operation will contain one more INF value. HINT: Think of BuildMaxHeap and don't forget to use recursion! The required operation must occur in place, that is no additional matrix (or additional array of any kind) can be used.

2. Develop an eficient algorithm insert (A, n, value) where A is a nonfull ma- trix (i.e. a matrix satisfying the above conditions, containin at least one INF value), and value a number to be insterted. The insertion must occur in place, that is no additional matrix (or additional array of any kind) can be used. 3. Using no other sorting method, but the algorithms developed in previous parts of this exercise (if needed), develop an algorithm that sorts n² numbers in O(n³) time. You must use a n x n matrix as desribed above. Exercise 4.4: Search a matrix 147 11 15 2 58 12 19 369 16 22 10 13 14 17 24 18 21 23 26 30 Given a matrix (2D array) with n integers, search for a target value x, efficiently, i.e., return whether x exists in the matrix (true/false). Assumptions: • Each row is sorted in ascending order Each column is sorted in ascending order In what follows, we will call a matrix any matrix that satisfies the conditions shown in the image above. We will addittionally assume, that the matrix may have missing numerical ele- ments. In this case, the cell fill be filled with the special value INF which is larger than any number (like infinity in mathematics). If a row contains an INF value this must be the last value, and if a column contains an INF value this must be the last value as well. For example, if a matrix contains a single INF value (and the rest is filled with numbers) the INF value must be located in the bottom row of the right- most column. If a matrix contains no numbers (a.k.a empty matrix), it will be filled only with INF values. In the form a warmup exercise, draw a 4 x 4 matrix containing elements {9, 16, 3, 2, 4, 8, 5, 14, 12}. 1. Develop an efficient algorithm called popmin (A, n) where A is a nonempty nx 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. Since we are removing a number from the matrix, the matrix after the operation will contain one more INF value. HINT: Think of BuildMaxHeap and don't forget to use recursion! The required operation must occur in place, that is no additional matrix (or additional array of any kind) can be used.