math question in c algorithm book help please

Discussion in 'C Programming' started by ben, Feb 6, 2005.

  1. ben

    ben Guest

    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, sz = 1;

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

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

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

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

    return 0;
    }
    ben, Feb 6, 2005
    #1
    1. Advertising

  2. ben

    Chris Torek Guest

    In article <060220051856274220%>, ben <> 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 (40°39.22'N, 111°50.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.
    Chris Torek, Feb 6, 2005
    #2
    1. Advertising

  3. ben

    ben Guest

    In article <>, Chris Torek
    <> 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, sz = 1;
    while( scanf("%d %d\n", &p, &q) == 2 ) {
    // the FIND operation:
    for( i = p; i != id; i = id ) ;
    for( j = q; j != id[j]; j = id[j] ) ;
    if( i == j ) continue;
    // the UNION operation (inc. weighted tree maintenance):
    if( sz < sz[j] ) {
    id = j;
    sz[j] += sz;
    } else {
    id[j] = i;
    sz += 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 = id ) ; /* 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.
    ben, Feb 17, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. chirs
    Replies:
    18
    Views:
    743
    Chris Uppal
    Mar 2, 2004
  2. KK
    Replies:
    2
    Views:
    510
    Big Brian
    Oct 14, 2003
  3. AciD_X
    Replies:
    4
    Views:
    8,069
    Jonathan Turkanis
    Apr 1, 2004
  4. Mark Healey
    Replies:
    7
    Views:
    1,451
    Tim Prince
    May 22, 2006
  5. VK
    Replies:
    15
    Views:
    1,110
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page