wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> The Sums of a Set
        
(Message started by: Dudidu on Dec 7^th, 2003, 9:36am)

Title: The Sums of a Set
Post by Dudidu on Dec 7^th, 2003, 9:36am

You are given a set S [subseteq] {1, ..., n}.
Devise an efficient algorithm that outputs all the numbers (x + y) such that x, y [in] S.

Title: Re: The Sums of a Set
Post by Dudidu on Dec 9^th, 2003, 7:12am

Can someone give an answer (even the trivial one) ?
Don't worry about how efficent it is, we'll improve it later... ;)

Title: Re: The Sums of a Set
Post by towr on Dec 9^th, 2003, 8:08am

on 12/09/03 at 07:12:06, Dudidu wrote:

Can someone give an answer (even the trivial one) ?

like
f(S) = {x+y [in] S | (x,y) [in] S[times]S} ?

hmm.. on second thought I don't think I actually know a language that'll pass it (PVS comes close, though it's not so much a programming language as a theorem prover)

Prolog should be simple enough as well though (and reads much the same):

f(S, R):-setof(T, X^Y^(member(X,S), member(Y,S), T is X+Y, member(T,S)), R).

%% in case member isn't predefined
member(E, [E|_]).
member(E, [_|T]):-member(E, T).

Title: Re: The Sums of a Set
Post by Dudidu on Dec 10^th, 2003, 12:17am

If you didn't understand, you can think of the set S as an array of size m (so getting the elements is as simple as addressing some element in the array).
Now, its seems (to me ::)) that its quite easy to give a pseudo-code for the trivial answer.

Title: Re: The Sums of a Set
Post by towr on Dec 10^th, 2003, 12:54am

my answer isn't trivial enough?

Title: Re: The Sums of a Set
Post by tsewen on Dec 10^th, 2003, 1:33am

for (int i = 2; i <= 2n; i++)
cout << i << " ";

Title: Re: The Sums of a Set
Post by Dudidu on Dec 10^th, 2003, 3:09am

on 12/10/03 at 00:54:42, towr wrote:

my answer isn't trivial enough?

No, firstly since I don't know Prolog and secondly (the more problematic issue) since I don't know how f(S, R) is practically calculated and thus, I don't know what is its time complexity.
Sorry... ???
P.S. - towr, just to be sure does 'member(T,S)' mean that T is a member of S (since if it is, I think that the definition of 'f(S, R)' is incorrect (?:-/?).

Quote:

for (int i = 2; i <= 2n; i++)
cout << i << " ";

Tom Wang, welcome to the forum :D.
What did you mean by this loop ?

Title: Re: The Sums of a Set
Post by Tom Wang on Dec 10^th, 2003, 3:54am

The program is supposed to output all the numbers z = x + y such that x and y are members of S, given the number n.

Title: Re: The Sums of a Set
Post by Tom Wang on Dec 10^th, 2003, 3:58am

I was confused by the question; I thought S was the set from 1 to n.

Title: Re: The Sums of a Set
Post by towr on Dec 10^th, 2003, 4:21am

on 12/10/03 at 03:09:08, Dudidu wrote:

No, firstly since I don't know Prolog and secondly (the more problematic issue) since I don't know how f(S, R) is practically calculated and thus, I don't know what is its time complexity.

it should be quadratic

Quote:

Sorry... ???

I guess I just know too many languages.. And it's so tempting to solve problems in the language that solves them the easiest.

Quote:

P.S. - towr, just to be sure does 'member(T,S)' mean that T is a member of S (since if it is, I think that the definition of 'f(S, R)' is incorrect (?:-/?).

Yes that is what it means.
I thought you wanted the sum to be in S.. Apparantly I also misread the problem.. But you can easily remove it..

Title: Re: The Sums of a Set
Post by Dudidu on Dec 10^th, 2003, 9:44am

on 12/10/03 at 03:58:40, Tom Wang wrote:

I was confused by the question; I thought S was the set from 1 to n.

Don't be discouraged, everybody makes mistakes (sometimes)... keep on trying !

on 12/10/03 at 04:21:01, towr wrote:

it should be quadratic...

I tought so.

Quote:

I thought you wanted the sum to be in S.. Apparantly I also misread the problem.. But you can easily remove it...

You're right, it is not necessary that the sum will be in S.

Now, the question is how can you improve it (a hint will follow soon (if no one gets it before)...)

Title: Re: The Sums of a Set
Post by Barukh on Dec 10^th, 2003, 11:56am

Here’s a more conventional code that will be easier to discuss the improvements on (at least for me ::)):

Code:

for (sum = 2*S[1]; sum <= 2*S[m]; sum++)
{
for (i = 1; (i <= m) && (S[i] <= sum/2); i++)
{
if ( inS(sum – S[i]) ) { print( sum ); break; }
}
}

The S[] is the array Dudidu talked about in his other mail; inS() is a membership check. The complexity of this code is O(N*m), which is quadratic in N in the worst case.

One way to improve this code would be to start the inner loop not at 1, but at index k such that sum - S[k] [le] N. However, this doesn’t imrpove the complexity.

Title: Re: The Sums of a Set
Post by James Fingas on Dec 10^th, 2003, 1:32pm

You didn't happen to get the idea for this question from another thread, did you?

I was going to post a link, but I didn't want to give away the answer...

Title: Re: The Sums of a Set
Post by Barukh on Dec 10^th, 2003, 2:49pm

on 12/10/03 at 13:32:31, James Fingas wrote:

You didn't happen to get the idea for this question from another thread, did you?

Personally, I haven't made any connection to any existing threads... Thus, the code is as poor as it is.

Title: Re: The Sums of a Set
Post by Dudidu on Dec 11^th, 2003, 4:07am

on 12/10/03 at 11:56:06, Barukh wrote:

Here’s a more conventional code that will be easier to discuss the improvements on (at least for me ::)):...

