Algorithms question: Assumptions: Integers in each row are sorted in ascending from left to right. Integers in each colu
Posted: Tue Jul 12, 2022 8:17 am
Algorithms question:
Assumptions:
Integers in each row are sorted in ascending from left toright.
Integers in each column are sorted in ascending from top tobottom.
Special Assumptions:
The matrix may have missing elements. If that is the case: thecell value will be replaced with a special value called INF. Thinkof INF as a value that is bigger than any number (similar toinfinity in mathematics).
If a row contains this INF value, it will be the last value onthe row.
If a column contains this INF value, it will be the last valueon the column.
Examples:
if our matrix contains one INF value (and the rest are numbers),the INF value will be located at the bottom row of the rightmostcolumn.
If our matrix has NO numbers, all cells will have INF values
Question:
Create an efficient algorithm in pseudocode called minVal(B, n)where B is a non-empty n x n matrix, which returns the smallestelement of B (element located in row 1, column 1) having theassumptions of the matrix as described. Since we are removing anumber from the matrix, after the algorithm runs, the matrix willcontain one more INF value. The algorithm must be in-place thusadditional matrix can be used. (n is the number of rows)
Hint: Think BuildMaxHeap and recursion
Assumptions:
Integers in each row are sorted in ascending from left toright.
Integers in each column are sorted in ascending from top tobottom.
Special Assumptions:
The matrix may have missing elements. If that is the case: thecell value will be replaced with a special value called INF. Thinkof INF as a value that is bigger than any number (similar toinfinity in mathematics).
If a row contains this INF value, it will be the last value onthe row.
If a column contains this INF value, it will be the last valueon the column.
Examples:
if our matrix contains one INF value (and the rest are numbers),the INF value will be located at the bottom row of the rightmostcolumn.
If our matrix has NO numbers, all cells will have INF values
Question:
Create an efficient algorithm in pseudocode called minVal(B, n)where B is a non-empty n x n matrix, which returns the smallestelement of B (element located in row 1, column 1) having theassumptions of the matrix as described. Since we are removing anumber from the matrix, after the algorithm runs, the matrix willcontain one more INF value. The algorithm must be in-place thusadditional matrix can be used. (n is the number of rows)
Hint: Think BuildMaxHeap and recursion