Solution to "One Algorithm Problem"

A

Andrew Tomazos

In follow-up to these two threads:
<http://groups.google.com/group/comp.programming/browse_thread/thread/
f7212303f3789b37>
<http://groups.google.com/group/comp.lang.c/browse_thread/thread/
58b60dda280aaccf>

Here is my C implementation of an O(N) time, O(1) space solution to
the "one algorithm problem" of sorting an unordered array of N records
(A[]) that have unique integer keys in the range 0..(N-1), according
to an array of integers (B[]) that are a permutation of the keys of A.

I would appreciate it if someone could verify that it is correct and
indeed runs in O(N) time.

void assert(int b) { if (!b) while (1) /* hang */; }

struct V {/* satalite data */};

struct R { int key; struct V value; };

void one_algo_prob(struct R* A, const int* B, const int N)
{
int i, j, a0, b0;

for (i = 0; i < N; i++)
if (A.key == 0)
{
A = A[0];
A[0].key = 0;
break;
}

for (i = 1; i < N; i++)
{
while (A.key != i)
{
A[0] = A;
A = A[A[0].key];
A[A[0].key] = A[0];
A[0].key = 0;
}
}

for (i = 0; i < N; i++)
assert(A.key == i);

a0 = 0;

for (i = 0; i < N; i++)
{
if (B == 0)
b0 = i;
}

assert(A[a0].key == 0);
assert(B[b0] == 0);

if (a0 != b0)
{
A[a0] = A[b0];
A[b0].key = 0;
a0 = b0;
}

assert(a0 == b0);

for (i = 0; i < N; i++)
{
j = i;
while (A[j].key != B[j])
{
A[a0] = A[j];
A[j] = A[B[j]];
A[B[j]] = A[a0];
A[a0].key = 0;
j = B[j];
}
}

for (i = 0; i < N; i++)
{
assert(A.key == B);
}
}

int main(int argc, char** argv)
{
struct R A[10];
int B[10];

B[0] = 8;
B[1] = 2;
B[2] = 7;
B[3] = 1;
B[4] = 5;
B[5] = 0;
B[6] = 3;
B[7] = 9;
B[8] = 4;
B[9] = 6;

A[0].key = 5;
A[1].key = 9;
A[2].key = 0;
A[3].key = 8;
A[4].key = 3;
A[5].key = 4;
A[6].key = 6;
A[7].key = 7;
A[8].key = 1;
A[9].key = 2;

one_algo_prob(A,B,10);
}

Regards,
Andrew.
 
D

Doug Miller

In follow-up to these two threads:
<http://groups.google.com/group/comp.programming/browse_thread/thread/
f7212303f3789b37>
<http://groups.google.com/group/comp.lang.c/browse_thread/thread/
58b60dda280aaccf>

Here is my C implementation of an O(N) time, O(1) space solution to
the "one algorithm problem" of sorting an unordered array of N records
(A[]) that have unique integer keys in the range 0..(N-1), according
to an array of integers (B[]) that are a permutation of the keys of A.

I would appreciate it if someone could verify that it is correct and
indeed runs in O(N) time.
Click to expand...

I'm making no comments on correctness. It definitely does *not* run in O(N)
time; both of these loops are O(N^2):
for (i = 1; i < N; i++)
{
while (A.key != i)
{
A[0] = A;
A = A[A[0].key];
A[A[0].key] = A[0];
A[0].key = 0;
}
}
Click to expand...


and
for (i = 0; i < N; i++)
{
j = i;
while (A[j].key != B[j])
{
A[a0] = A[j];
A[j] = A[B[j]];
A[B[j]] = A[a0];
A[a0].key = 0;
j = B[j];
}
}
Click to expand...
 
A

Andrew Tomazos

I'm making no comments on correctness. It definitely does *not* run in O(N)
time; both of these loops are O(N^2):
Click to expand...

Actually that would only be true if the inner loops ran an average of
N times per iteration of the outer loop, which they do not. In fact
they run an average of <1 times.

This can be demonstrated by placing a counter inside the inner loops.
Code and output included below.

The thing to remember is that the inner loop only gets executed if A
is out of place. After a single iteration of the inner loop, one
more A is in place that was not previously. Therefore the inner
loop can run only run a maximum of N times for the *entire* lifespan
of the outer loop. Therefore it runs an average of <1 time per
iteration of the outer loop.

Do you agree?

Thanks,
Andrew.

count_loop_1 = 0;
for (i = 1; i < N; i++)
{
while (A.key != i)
{
A[0] = A;
A = A[A[0].key];
A[A[0].key] = A[0];
A[0].key = 0;
count_loop_1++;
}
}
printf("N = %d, count_loop_1 = %d\n", N, count_loop_1);

count_loop_2 = 0;
for (i = 0; i < N; i++)
{
j = i;
while (A[j].key != B[j])
{
A[a0] = A[j];
A[j] = A[B[j]];
A[B[j]] = A[a0];
A[a0].key = 0;
j = B[j];
count_loop_2++;
}
}
printf("N = %d, count_loop_2 = %d\n", N, count_loop_2);

