Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > math question in c algorithm book help please

Reply
Thread Tools

math question in c algorithm book help please

 
 
ben
Guest
Posts: n/a
 
      02-06-2005
hello,
i'm following an algorithm book and am stuck on an early excersise in
it, not because of the c programming side of it or even the algorithm
side of it, i don't think, but because of maths. i don't really
understand what is expected, or really what the question means. could
anyone explain what the question's after please?
any help much appreciated.
thanks, ben.

Prove an upper bound on the number of machine instructions required to
process M connections on N objects using the below programme. You may
assume, for example, that any C assignment statement always requires
less than c instructions, for some fixed constant c.

/* p1.3 quickunionweighted.c: a solution to the connectivity problem
with weighted tree */

#include <stdio.h>
#define N 10000

int main(void)
{
int i, j, p, q, id[N], sz[N];

for( i = 0; i < N; i++ )
id[i] = i, sz[i] = 1;

while( scanf("%d %d\n", &p, &q) == 2 ) {

// the FIND operation:
for( i = p; i != id[i]; i = id[i] )
;
for( j = q; j != id[j]; j = id[j] )
;
if( i == j )
continue;

// the UNION operation (inc. weighted tree maintenance):
if( sz[i] < sz[j] ) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}

printf(" %d %d << new connection\n", p, q);
}

return 0;
}
 
Reply With Quote
 
 
 
 
Chris Torek
Guest
Posts: n/a
 
      02-06-2005
In article <060220051856274220%(E-Mail Removed)>, ben <(E-Mail Removed)> wrote:
>i'm following an algorithm book and am stuck on an early excersise in
>it, not because of the c programming side of it or even the algorithm
>side of it, i don't think, but because of maths. i don't really
>understand what is expected, or really what the question means. could
>anyone explain what the question's after please?


>Prove an upper bound on the number of machine instructions required to
>process M connections on N objects using the below programme. You may
>assume, for example, that any C assignment statement always requires
>less than c instructions, for some fixed constant c.


The question is about algorithm time complexity. For instance,
sorting operations are typically O(N log N) or O(N * N), where N
is the number of items being sorted. Roughly speaking, that tells
you how long it takes to sort 10 items, vs 15000, vs a million
(or indeed any other number N).

Suppose the algorithm is "order n-squared", and it takes about a
millisecond to sort 10 items. Then:

10*10 = 100 => 1.00 millisecond
1500*1500 = 2250000 => 22500.00 milliseconds (or 22.5 seconds)
1mil*1mil = 1e12 => 1e12 milliseconds
= 1e9 seconds
= ~11574 days
= ~31.7 years

Hence, sorting a million items with this code is probably not a
good idea.

On the other hand, suppose you find an algorithm that is "order n
log n" (log2, in this case, although it does not matter in big-O
notation because log10 X / log2 X is a constant). Suppose it is
about three times slower for ten items, taking just over 3 milliseconds
(I am doing this to make the math easier). Then:

10 * log2 10 = 33.2 => 3.32 milliseconds
1500 * log2 1500 = 15826.1 => 1582.61 milliseconds (~1.6 seconds)
1mil * log2 1mil = 19931568.6 => 1993156.86 milliseconds
= ~1993 seconds
= ~33.2 minutes

As you can see, an "N log N" algorithm does not bog down nearly as
fast as an "N squared" one -- even if it starts out a little slower,
it is faster once you have a significant number of items to process.

Big-O or "order" notation is useful for deciding how much data you
can stand to process. It completely ignores linear factors, however:
if routine A is O(n log n) and routine B is O(n log n), they have
the same order, but A can still run a million times faster than B
in all cases. So it is not the entire picture, just a very important
part of it.

General algorithm questions (including "is this O(whatever)") mostly
belong in comp.programming.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
 
Reply With Quote
 
 
 
 
ben
Guest
Posts: n/a
 
      02-17-2005
In article <(E-Mail Removed)>, Chris Torek
<(E-Mail Removed)> wrote:
....
....
....
> As you can see, an "N log N" algorithm does not bog down nearly as
> fast as an "N squared" one -- even if it starts out a little slower,
> it is faster once you have a significant number of items to process.
>
> Big-O or "order" notation is useful for deciding how much data you
> can stand to process. It completely ignores linear factors, however:
> if routine A is O(n log n) and routine B is O(n log n), they have
> the same order, but A can still run a million times faster than B
> in all cases. So it is not the entire picture, just a very important
> part of it.



Chris,

sorry for the very long delay in thanking you for your reply. thanks
very much for the answer, it was very helpful. i understood pretty much
all of what you said but i'm still a bit stuck on the details on how to
do the following exercise.

the exercise question is:


Prove an upper bound on the number of machine instructions required to
process M connections on N objects using the below programme. You may
assume, for example, that any C assignment statement always requires
less than c instructions, for some fixed constant c.

/* p1.3 quickunionweighted.c: a solution to the connectivity problem
with weighted tree */
#include <stdio.h>
#define N 10000

int main(void)
{
int i, j, p, q, id[N], sz[N];
for( i = 0; i < N; i++ )
id[i] = i, sz[i] = 1;
while( scanf("%d %d\n", &p, &q) == 2 ) {
// the FIND operation:
for( i = p; i != id[i]; i = id[i] ) ;
for( j = q; j != id[j]; j = id[j] ) ;
if( i == j ) continue;
// the UNION operation (inc. weighted tree maintenance):
if( sz[i] < sz[j] ) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
printf(" %d %d << new connection\n", p, q);
}
return 0;
}



so a formula that tells you the worst, most unlucky as it were, number
of instructions that'd have to be executed in order to complete the
above code (based on the M and N values) is required.

does the following course of action sound correct? taking the first
'for' loop from the FIND operation in the above code and using that as
an example would it go like this?:

each commented number represents how many instructions:

for( i = p; /* 2 - a read and a write */
i != id[i]; i = id[i] ) ; /* 4 * x - that is 2 reads and 2 writes
multiplied by the number of loops */

so say the number of loops was 10. 10*4 + 2 = 42.

then because the question says "You may assume, for example, that any C
assignment statement always requires less than c instructions, for some
fixed constant c." say i pick 5 for that (i'm a bit unsure on what
that quoted sentance means exactly)

so for this bit that 'for' line totals 42 * 5 = 210. so 210 machine
instructions for that 'for' loop being run 10 times.

obviously you'd need to work out how many times the for loop would get
run in the worst case, along with all the other parts of code, and
total all that up.

is that the rough idea of how to proceed to answer the exercise
question?

thanks, ben.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Math.random() and Math.round(Math.random()) and Math.floor(Math.random()*2) VK Javascript 15 05-02-2010 03:43 PM
Math.min and Math.max for byte / short Philipp Java 9 07-23-2008 12:37 AM
math.h trig functions questions (and some forgotten high school math) Mark Healey C Programming 7 05-22-2006 10:42 AM
Re: Is still math.h the C++ math library ? AciD_X C++ 4 04-01-2004 07:29 PM
Why can I not use: Math a=new Math(); chirs Java 18 03-02-2004 06:00 PM



Advertisments