largest no

[bele_harshad2006]

how can i pick up largest no from 5 rows by 5 column matrix????

[Keith Thompson]

CBFalconer <cb********@yah oo.comwrites:

Keith Thompson wrote:

>Richard Heathfield <rj*@see.sig.in validwrites:

>>Tor Rustad said:

... snip ...

>>>
Arrgh.. exponential-time??! The worst sorting algorithms I know,
are O(N^2). :-/

I can't remember Knuth or Sedgewick, discussing anything worse
than that.

Give a hint please..

Well, let's see now...

while not sorted
exchange two elements at random
endwhile

That would do it, I think.

If the exchanges are truly random, that's not guaranteed to
terminate, so it doesn't qualify as an algorithm.

Yes it is, given sufficient time and a really random generator :-)

No, it's not. A truly random generator can generate any possible
sequence, including a sequence that causes the code to repeatedly swap
the first two elements forever. The worst-case behavior is that it
never terminates.

It isn't certain to terminate, but it terminates in some finite time
with probability 1. I *think* that's right. In any case, this
stopped being about C some time ago.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Clark Cox]

On 2007-06-06 20:18:36 -0700, CBFalconer <cb********@yah oo.comsaid:

Keith Thompson wrote:

>Richard Heathfield <rj*@see.sig.in validwrites:

>>Tor Rustad said:

... snip ...

>>>
Arrgh.. exponential-time??! The worst sorting algorithms I know,
are O(N^2). :-/

I can't remember Knuth or Sedgewick, discussing anything worse
than that.

Give a hint please..

Well, let's see now...

while not sorted
exchange two elements at random
endwhile

That would do it, I think.

If the exchanges are truly random, that's not guaranteed to
terminate, so it doesn't qualify as an algorithm.

Yes it is, given sufficient time and a really random generator :-)

No, given a truly random number generator, the probability that it will
terminate *approaches* 100% as time approaches infinity. However you
never have an absolute guarantee that it will terminate as there is a
non-zero chance that , for instance, the sequence of numbers is nothing
but the number 42 repeated an infinite number of times.
--
Clark S. Cox III
cl*******@gmail .com

[mark_bluemel]

On 6 Jun, 17:29, "Joachim Schmitz" <nospam.j...@sc hmitz-digital.de>
wrote:

"CBFalconer " <cbfalco...@yah oo.comschrieb im Newsbeitragnews :46************ ***@yahoo.com.. .

mark_blue...@po box.com wrote:

Richard Heathfield <[e-mail].i nvalidwrote:
mark_blue...@po box.com said:
On 6 Jun, 10:50, bele_harshad2.. [e-mail] wrote:

>>>how can i pick up largest no from 5 rows by 5 column matrix????

>>Step 1. Sort the columns of each row into ascending order.
Step 2. Sort the rows into ascending order using the last column as
the key.
Step 3. Pick the last column of the last row.

>I'm sure we can do better than O(c log c + r log r). Perhaps we
should specify a particular sort. That can get us right up to
O(c^2 + r^2) without any major effort. But can anyone find an
exponential-time algorithm?

There's a big problem here, though - how can we sort anything when
we don't know how to tell whether one thing is larger than another?

You apparantly totally missed the humor involved in RH's post.

I didn't.

Me too I must admit. Isn't that what smileys have been invented for?

As Denis points out, that would ruin the joke. "Dry" humour and irony
(both rather British) should never be sullied with emoticons.

[mark_bluemel]

On 7 Jun, 02:19, Joe Wright <joewwri...@com cast.netwrote:

bele_harshad2.. [e-mail] wrote:

how can i pick up largest no from 5 rows by 5 column matrix????

No matrices in C, sorry. We do have arrays though. Consider..

int arr[5][5];

Does this satisfy your description of a matrix?

The arr array has 25 elements. We can find the largest of them by simply
tripping through the array comparing 'this' one to the previously larger
one. The position of the largest element in the array might also be of
interest. Consider..

int i, j, r, c, max = 0;

Did the problem statement indicate that the numbers were necessarily
positive?

>
for (i = 0; i < 5; ++i)
for (j = 0; j < 5; ++j)
if (arr[i][j] max) {
max = arr[i][j];
r = i, c = j;
}

When this finishes, max will hold the largest int and r and c will tell
you where it is. And very quickly.

<Identity=Origi nalPoster>
Thank you for that solution. I got full marks on the assignment. My
instructor was impressed with my progress.