This prints out:
N = 10, count_loop_1 = 6
N = 10, count_loop_2 = 7
 
D

Doug Miller

I'm making no comments on correctness. It definitely does *not* run in O(= N)
time; both of these loops are O(N^2):
Click to expand...

Actually that would only be true if the inner loops ran an average of
N times per iteration of the outer loop, which they do not. In fact
they run an average of <1 times.

This can be demonstrated by placing a counter inside the inner loops.
Code and output included below.

The thing to remember is that the inner loop only gets executed if A
is out of place. After a single iteration of the inner loop, one
more A is in place that was not previously. Therefore the inner
loop can run only run a maximum of N times for the *entire* lifespan
of the outer loop. Therefore it runs an average of <1 time per
iteration of the outer loop.

Do you agree?
Click to expand...


Yeah, you're right. Missed that point about maximum of N times. Sorry.
Thanks,
Andrew.

count_loop_1 = 0;
for (i = 1; i < N; i++)
{
while (A.key != i)
{
A[0] = A;
A = A[A[0].key];
A[A[0].key] = A[0];
A[0].key = 0;
count_loop_1++;
}
}
printf("N = %d, count_loop_1 = %d\n", N, count_loop_1);

count_loop_2 = 0;
for (i = 0; i < N; i++)
{
j = i;
while (A[j].key != B[j])
{
A[a0] = A[j];
A[j] = A[B[j]];
A[B[j]] = A[a0];
A[a0].key = 0;
j = B[j];
count_loop_2++;
}
}
printf("N = %d, count_loop_2 = %d\n", N, count_loop_2);

This prints out:
N = 10, count_loop_1 = 6
N = 10, count_loop_2 = 7
Click to expand...
 
B

Ben Bacarisse

Richard Heathfield said:
Andrew Tomazos said:
In follow-up to these two threads:
<http://groups.google.com/group/comp.programming/browse_thread/thread/
f7212303f3789b37>
<http://groups.google.com/group/comp.lang.c/browse_thread/thread/
58b60dda280aaccf>

Here is my C implementation of an O(N) time, O(1) space solution
to the "one algorithm problem" of sorting an unordered array of N
records (A[]) that have unique integer keys in the range 0..(N-1),
according to an array of integers (B[]) that are a permutation of
the keys of A.

I would appreciate it if someone could verify that it is correct
and indeed runs in O(N) time.
Click to expand...

Unfortunately, you missed an important condition of the original
specification, to wit: "WITHOUT using any extra variable space".
Click to expand...

I think you miss-understand what the OP meant by "variable" space.
The OP was writing in a foreign language and struggling to say "space
that depends on the problem size". Of course, even this is not exact
enough for a formal analysis (I am sure you remember the Great In
Place Merge Debate a while back) but, informally, in-place means with
only O(1) extra counters and indexes etc.
 
M

mohangupta13

Ben Bacarisse said:





I hope so, for his sake! :)
Click to expand...
Sorry I actually meant that only by 'variable space ' " space that
depends on the problem size ".
Thanks to all. I guess its a great place to hang out with such great
people.
 
A

Andrew Tomazos

This surely counts as extra space.

(And no, I don't see how to do it /without/ extra space.)
Click to expand...

Hehe. What's 16 bytes between friends? And you are forgetting about
the parameters of the function, they take up space on the stack.

The OP means in "constant space" or in "O(1) space".

The point of O(1) is even if N = 1000000, the function still uses just
16 bytes.

If you really couldn't use *any* space where are you planning on
storing the code for the algorithm? :) I suppose you could XOR it
somehow onto the A array, and then JMP A. :)
-Andrew.
 
P

Paul E. Black

I don't think it is correct. It seems to overwrite one value (but not
keys). It appears to use A[0] as temporary storage for swaps and
such, but a single variable of type struct V should suffice.

Here is my C implementation of an O(N) time, O(1) space solution to
the "one algorithm problem" of sorting an unordered array of N records
(A[]) that have unique integer keys in the range 0..(N-1), according
to an array of integers (B[]) that are a permutation of the keys of A.

I would appreciate it if someone could verify that it is correct and
indeed runs in O(N) time.

void assert(int b) { if (!b) while (1) /* hang */; }

struct V {/* satalite data */};

struct R { int key; struct V value; };

