B
ben
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;
}
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;
}