Science and Technology news... :: View topic - Minimum sub-sequence sum

Michael Jarrod · Guest

Hello,

I have a sequence of integers (positive/negative values) and I would
like to find the sub sequence of consecutive values that yields the
smallest sum, I can think of a very simple O(n^3) complex solution,
however I was wondering are there any better solutions? and what is
the name of this kind of problem?

-Mich

David Wagner · Guest

Michael Jarrod wrote:
[quote]I have a sequence of integers (positive/negative values) and I would
like to find the sub sequence of consecutive values that yields the
smallest sum, I can think of a very simple O(n^3) complex solution,
however I was wondering are there any better solutions?
[/quote]
Yes, there are better algorithms. This is a classic homework problem
in algorithms. Are you taking an algorithms course? Is this is a
homework problem?

Rather than telling you the answer, I will let you have the experience
of finding the algorithm yourself -- algorithms is an area that is best
learnt by solving algorithm design problems yourself rather than just
looking up the solution at the back of the book. (While the process of
searching for a better algorithm yourself can be frustrating and painful,
it>s the best way I know to learn the subject.)

You should find it very easy to design a O(n^2) algorithm. But can
you do even better?

If you>re stuck, here are some warmup problems to consider that may help.
Suppose you wanted to find the prefix of your sequence that yields the
smallest sum. In other words, this is a variant of your problem where
we only consider consecutive subsequences that include the start of the
original sequence (i.e., we look for a value i such that the sum of the
elements at indices 0,1,..,i gives the smallest possible sum). How fast
could you do it? What about another variant where you are given the
original sequence and also a number j, and want to find the value i such
that the sum of the elements at indices 0,1,..,i is minimized? How fast
can you do it? Suppose you wanted to compute the solution to the latter
problem for every value of j (so that the output of your algorithm is
N answers, one for each possible value of j)? How fast can you do that?

Michael Jarrod · Guest

Hi David,

On Jul 21, 8:49 pm, d...@taverner.cs.berkeley.edu (David Wagner)
wrote:
[quote]Yes, there are better algorithms. This is a classic homework problem
in algorithms. Are you taking an algorithms course? Is this is a
homework problem?

Rather than telling you the answer, I will let you have the experience
of finding the algorithm yourself -- algorithms is an area that is best
learnt by solving algorithm design problems yourself rather than just
looking up the solution at the back of the book. (While the process of
searching for a better algorithm yourself can be frustrating and painful,
it>s the best way I know to learn the subject.)

[/quote]
Its not a homework problem but rather an interview question I
encountered a few months ago, I take your point that investigating it
on my own would be far more beneficial.

[quote]You should find it very easy to design a O(n^2) algorithm. But can
you do even better?

[/quote]
I hope I can! :)

[quote]If you>re stuck, here are some warmup problems to consider that may help.
Suppose you wanted to find the prefix of your sequence that yields the
smallest sum. In other words, this is a variant of your problem where
we only consider consecutive subsequences that include the start of the
original sequence (i.e., we look for a value i such that the sum of the
elements at indices 0,1,..,i gives the smallest possible sum). How fast
could you do it? What about another variant where you are given the
original sequence and also a number j, and want to find the value i such
that the sum of the elements at indices 0,1,..,i is minimized? How fast
can you do it? Suppose you wanted to compute the solution to the latter
problem for every value of j (so that the output of your algorithm is
N answers, one for each possible value of j)? How fast can you do that?
[/quote]
I can see how these two simpler problems would be solved using an
O(n^2) complex algorithm, I am going to consider using a DP style
approach, and somehow remember sums for specific ranges.

Thanks for the insight, I>ll post back if I have anymore difficulties

-Mich

Mark T.B. Carroll · Guest

Michael Jarrod <Michael.Jarrod@gmail.com> writes:

[quote]I have a sequence of integers (positive/negative values) and I would
like to find the sub sequence of consecutive values that yields the
smallest sum, I can think of a very simple O(n^3) complex solution,
however I was wondering are there any better solutions? and what is
the name of this kind of problem?
[/quote]
Your O(n^3) gets another n from each of:

1. Try different positions for the start of the subsequence
2. Try different positions for the end of the subsequence
3. Calculating the sum of a subsequence

to make the O(n^3)?

Mark

Guest · Posted: Wed Jul 23, 2008 7:22 am Post subject: Re: Minimum sub-sequence sum

On Jul 21, 8:13 pm, Michael Jarrod <Michael.Jar...@gmail.com> wrote:
[quote]Hello,

I have a sequence of integers (positive/negative values) and I would
like to find the sub sequence of consecutive values that yields the
smallest sum, I can think of a very simple O(n^3) complex solution,
however I was wondering are there any better solutions? and what is
the name of this kind of problem?

-Mich
[/quote]
Jon Bentley uses a problem like this in one of his Programming Pearls
columns. There are
subquadratic algorithms as well as two quadratic algorithms he
considers. You might try a
divide-and-conquer approach and also a tail-recursive (read: clever
iterative) approach to get
a subquadratic runtime. Surprisingly, the quickest solution needs
little memoization if any.

If you can>t come up with it on your own (or even if you can), check
out the collections (two
that I know) of Programming Pearls by the above author.

Gerhard Paseman, 2008.07.23

Bryan Olson · Guest

grpadmin@gmail.com wrote:
[quote]Michael Jarrod wrote:
I have a sequence of integers (positive/negative values) and I would
like to find the sub sequence of consecutive values that yields the
smallest sum, I can think of a very simple O(n^3) complex solution,
however I was wondering are there any better solutions? and what is
the name of this kind of problem?

Jon Bentley uses a problem like this in one of his Programming Pearls
columns. There are
subquadratic algorithms as well as two quadratic algorithms he
considers. You might try a
divide-and-conquer approach and also a tail-recursive (read: clever
iterative) approach to get
a subquadratic runtime. Surprisingly, the quickest solution needs
little memoization if any.

If you can>t come up with it on your own (or even if you can), check
out the collections (two
that I know) of Programming Pearls by the above author.
[/quote]
It>s in the first collection, /Programming Pearls/. First edition 1986,
second 2000.

http://www.amazon.com/Programming-Pearls-2nd-ACM-Press/dp/0201657880

--
--Bryan

Guest · Posted: Fri Jul 25, 2008 8:56 pm Post subject: Re: Minimum sub-sequence sum

On Jul 21, 11:13 pm, Michael Jarrod <Michael.Jar...@gmail.com> wrote:
[quote]Hello,

I have a sequence of integers (positive/negative values) and I would
like to find the sub sequence of consecutive values that yields the
smallest sum, I can think of a very simple O(n^3) complex solution,
however I was wondering are there any better solutions? and what is
the name of this kind of problem?

-Mich
[/quote]
Do you means a subsequence of values at consecutive indexes, or a
subsequence of values that are consecutive integers?


www.GetXFactor.com Leading Technology, Science, Agriculture News and information	Part of the Identityscape.com network... getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

Science and Technology news... Forum Index -> Cryptography Forum
Page 1 of 1