Thursday, August 4, 2011

Maximum Subsequence

6 interns sat in front of their laptops with enthusiasm flashing on their faces brighter than the laptop light.And why not,it was the first day of their internship & they were eager to start off.Their wait ended after their professor entered & without wasting a single moment,gave them a problem to solve.He called it the maximum sub sequence problem.It sounded trivial enough.

Given a sequence of numbers in a array can you find a continuous sequence of numbers such that they give you the maximum sum?If all the numbers are positive then the max subsequence would be the whole array.problem is when we encounter negative numbers.Completing the problem statement,if all the numbers turn out to be neg then the max sub sequence sum would be taken as zero.
If you are still not clear about the problem.It is equivalent to placing two sticks in the array in such a position that the sum between them is the highest compared to any other positions.
Within no time they had an algorithm ready.The only thing in their mind was to solve it as quickly as possible and never really gave any thought about bettering the algorithm.
Again the brute force came to their rescue.Simply do it for all positions and one with the highest sum would be the answer.Turns out the complexity was quadratic.Well atleast the problem was solved.
But the professor was adamant that the problem could be tacked in linear time.
Yup thats the professor!:)
How can it be said there can be linear time algorithm for this?
The awesome proof follows.Forget about the algorithms for a while and think this way.
Say there is an oracle which gives you the answer for array of numbers given.But there's a problem.It takes only $n-1$ inputs.Oops but we have $n$ numbers in the array.But think for a while,there has to be a way in which it can be used.
I'll just give the oracle the whole array except for the last element and the oracle returns with the answer for the $n-1$ elements.Now we have two numbers in hand.One is the last element which was left out and the other is the max subsequence sum for $n-1$ elements.Can we with these two components infer the actual max sub sequence sum of the whole array?And guess what yes we can!
There are just two scenarios
1.The last element is negative-This is the easiest one.In this whatever the oracle gave becomes the final answer
2.The last element is positive-Two cases arrive here
  1. The max subsequence given by the oracle includes the $n-1$th element-In this case since the last no is positive we include the last $n$th element too to the max subsequence and arrive at the final answer
  2. The max subsequence does not include the last $n-1$ element.This is the most tricky one.In this we never know,the max subsequence might be vry different and the one with the $n$th element.So what we can do is just find the max sub sequence including the last element($n$th).In simpler words what can be the maximum sum you can obtain fixing one position at the end.Compare this with the sub sequence sum given by the oracle.Which ever is greater will fetch us the answer.
So the oracle is making our task very easy.But you may wonder where is this discussion heading.How do u think the oracle will solve the problem?Dont you think the oracle having $n-1$ elements can further give all elements except one to another oracle.
Doesnt this thought trigger something?Its nothing but the decrease and conquer told differently!and as you can see this is done in linear time.
Interestingly this problem has a history too.It first arose in two dimensional form and inorder to simplify it was converted in one dimentional form.First a cubic algol was formulated after which a quadratic and a logarithmic time followed.The best part was the linear algol was designed in less than a minute by a person who attended a seminar where this problem was told about.

How does it really matter?
You may always say that my computer is very fast and so it doesnt really matter.ok whats the harm in comparing anyway.Lets say a computer is as fast as 10GHz. That is nothing but it can perform$10^{10}$ steps in one second.

$N$ $N^{2}$
$10$ $100$
$100$ 10000
$1000$ $10^{6}$
$10000$ $10^{8}$
$10^{5}$ $10^{10}$
$10^{9}$ $10^{18}$

Lets calculate the time for the last instance.
Time taken by the linear one would be=$10^{9}/10^{10}$=0.1seconds
Time taken by the quadratic one would be=$10^{18}/10^{10}$=$10^{8}$seconds
Converting that into years it would approximately 3.5yrs!!!!!!
You see what difference it makes.One takes less than a second to solve the problem whereas the other takes years.And this is just between linear and quadratic.Imagine the scenario for the cubic and the further ones.
Of course it is inavitable to use those when u cant find a linear time algol or when there is no such algol.But effort has to made to reduce the complexity and one way of bettering would be using the apporopriate algorithm design techniques.
"Science is what we understand well enough to explain it to a computer".The technology may advance even more tomorrow and there will be new programming languages formed,but independent of all this the essence of algorithms will always be the same.Thats what makes it the most important part computer science.Dijkstra was right when he said "Computer Science is no more about computers than astronomy is about telescope".
What do you think is the real foundation of computer science?:)

So what happened to our 6 friends?Well they had their best beginning and continued on what became the amazing 2 months of their learning experience.
Moral of the story-Between a fast computer and a fast algorithm always go for the latter.you know why :):)

Nikitha Shenoy

