Selection Problem - Matrix

[anirban]

Let A be a real valued matrix of order n*n already stored in memory. Its (i, j)-th element is denoted by a[i, j]. The elements of the matrix A satisfy the following property:

Let the largest element in row i occur in column Li. Now, for any two rows i1, i2, if i1<i2, then Li1<=Li2.

(a)
2 6 4 5 3
5 3 7 2 4
4 2 10 7 8
6 4 5 9 7
3 7 6 8 12

(b)

Row I l(i)
1 2
2 3
3 3
4 4
5 5

Figure shows an example of (a) matrix A, and (b) the corresponding values of l_i for each row i.

Write an algorithm for identifying the largest valued element in matrix A which performs at most O(n*logn) comparisons.

[stevesmithx]

To get better help, post the code you have so far.

[anirban]

no i just want the algo in O(nlogn) time please

[brewbuck]

no i just want the algo in O(nlogn) time please

You aren't going to get it.

[arpsmack]

Are you certain that it is O(n*log n)?
Because i think that would mean you can perform only 4(~3.5) comparisons at most
for the example problem you have posted.

This is not true, you are ignoring the hidden constant. In fact, the algorithm could use 1 billion comparisons for a 5x5 matrix and still be O(n log n).

On a less important note, logarithms in computer science typically refer to the log base 2, while you are calculating the log base 10. This doesn't matter quite as much since logs of different bases are proportional to each other by a constant factor, making them equivalent in Big-Oh notation.

which means the obvious O(n) solution

I would be interested in hearing your O(n) solution because I'm pretty sure no O(n) solution exists. I'm thinking that you are probably misunderstanding the problem, but I'm willing to hear you out.

@anirban:

The presence of "log n" in the upper bound for an algorithm usually indicates some kind of divide-and-conquer approach. Consider an algorithm like mergesort: divide the list in half, sort each half, merge the two halves.

Is there a way you can partition your problem into two smaller chunks, and then recursively perform your algorithm on those chunks? This hopefully starts you off in the right direction. If not, then there isn't much I can say besides just handing you an answer.

[OnionKnight]

I would be interested in hearing your O(n) solution because I'm pretty sure no O(n) solution exists. I'm thinking that you are probably misunderstanding the problem, but I'm willing to hear you out.

There is only one row you'd need to search through as all other rows are guaranteed to have it's maximum value less than it. In the case of equality, it wouldn't matter which of the possible rows you'd pick so you can just search through that row.

[arpsmack]

There is only one row you'd need to search through as all other rows are guaranteed to have it's maximum value less than it. In the case of equality, it wouldn't matter which of the possible rows you'd pick so you can just search through that row.

Ah ok, that's what I figured you were thinking.

What the problem states is that the *column index* of the maximum element in a row will be less if the row index is less, it doesn't say that the value of the maximum element will be less. The maximum value for the entire matrix could be in any row.

Here's a valid matrix that has its maximum value in the first row (the max value in each row is underlined):

.   0 1 2 3 4
.   ---------
0 | 9 7 4 3 2
1 | 8 1 1 2 7
2 | 3 5 2 2 1
3 | 3 3 4 2 6
4 | 1 2 5 4 8

Row   | Column Index of Max Value
0     | 0
1     | 0
2     | 1
3     | 4
4     | 4

[OnionKnight]

for any two rows i1, i2, if i1<i2

What does it mean that a row is less than another?

[anirban]

means row number i1 < row number i2

[stevesmithx]

Write an algorithm for identifying the largest valued element in matrix A which performs at most O(n*logn) comparisons.

Are you certain that it is O(n*log n)?
Because i think that would mean you can perform only 4(~3.5) comparisons at most
for the example problem you have posted.

[laserlight]

means row number i1 < row number i2

Honestly, I do not understand what that means either. What is a row number?

[stevesmithx]

I think the OP is referring to the index number of the rows of the matrix (a)

(a)
1->2 6 4 5 3
2->5 3 7 2 4
3->4 2 10 7 8
4->6 4 5 9 7
5->3 7 6 8 12

The second matrix (b) have the indices of these rows in their 1st column
and the indices of the columns having the largest number in the current row in the 2nd column.
This problem would be much easier to solve without the O(nlogn) restriction.

[OnionKnight]

I think the OP is referring to the index number of the rows of the matrix (a)

The second matrix (b) have the indices of these rows in their 1st column
and the indices of the columns having the largest number in the current row in the 2nd column.
This problem would be much easier to solve without the O(nlogn) restriction.

The ordo notation gives upper bounds, which means the obvious O(n) solution is also O(n*log(n)). Not sure if I want to point it out though, seems to be an awful lot like "do my homework".

[stevesmithx]

On a less important note, logarithms in computer science typically refer to the log base 2, while you are calculating the log base 10. This doesn't matter quite as much since logs of different bases are proportional to each other by a constant factor, making them equivalent in Big-Oh notation.

I agree with this. Now the n log n evaluates to 12 for n=5.

This is not true, you are ignoring the hidden constant. In fact, the algorithm could use 1 billion comparisons for a 5x5 matrix and still be O(n log n).

Hmm, I am confused here.
Could you explain what hidden constant i am missing here?
i think you are exaggerating when you say 1 billion!! here

[brewbuck]

I agree with this. Now the n log n evaluates to 12 for n=5.


Hmm, I am confused here.
Could you explain what hidden constant i am missing here?
i think you are exaggerating when you say 1 billion!! here

Big-Oh notation talks about limits and "aymptotic behavior." I.e. the SHAPE of the curve as N increases. It says nothing about the overall SLOPE of the curve.