Barukh hi,
I have some comments/questions about your code:

Quote:

inS() is a membership check...

1) How does it implemented ? - since if it is implemented as a naive search (i.e. looking for that element in S) then it will take O(m²N) and not O(mN)...

Quote:

quadratic in N in the worst case...

2) How can you improve it to be O(m²) (assuming that you fixed the inS() problem/feature ;))?

3) One remark: you assume that the array S is sorted (which isn't a must) - but this doesn't create a problem (since sorting it would take O(m) ?!).
Waiting for your reply...

Title: Re: The Sums of a Set
Post by James Fingas on Dec 11^th, 2003, 4:38am

on 12/10/03 at 14:49:22, Barukh wrote:

Personally, I haven't made any connection to any existing threads... Thus, the code is as poor as it is.

I was actually asking Dudidu about the original question. Your code seems fairly straightforward, although there are probably some easier ways to do it.

Title: Re: The Sums of a Set
Post by Dudidu on Dec 11^th, 2003, 6:02am

on 12/11/03 at 04:38:13, James Fingas wrote:

I was actually asking Dudidu about the original question...

James hi,
I didn't get the idea for this question from another thread.
But if there is a similar thread and I'm recycling problems, I'm sorry...

P.S. - can you send me the link to the other thread (or post it (after this riddle is solved)) ?

Title: Re: The Sums of a Set
Post by James Fingas on Dec 11^th, 2003, 6:09am

I guess I'm the only one who sees the similarity. The solution I'm thinking of works in O(n log n). Of course, that's not great if m << n, but pretty cool nonetheless.

Title: Re: The Sums of a Set
Post by Barukh on Dec 11^th, 2003, 1:11pm

on 12/11/03 at 04:07:44, Dudidu wrote:

1) How does it implemented ? - since if it is implemented as a naive search (i.e. looking for that element in S) then it will take O(m²N) and not O(mN)...

Since there were no restrictions on the space, the simplest way is to have a boolean array inS[] - it takes O(N) to build it. Or, even better, use a hash.

Quote:

2) How can you improve it to be O(m²) (assuming that you fixed the inS() problem/feature ;))?

I wish I knew... :-/

Title: Re: The Sums of a Set
Post by TenaliRaman on Dec 11^th, 2003, 10:43pm

One thing i don't get in the question,
given any set S with #S=m one can easily find a O(m²) solution.(its just a matter of two loops)

I thought that the knowlege that S is a subset of {1,..,n} would help the case. I came up with O(n*m²log(m)) which hardly seems any better.And my friend seems to suggest that S is a subset of {1,..,n} can hardly ever make the algo efficient because he feels it makes the search space that much bigger.

