wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find number in ordered matrix.
        
(Message started by: Corin on Nov 13^th, 2007, 6:38pm)

Title: Find number in ordered matrix.
Post by Corin on Nov 13^th, 2007, 6:38pm

Given an ordered matrix, both the column and row is increasing with index. How to find a number in this matrix?

It's an old problem, I don't see how to get a solution with O(n). Thanks for anybody who knows to have a note here...

Title: Re: Find number in ordered matrix.
Post by dont.hurt.again on Nov 13^th, 2007, 9:48pm

start moving from top right corner .

when ever u encounter a bigger no move downwards and if no is smaller move leftside.

either u will get ur no or u will be unable to move further. If u are unable to move then there is no such no in the matrix.

the maximum move a person can make is 2n where matrix is nXn.

Title: Re: Find number in ordered matrix.
Post by Corin on Nov 13^th, 2007, 10:27pm

Assume you have 4x4 matrix like:

1 2 5 6
2 3 6 7
3 4 7 9
8 10 11 12

How to search "8" with your strategy? Thanks.

Title: Re: Find number in ordered matrix.
Post by riddle_sea on Nov 13^th, 2007, 10:31pm

If i am not mistaken then this kind of matrix is given a special name? Can anyone suggest the name?

Title: Re: Find number in ordered matrix.
Post by riddle_sea on Nov 13^th, 2007, 10:42pm

on 11/13/07 at 22:27:40, Corin wrote:

Assume you have 4x4 matrix like:

1 2 5 6
2 3 6 7
3 4 7 9
8 10 11 12

How to search "8" with your strategy? Thanks.

we can similarly use the same strategy....
we will move downwards starting from 6 till we reach 9 then as 8 is smaller we move left and meet 7 then we move downward again and encounter 11 and as 8 is smaller we move to the left and meet 8 at the last.....

and yes this matrix's special name is Young's Matrix

Title: Re: Find number in ordered matrix.
Post by Grimbal on Nov 14^th, 2007, 5:50am

on 11/13/07 at 22:27:40, Corin wrote:

Assume you have 4x4 matrix like:

1 2 5 6
2 3 6 7
3 4 7 9
8 10 11 12

How to search "8" with your strategy? Thanks.

Start from top right corner, 6.
- 6 is too small, go down to 7
- 7 is too small, go down to 9
- 9 is too large, go left to 7
- 7 is too small, go down to 11
- 11 is too large, go left to 10
- 10 is too large, go left to 8
- 8 ... bingo!

There are maximum 2n-1 tests. It can be more than n, but that is still O(n).

Title: Re: Find number in ordered matrix.
Post by gotit on Nov 14^th, 2007, 7:37am

on 11/13/07 at 22:31:27, riddle_sea wrote:

If i am not mistaken then this kind of matrix is given a special name? Can anyone suggest the name?

As far as I know such a matrix is called a Young's tableau. Btw, I have two more questions on Young's tabeau.

i) Consider a non-full young's tableau(the empty positions are filled with some large number).How will you insert an element inside the matrix?
ii) How will you sort the elements of a completely filled Young's tableau.

Title: Re: Find number in ordered matrix.
Post by riddle_sea on Nov 14^th, 2007, 12:41pm

on 11/14/07 at 07:37:01, gotit wrote:

As far as I know such a matrix is called a Young's tableau. Btw, I have two more questions on Young's tabeau.

ii) How will you sort the elements of a completely filled Young's tableau.

we can solve it through heaps...
what we have in hand, we have n sorted arrays and total elements nxn...

make a heap containing the first element of each row (being the minimum of the row) then min-heapify it.. you will get the minimum of all 1st column elements.. put that element into the final array.
Now from the array (row) to which the minimum element belongs take the next column element and insert into heap... now again min-heapify ... again put the smallest into the final array...
continue till you have examined all the elements...

The order is O(n²log n)....

Tell me if i am wrong....

Title: Re: Find number in ordered matrix.
Post by swami on Nov 15^th, 2007, 7:25am

Cant we merge 2 rows (or cols) in O(n)??

To merge all the 'n' rows, it will take O(n^2). Isnt that the best we can do?

Title: Re: Find number in ordered matrix.
Post by Grimbal on Nov 15^th, 2007, 8:20am

I believe merging k rows or size n is O(nk log k).

Title: Re: Find number in ordered matrix.
Post by aditi on Nov 15^th, 2007, 5:48pm

Let us assume that empty slots are indicated by 'infinity'.
1.In a Youngs tableau, the largest element is A[n][n]. Thus if A[n][n] is not infinity, then there are no empty slots and we can exit.
2.Else, i = j =n.
3.Place the element to be inserted in A[i][j].
4.Find m =max(A[i][j], A[i][j-1], A[i-1][j])
5.if(m=A[i][j]) quit.
6.if(m=A[i][j-1]) {swap(A[i][j],A[i][j-1]); j--;}
else {swap(A[i][j], A[i-1][j]); i--;}
7.Repeat steps 3-7 as long as i!=1 or j!=1.

Title: Re: Find number in ordered matrix.
Post by bbskill on Nov 16^th, 2007, 10:18am

on 11/15/07 at 08:20:01, Grimbal wrote:

I believe merging k rows or size n is O(nk log k).

Why it will take O(nk log k). Each row is sorted, so we could merge any two sorted rows in O(n), right?
Since there are n rows, we could sort them into an array of n^2 size in O(n^2).
The recursion formula is F(n) = F(n-1) + n; F(1) = n;
Am I right?

Title: Re: Find number in ordered matrix.
Post by towr on Nov 16^th, 2007, 2:11pm

on 11/16/07 at 10:18:36, bbskill wrote:

Why it will take O(nk log k). Each row is sorted, so we could merge any two sorted rows in O(n), right?

Let's take 8 rows to start with, as an example
We pair the rows up, and get 4 rows of length 2N in O(8N) time
Then we pair the 4 new rows up again and get 2 rows of 4N in O(8N) time
Then we pair those final two rows up, and merge then in O(8N) time
so in total, O(log(8)*8N).

In general a similar method would give O(n k log(k)).

Title: Re: Find number in ordered matrix.
Post by wanderer on Nov 26^th, 2007, 11:35pm

on 11/13/07 at 18:38:53, Corin wrote:

its an old problem..pardon me for coming back to it..
I know the O(n) solution. But is it possible to solve it in O(log n) time ?

Title: Re: Find number in ordered matrix.
Post by Grimbal on Nov 27^th, 2007, 1:02am

It is not.

In the special case where all items above the reverse diagonal (from top right to bottom left) are smaller than the item you search and all items below it are larger, in that special case the only way to eliminate an item of the diagonal from consideration is to test it directly. So in the worst case, you have to check n items.