May I post you the next assignment directly?
</Identity>

[Richard Heathfield]

Keith Thompson said:

Keith Thompson <ks***@mib.orgw rites:

>Richard Heathfield <rj*@see.sig.in validwrites:

>> ma**********@po box.com said:
On 6 Jun, 10:50, bele_harshad2.. [e-mail] wrote:
how can i pick up largest no from 5 rows by 5 column matrix????

Step 1. Sort the columns of each row into ascending order.
Step 2. Sort the rows into ascending order using the last column as
the key.
Step 3. Pick the last column of the last row.

I'm sure we can do better than O(c log c + r log r). Perhaps we
should specify a particular sort. That can get us right up to O(c^2
+ r^2) without any major effort. But can anyone find an
exponential-time algorithm?

Google "permutatio n sort".

Sorry, permutation sort isn't exponential-time. (It's worse.)

Worse is okay too.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Richard Heathfield]

Keith Thompson said:

Richard Heathfield <rj*@see.sig.in validwrites:

>Tor Rustad said:

>>Richard Heathfield wrote:
ma**********@po box.com said:
On 6 Jun, 10:50, bele_harshad2.. [e-mail] wrote:
>how can i pick up largest no from 5 rows by 5 column matrix????

I'm sure we can do better than O(c log c + r log r). Perhaps we
should specify a particular sort. That can get us right up to O(c^2
+ r^2) without any major effort. But can anyone find an
exponentia l-time algorithm?

Arrgh.. exponential-time??! The worst sorting algorithms I know, are
O(N^2). :-/

I can't remember Knuth or Sedgewick, discussing anything worse than
that.

Give a hint please..

Well, let's see now...

while not sorted
exchange two elements at random
endwhile

That would do it, I think.

If the exchanges are truly random, that's not guaranteed to terminate,
so it doesn't qualify as an algorithm.

while not sorted
pick two elements at random
if they are disordered
exchange them
otherwise
find the first two elements that are disordered, and exchange them
end if
endwhile

Not quite as satisfying, but at least it will terminate at some point.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Chris Dollin]

Joachim Schmitz wrote:

"CBFalconer " <cb********@yah oo.comschrieb im Newsbeitrag

>You apparantly totally missed the humor involved in RH's post.

Me too I must admit. Isn't that what smileys have been invented for?

Smileys are a (n ubsubtle) replacement for tone-of-voice and so
should be omitted when wouldn't use the tone-of-voice signal,
such as in written text.

--
"Our future looks secure, but it's all out of our hands." /Man and Machine/
- Magenta

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

[Tak-Shing Chan]

On Thu, 7 Jun 2007, Chris Dollin wrote:

Joachim Schmitz wrote:

>"CBFalconer " <cb********@yah oo.comschrieb im Newsbeitrag

>>You apparantly totally missed the humor involved in RH's post.

Me too I must admit. Isn't that what smileys have been invented for?

Smileys are a (n ubsubtle) replacement for tone-of-voice and so
should be omitted when wouldn't use the tone-of-voice signal,
such as in written text.

Subtle humours are linguistic puzzles in disguise and so
should be omitted when these off-topic elements are lowering the
signal-to-noise for the newsgroup, such as comp.lang.c.

Tak-Shing

[Chris Dollin]

Tak-Shing Chan wrote:

On Thu, 7 Jun 2007, Chris Dollin wrote:

>Joachim Schmitz wrote:

>>"CBFalconer " <cb********@yah oo.comschrieb im Newsbeitrag

>>>You apparantly totally missed the humor involved in RH's post.
Me too I must admit. Isn't that what smileys have been invented for?

Smileys are a (n ubsubtle) replacement for tone-of-voice and so
should be omitted when wouldn't use the tone-of-voice signal,
such as in written text.

Subtle humours are linguistic puzzles in disguise

So is text.

and so
should be omitted when these off-topic elements are lowering the
signal-to-noise for the newsgroup, such as comp.lang.c.

Wouldn't leave much.

Use all the smileys you like -- take my spare ones if you will.

--
"No-one here is exactly what he appears." G'kar, /Babylon 5/

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

[mark_bluemel]

On 7 Jun, 11:57, Richard Heathfield <[e-mail].i nvalidwrote:

Chris Dollin said:

<snip>

Use all the smileys you like -- take my spare ones if you will.

He's already pinched all mine. I think he's going for a global monopoly.

Do you recommending declaring those in header files?