Re: some guide

Timo Schneider wrote:
On 2007-02-05, shokoohcpp@xxxxxxxxxxxxxx <shokoohcpp@xxxxxxxxxxxxxx> wrote:


describe a theta (nlog n)-time algorithm that give a set of S of n
and another integer x determine wether or not there exit two elements
in s whose sum is exactly x

That sounds easy. But please keep in mind it is three o'clock in the
morning in my country, so I might be wrong.

I assume that all integers in S are positive.

1.) Sort the n elements in S with a n*log(n) sort algorithm.

Steps 2..6 seem needlessly complicated.
Let jj be the subscript of the lowest element in the sorted array.
Let kk be the subscript of the highest element.
while (jj<kk) {
if (aa[jj]+aa[kk]>x) {
} else if (aa[jj]+aa[kk]<x) {
} else {
if (jj>=kk) {
} else {
print(aa[jj] || '+' || aa[kk] || '=' x);

2.) Throw away everything larger than x, it's of no use.

3.) Divide the list of step 2.) in two parts:
S_1 = [0 .. x/2]
S_2 = [(x/2)+1 .. x]

Now we can look at the problem from a different angle:
Is there an s_1 \in S_1 and an s_2 \in S_2 so that s_1 + s_2 =
x? Because it can't be two elements of S_1 or S_2 that equal x,
because the sum of two members of S_1 is always smaller than x,
the sum of two members of S_2 is always bigger than x.

4.) Now we do the same thing again:
S_1 = [0 .. x/4]
S_2 = [(x/4)+1 .. x/2]
S_3 = [(x/2)+1 .. 3x/4]
S_4 = [(3x/4)+1 .. x]

Now we only have to compare the elements in S_1 two those in S_3 and
S_2 to those in S_4, this is the same problem as in Step 3.) but the
problem size is only half as big.

5.) So we get T(n) = 2*T(n/2) + c if n > 1
= 1 if n = 1
That should be O(n).

6.) O(n*log(n)) + O(n) \in O(n*log(n))

An alternative solution would be to construct some sort of lookup table
so that we can check if x_1 \in S in O(1). Then we iterate over the S
and check if x - s_i is \in S. That would be O(n).

--Mike Amling

Relevant Pages

  • Re: Sort-of a sorting problem
    ... Sort these into a list with proper outline format: ... I need to find a way to sum each lower level into a successive level (ie ... >summarixe all iinto up to the top level. ... standard aggegate functions will do this in each level's ...
  • Re: Precision issue?
    ... >>you may want to look into some sort of compensated summation algorithm. ... > implementation of SUM is in Fortran compilers. ... the sorting of data to improve some summation algorithms was pretty much what I ...
  • Re: Use index and match function to get data from pivot table
    ... If you can sort the names, you should be able to use 'Subtotals' found on the Data menu. ... There are 1000 students in file. ... "Sum of % of bad performance ...
  • Re: trying to sum a group of records but "sum" missing from Group, Sort, and Total dropdown/wizard
    ... I could then see that "sum" was unghosted and available to me. ... I could then also create groups using the group & sort wizards and get ... Format changes number type to string type. ... Totals tab I can Group my records by the "productiondate" field then ...
  • Re: Sort-of a sorting problem
    ... I setup 5 integer fields. ... This makes it easy for sort and grouping ... Each of the lower level tasks is an aggregate sum already involving several tables, subcalculation for each record, and summation of that sum. ... Separate fields could be used for each heirarchy level, but this will be extremely tedious. ...