| Username |
Post |
| HomeBoy |
Posted
on 15-Dec-01 10:20 PM
Hi Desi folks,
I know there are a lot of Desi folks pursing degree in Computer Science. Could someone hint me to crack this?
Question:
The input is an N x N Matrix of numbers that is already in memory. Give an O(N) worst-case algorithm that decides if a number X is in the matrix.
|
| DESI |
Posted
on 16-Dec-01 02:35 PM
HomeBoy,
You appears to be new in this site! For your question, you are at very WRONG place because 'celebraties' of this site are not so DIVERSE, but STERIO TYPE.
Ask some questions regarding Nepali and American politics, there are a good number of EXPERTS here. Your probability to get such a answear is 98.66666666.
Dude, never Mind.
|
| Biswo |
Posted
on 16-Dec-01 03:48 PM
I think this question is easy.
You can just look at each number. It is linear search, and of O(N) algorithm.
|
| DESI |
Posted
on 16-Dec-01 04:39 PM
Home Boy,
It is ready; Get your fast Food! I mean Cake!!!
|
| le chef du nuit |
Posted
on 17-Dec-01 12:26 PM
since its a n*n matrix, would the search be linear?
the worst possible way to search that space would be
for i in 1..n do
for j in 1..n do
check position (i,j)
worst case would be if the think your looking for is in the (n,n) slot
so the worst case is o(n^2)
|
| sudhos |
Posted
on 17-Dec-01 12:59 PM
Well, homeboy, it is little tricky, right? Here is fully Baked Cake!
The above problem is NOT EASY as it seems coz the
KEY QUESTION is WORST CASE Time. However, not hard as well
if it is seen in another way.
But, just applying linier search on every cell,
it is IMPOSSSIBLE to write an algorithm to find
X in O(N),worst case time UNLESS there is a Restriction
on how inputs are arranged in rows and column of the matrix.
Because,
N x N matrix has N^2 cells, and the last cell position is
N^2 i.e if N=10, N^2 = 100. If it happens that the X is in
last cell, which is worst case, we need to check every other
99 cells positions before 100 cell position. That means O(N^2),
quadratic worst case time.
So, the question is: is it possible to have an algorithm
to solve it in O(N) time?
Answear is:
YES if and only if there are following restrictions:
1)Each value in cell in a Row should be increasing left to right
2)Each value in cell in a Column should be increasing top to bottom.
Here is how to solve:
With a linear search down the DAIGONAL to find an element
greater than or equal to your search term, you get at most
N tests. If you were to do a binary search down the
diagonal, that part would contribute O(logN).
Locating the proper DAIGONAL element, X(n,n), then leaves
you with two other ordered arrays to search, one is of size
n-1 to the left of X(n,n) and the other is of size N-n to the
right of element X(n-1,n-1). You would want to do a binary
search on them, too, when N gets to be sufficiently large.
Here is pusedocode:
i = j = 0;
do {
n = a[i][j];
if (n == X) return TRUE;
if (n > X) return FALSE;
if (n newi = i; newj = j;
if (a[i+1][j]>X)
j++;
else i++;
}
} while ((i return FALSE;
|
| Biswo |
Posted
on 17-Dec-01 09:36 PM
Hey, I thought total number of elements (n*n) was N. So, I told it would be N^2
algorithm.
Unless it is sorted, or have any other particular property, I don't think there is
any algorithm of O(N) complexity. I second Sudhos on this. Sorry for the mistake.
|
| GP |
Posted
on 17-Dec-01 10:50 PM
What happens if its a banded matrix of N and half band width of M?
|
| Biswo |
Posted
on 17-Dec-01 10:57 PM
Sorry.
>So, I told it would be N^2 algorithm.
So, I said it would be O(N) algorithm.
--------
What is half bandwidth, banded , GPJi? I just didn't see the terms in matrix.
|