void one_algo_prob(struct R* A, const int* B, const int N)
{
int i, j, a0, b0;

for (i = 0; i < N; i++)
if (A.key == 0)
{
A = A[0];
Click to expand...

This line overwrites the value which was in A with the value in
A[0], thus loosing A.value forever.
A[0].key = 0;
break;
}
Click to expand...

-paul-

Below is my modification to Andrew's code. It is intended to track
the values.

// assert macro
// test assertions by compiling with -D RIGOROUS

#include <stdio.h>

#ifdef RIGOROUS
#define ASSERT(ex) {if(!(ex))(void)fprintf(stderr,"%s false in %s, line %d\n",#ex,__FILE__,__LINE__);}
#else
#define ASSERT(ex)
#endif

/*
From: Andrew Tomazos <[email protected]>
Newsgroups: comp.programming,comp.theory,comp.lang.c
Subject: Solution to "One Algorithm Problem"
Date: Mon, 20 Apr 2009 01:28:57 -0700 (PDT)
Organization: http://groups.google.com
Message-ID: <202c9dfa-72fb-4ed0-9565-56642ff98fb7@w40g2000yqd.googlegroups.com>

In follow-up to these two threads:
<http://groups.google.com/group/comp.programming/browse_thread/thread/
f7212303f3789b37>
<http://groups.google.com/group/comp.lang.c/browse_thread/thread/
58b60dda280aaccf>

Here is my C implementation of an O(N) time, O(1) space solution to
the "one algorithm problem" of sorting an unordered array of N records
(A[]) that have unique integer keys in the range 0..(N-1), according
to an array of integers (B[]) that are a permutation of the keys of A.

I would appreciate it if someone could verify that it is correct and
indeed runs in O(N) time.
*/

//-PEB void assert(int b) { if (!b) while (1) /* hang */; }
#define assert(ex) ASSERT(ex) //+PEB

//-PEB struct V {/* satalite data */};
struct V {char *s;}; //+PEB

struct R { int key; struct V value; };

void one_algo_prob(struct R* A, const int* B, const int N)
{
int i, j, a0, b0;

for (i = 0; i < N; i++)
if (A.key == 0)
{
A = A[0];
A[0].key = 0;
break;
}

for (i = 1; i < N; i++)
{
while (A.key != i)
{
A[0] = A;
A = A[A[0].key];
A[A[0].key] = A[0];
A[0].key = 0;
}
}

for (i = 0; i < N; i++)
assert(A.key == i);

a0 = 0;

for (i = 0; i < N; i++)
{
if (B == 0)
b0 = i;
}

assert(A[a0].key == 0);
assert(B[b0] == 0);

if (a0 != b0)
{
A[a0] = A[b0];
A[b0].key = 0;
a0 = b0;
}

assert(a0 == b0);

for (i = 0; i < N; i++)
{
j = i;
while (A[j].key != B[j])
{
A[a0] = A[j];
A[j] = A[B[j]];
A[B[j]] = A[a0];
A[a0].key = 0;
j = B[j];
}
}

for (i = 0; i < N; i++)
{
assert(A.key == B);
(void)printf("A[%d].key is %d value.s is %s\n", i, A.key, A.value.s); //+PEB
}
}

int main(int argc, char** argv)
{
struct R A[10];
int B[10];

B[0] = 8;
B[1] = 2;
B[2] = 7;
B[3] = 1;
B[4] = 5;
B[5] = 0;
B[6] = 3;
B[7] = 9;
B[8] = 4;
B[9] = 6;

A[0].key = 5; A[0].value.s = "five";
A[1].key = 9; A[1].value.s = "nine";
A[2].key = 0; A[2].value.s = "zero";
A[3].key = 8; A[3].value.s = "eight";
A[4].key = 3; A[4].value.s = "three";
A[5].key = 4; A[5].value.s = "four";
A[6].key = 6; A[6].value.s = "six";
A[7].key = 7; A[7].value.s = "seven";
A[8].key = 1; A[8].value.s = "one";
A[9].key = 2; A[9].value.s = "two";

one_algo_prob(A,B,10);
}

/*
Regards,
Andrew.
 
A

Andrew Tomazos

(The crosspost thread got botched up somehow, please excuse
duplication)

I don't think it is correct.  It seems to overwrite one value (but not
keys).  It appears to use A[0] as temporary storage for swaps and
such, but a single variable of type struct V should suffice.
Click to expand...

Yes, this is intentional and part of the original problem (from the
original post). I should have restated that part. The A with key
0 may be used as temporary storage, and doesn't hold any meaningful
data. With this allowance, the algorithm must also be O(1) space with
regard to the size of V. Using an extra variable of type V would make
it O(V) space, and break the requirement.

As you can see from the output of your modifications everything is
correct except the one with key 0...

A[0].key is 8 value.s is eight
A[1].key is 2 value.s is two
A[2].key is 7 value.s is seven
A[3].key is 1 value.s is one
A[4].key is 5 value.s is five
A[5].key is 0 value.s is one <-- temporary/meaningless
A[6].key is 3 value.s is three
A[7].key is 9 value.s is nine
A[8].key is 4 value.s is four
A[9].key is 6 value.s is six

....as intended.

Regards,
Andrew.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Algorithm 1
Adding adressing of IPv6 to program 1
How to multiply two matrices of size in using inline assembly in C++ 2
Problem with codewars. 5
Python code problem 2
Help!! Can anyone provide this solution? 1
Where is my mistake? Why is s equal to minus infinity at some loop iterations? 0
Codeforces problem 0

Members online

No members online now.
Total: 34 (members: 0, guests: 34)
Robots: 471

Forum statistics

Threads
473,769
Messages
2,569,580
Members
45,054
Latest member
TrimKetoBoost

Latest Threads

Top