Title: Re: The Sums of a Set
Post by James Fingas on Dec 12^th, 2003, 6:02am

The trivial answer that is O(m[sup2]) is this one (pseudocode):

input array s of length m
result list Z = empty list

for i = 1 to m {
for j = i+1 to m {
Z.add( s[i] + s[j] )
}
}

This of course has duplicate entries, but if we don't care, it's a trivial O(m[sup2]) answer. I haven't yet thought of a method faster than O(m[sup2]logm) (sort them) to remove the duplicates, so that appears to be the limiting performance factor. So here is a listing of the best times so far:

my interesting solution: O(n log n)
Barukh's solution: O(mn)
my trivial solution: O(m[sup2] log m)

Which of these is best will depend on the relative sizes of m and n. My guess is that an answer running in O(m[sup2]) is possible.

Title: Re: The Sums of a Set
Post by TenaliRaman on Dec 12^th, 2003, 8:35am

hmm on "re-analysis" it seems the method i came up with is O(nmlogm) so it maybe relevant after all.

the procedure is as follows,
Given,
N = {1,...,n}
S subset of N and #S=m

Generate a set A = {2,....,2n}
(Note:this set has all the possible (x+y)'s for x,y belong to N.)
Sort S which is m*logm
Let S' be the set with all the (x+y)'s for x,y belong to S.
int k=0;
for(i=0;i<2n-1;i++)
{
....for(j=0;j<m;j++)
....{
.........if(A[i]>S[j] && A[i]-S[j] is in S)
..............S'[k++] = A[i];
....}
}
the A[i]-S[j] is in S can be done using a binary search algorithm which is O(logm).

So the overall is O(nmlogm)

Title: Re: The Sums of a Set
Post by James Fingas on Dec 12^th, 2003, 2:34pm

Another way to implement the inS function is just to make an array L (for lookup) that is N long, full of zeros, then do this:

for i = 1 to m {
L[ s[i] ] = 1
}

The inS(j) is L[j], with constant time.

And if you want indentation to work properly, post with indentation screwed up, then modify and resave your post (which fixes indentation).

Title: Re: The Sums of a Set
Post by TenaliRaman on Dec 13^th, 2003, 6:57am

Thanks for that tip off James, that would improve my algo's efficiency to O(mn).

I just realised that my implementation is same as that of Barukh's, the only thing being Barukh has better efficiency since my average efficiency will be always O(mn) and Barukh's average efficiency will be < O(mn).

I think after looking at different directions for better algo i think i would rather vote for the simple O(m²) solution.

Title: Re: The Sums of a Set
Post by Dudidu on Dec 14^th, 2003, 1:04am

Everybody hi,

Quote:

The trivial answer that is O(m²) is this one...

James hi,
This is the algorithm that I asked Barukh about. As you indicated it doesn't remove duplicates so... a trivial algorithm would do it (output the desired numbers and remove the duplicates) in an O(m² + N) (or some may say O(max{ m²,N})) time complexity (which is better then O(mN)) - what is it ?

Nevertheless, I see that you all are fixed on the ~m² time complexity area so try to improve it... (Big Hint:[hide] How polynomials can be used ?[/hide]).

Title: Re: The Sums of a Set
Post by Eigenray on Dec 14^th, 2003, 5:12am

Ahhh...[hide]
Let f(x) = [sum]_{s in S} x^s, and compute f²(x) = [sum]_k=2²ⁿ b_kx^k with FFT in O(nlog n) time. Then simply read off { k | b_k != 0 }[/hide].

Title: Re: The Sums of a Set
Post by Barukh on Dec 15^th, 2003, 7:13am

on 12/12/03 at 06:02:55, James Fingas wrote:

So here is a listing of the best times so far:

my interesting solution: O(n log n)
Barukh's solution: O(mn)
my trivial solution: O(m[sup2] log m)

Which of these is best will depend on the relative sizes of m and n. My guess is that an answer running in O(m[sup2]) is possible.

I would like to add that the O(m²) solution may be preferable also in case n - m << n: just compute the numbers in the range [2...2n] that are not in the output.

on 12/14/03 at 05:12:38, Eigenray wrote:

Ahhh...

Perfect! If this is what James had in mind for his O(n log n) solution, than the connection with another thread is clear.

Very nice problem, Dudidu! :D

Title: Re: The Sums of a Set
Post by James Fingas on Dec 15^th, 2003, 7:57am

on 12/15/03 at 07:13:48, Barukh wrote:

I would like to add that the O(m²) solution may be preferable also in case n - m << n: just compute the numbers in the range [2...2n] that are not in the output.

I don't see how this is particularly easy ... a number x is in the set if an integer i can be found so that i and x-i are both in S. The number x is not in the set if no such integer i can be found. At first I envisioned generating the complement to S, but this doesn't help you find which x are not in the result.

Quote:

Perfect! If this is what James had in mind for his O(n log n) solution, than the connection with another thread is clear.

That is exactly what I was thinking of, but a general O(m[sup2]) solution still seems to be lacking. The trivial way to get rid of duplications in O(m[sup2] + n) time is to put the resulting numbers in an array then read out which positions in the array are filled.

I think I see how to eliminate the need to search through the array (which is the part that takes O(n) time). Do the following:

input array s (size m)
array R (holds resulting numbers, size n)
list L (lists places in the array that have been used)

for i = 1 to m {
for j = i+1 to m {
L.add( s[i] + s[j] )
R[ s[i] + s[j] ] = 1
}
}

#now print out the resulting numbers. The are m(m-1)/2 list entries.

while L.count > 0 {
if R[ L.first ] > 0 {
R[ L.first ] = 0
print L.first
}
L.removeFirst
}

This way you only look through the numbers you generated, and you only print out one copy of each, all in O(m[sup2]) time, using O(n + m[sup2]) memory.

Title: Re: The Sums of a Set
Post by TenaliRaman on Dec 16^th, 2003, 12:00am

James,
one can slightly improve upon your code,

let the R's be filled with zeroes.
for i = 1 to m
{
for j = i+1 to m
{
if(R[s[i]+s[j] != 1)
{
output s[i] + s[j]
R[ s[i] + s[j] ] = 1
}
}
}

Title: Re: The Sums of a Set
Post by James Fingas on Dec 16^th, 2003, 6:35am

Very good. That's probably the best we'll be able to do.

Title: Re: The Sums of a Set
Post by Dudidu on Dec 16^th, 2003, 6:40am

Everybody hi,
You got it all ! Bravo ! ;D

Quote:

You didn't happen to get the idea for this question from another thread, did you?

James, now (I think) I understand why you asked my that question (you already known the answer when you wrote it...).

Title: Re: The Sums of a Set
Post by Barukh on Dec 16^th, 2003, 11:15pm

on 12/15/03 at 07:57:26, James Fingas wrote:

I don't see how this is particularly easy ... a number x is in the set if an integer i can be found so that i and x-i are both in S. The number x is not in the set if no such integer i can be found.

Let me elaborate on this. What got me to think about this was the following simple observation: if |S| = n (i.e. S contains every number in the range [1..n]), then the result may be printed immediately, without any computation. Is this something we can use if just a few elements are missing in S?

Let W(s) be the number of ways in which s [le] 2n may be written as a sum of two natural numbers [le] n. It is obvious that for s [le] n, W(s) = W(2(n+1)-s) = [smiley=lfloor.gif] s/2[smiley=rfloor.gif], so it is available at the start. Now, if m’ = n – m << n, just do the following:
1. For every x [notin] S, decrement W(x+y) for every y.
2. Output every s for which W(s) > 0.

Example: let S = {1,…,n} \ {1, n-1}. Because W(2) = W(3) = W(2n-1) = 1, the first step of the above procedure will eliminate these three numbers, and all others will be printed. This way we have complexity O(nm’), that may be better than O(n log n).

This procedure may be further improved by observing that it is sufficient to look only at numbers s, for which W(s) [le] m’. This reduces the complexity to O(m’² + n).

P.S. Does it make any sense? I've just returned from my trip to the US, being under the effect of jet leg. :o

Title: Re: The Sums of a Set
Post by James Fingas on Dec 17^th, 2003, 5:06am

Barukh,

That looks like it would work. That'll teach me to be skeptical!