15 comments:

  1. Thank God, the faces are not seen in the photos :P Absolutely brilliant work and amazing job.From quadratic to linear complexity!! The oracle method looks so simple but is so important.Comparing the complexity difference with example and which turns out to be years in one and seconds in the other is fantastic!!Awesomly done and ya we will choose a fast algorithm over a fast computer!! After all this is "algorithinking"!!

    ReplyDelete
  2. Beautiful explanation by going with the flow.
    "The only thing in their mind was to solve it as quickly as possible and never really gave any thought about bettering the algorithm.". I completely agree with you there. Makes me wonder... why wont most of us even attempt find a better solution than the existing one? Laziness? Carelessness? I dont know.

    Here is the reason as to why we were able to reduce a brute force quadratic time algorithm to a linear time algorithm. The brute force algorithm used to check for all the possible subsequence sums. It then returned the one with the maximum sum. But wait.. Something is going terribly wrong here. You are performing a whole lot (I repeat, a whole lot!) of redundant and repetative additions. This observations hints us about the existence of a better algorithm. It sort of gives us an abstract picture on the technique of removal/reducing of those repetative additions as well. And this is exactly what the oracle does.

    Just one doubt haunts me: Is this a divide and conquer algorithm or a decrease and conquer algorithm? I'd go with the latter :P

    ReplyDelete
  3. Maximum sub-sequence problem oh waaaaw. The way question is posed explaining the worst case and best case method clearly. which makes the reader v clear about the problem.by the way that 1st photo was not taken on the day we solved the problem (:P).

    Answer telling machine Oracle is introduced in the rite context.Oracle is nothing but a recursive function call of n-1 elements as input from a array of n elements would be a prefect explanation for a computer scientist.

    I think the Oracle algorithm design technique is decrease by one and conquer.Explanation for importance of v need of reducing the complexity rather then just simply getting a solution to a problem is demonstrated clearly in the table.
    Moral of the algorithmic story is a perfect way to end.
    well done. :)

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. Superb starting of 'real tool of computer science"..:):)
    Describing the scenario and slowly introducing the maximum subsequence problem in it-interesting..:)..placing a stick between the array such that their sum is max says it all..gud idea ..:)
    Working of oracle nicely shown[i remember u teaching me ;)]..luvd the part where u showed the time taken for quadratic complexity..an eye brow raiser..:)
    Nice quotes towards the end..:)Moral of the story-well taken..:):)great job...:)

    ReplyDelete
  6. Hey very nice post I must say. I initially hadnt understood this topic when I read through the book. But now you have made it easier and I could understand very well.

    "Dont bother whether it is the answer.Just by fixing one position to the last element fix the other position such that it gives max sum.Compare this with the subsequence sum given by the oracle.Which ever is greater will fetch us the answer."................................. I had to read through this several times before I understood what you wanted to convey. It is not very clear.

    "Dont you think the oracle can just give all the elements except one to say another oracle and this recursively continues.".................... I didnt get you here.

    Its nice to see that you have such a great opportunity to learn from Sudarshan. He is a powerhouse of knowledge. Make the best use of your time with him. :)

    ReplyDelete
  7. @vijesh-Thanks a lot for your inputs.will see where they can be incorporated:)
    @vijay-yeah it would be decrease by one to be more precise:)
    @shruti & shobitha-thanks:)

    ReplyDelete
  8. @apoorva-hey really appreciate your inputs:)working on the parts you told that weren't clear.
    and yeah it has indeed been our pleasure to learn from sudarshan.making the best out of it :)

    ReplyDelete
  9. i second apoorva... the problem statement could have been simpler for first time readers...

    I would have loved to see some pictures of sticks... to illustrate the problem statement :D

    Illustration on emphasizing more on fast Algorithm ... was very impressive

    ending amazingly simple n cool :D

    ReplyDelete
  10. To begin with its a very good problem....
    I feel that the problem could have been introduced in a better manner....
    the point where u shift from from brute force to decrease and conquer is a bit tricky to understand....
    Needs more than one reading to get the concepts right...

    ReplyDelete
  11. problem was very nice...
    your confidence in your students is very heartwarming.

    and i certainly agree partly with biligiri...intro could have been done in a more budding comp.sci. engineer-friendly way....

    as for the grasping of concepts...it took me two good readings to get it right...latter part was good.

    ARE you a cormen fan...?
    because the stuff is done the same way there too(the part about preference of faster algos over comps)...

    the oracle was good..trouble was i really didn't understand her tendencies..
    i would really appreciate that you take one of these two options...

    1)frame the oracle story better
    2)chuck the oracle and present content in a no-nonsense manner.

    well,that is all.
    few shortcomings....overall a nice article.

    ReplyDelete
  12. If you are still not clear about the problem.It is equivalent to placing two sticks in the array in such a position that the sum between them is the highest compared to any other positions.

    i want this in picture. the ending is pretty well with quotes.tabulations very well done and i agree with biligiri. just one trial isn't enough to understand this.

    the concept is crisp and so is the explanation. i wish it could have been more good if you sort out minor mistakes in the typing here and there

    ReplyDelete
  13. anonymous dude...

    i am clear about the problem.
    very clear,thank you.

    see,what i said was the part about the oracle was fairly unclear. this is what i wanted to be changed. not the problem or article.

    I was only handing out suggestions to better the article..not expressing my misunderstanding.

    thank you for your concern.

    ReplyDelete
  14. @chetan.s.kumar-Am yet to incorporate changes in this article :)and i hadn't got back to you yet :) so what concern are you talking about? :)

    ReplyDelete
  15. Hey Nikitha,

    Very nice explanation. Good job. But i felt if you could explain first the O(n^3) and O(n^2) approaches and then the linear algorithm it would have been much better.

    ReplyDelete