Have you heard of the
Fibonacci Sequence?
It’s a sequence of
numbers whereby, every number is the sum of the previous two numbers.
Stating things more
formally,
Tn=Tn-2+Tn-1
The Fibonacci Sequence
with T1 = 1 and T2 = 1 is: 1, 1, 2, 3, 5, 8, 13, 21, 34,
55, 89……
Suppose we had to write
a program which prints on the screen n terms of the Fibonacci Sequence: One way
of
doing that would be:
#include <iostream>
using namespace std;
int Fib(int a){
if(a==1
|| a==2){
return
1;
}else{
return
Fib(n-2)+Fib(n-1);
}
}
int main(){
int
n;
cin>>n;
for(int
i= 1;i<=n;i++){
cout<<Fib(i)<<’
‘;
}
cout<<endl;
}
In this implementation, the running time would be
what?
Let’s See:
We’re running the main recursion up there, and for
every number n it forces us to run recursion again on (n-1) and on (n-2), which
takes us n computations right?
And we that for ‘n’ computations, down in the main loop,
Thus roughly speaking our Running time here would be O(n2).
Can We do better?
Can We make the Program more efficient?
As it turns out we can!
Check out the following Program:
#include <iostream>
using namespace std;
int main(){
int
n;
cin>>n;
int
fib[n+1];
for(int
i = 1;i<=n;i++){
if(i==1
|| i==2){
fib[i]
= 1;
}else{
fib[i]
= fib[i-1]+fib[i-2];
}
cout<<fib[i]<<’
‘;
}
cout<<endl;
}
Now, Let’s try to figure, its running time, We just
have one main loop which runs for N times. Thus, the Running time/Complexity is
O(n).
Now,
What was the difference between the two programs we
saw above?
What made the second one more efficient while the
first one was less?
That’s where the paradigm of Greedy Algorithms and
Dynamic Algorithms (or Dynamic Programming) comes into play.
The first Program/Algorithm was what we may term a
Greedy Algorithm because in every iteration/computation of that algorithm we
computed something rigorously without thinking if we had computed it previously
as well or not.
While in the Second Program/Algorithm, it would be
termed Dynamic because at every step we stored the nth term of the
Fibonacci Sequence so that we could again use it to compute the next term.
That’s somewhat like the General Structure of a
Dynamic Algorithm, what we do in a Dynamic Algorithm in a step wise manner:
1.
) The initial stage of designing a dynamic programming algorithm for a problem
usually involves generalising the problem slightly, and solving a collection of
smaller subproblems as well as the specific problem instance described by the
input. Although this seems as though we have made our problem harder (by
deciding to compute extra results), an intelligent choice of generalisation
will be the key to solving our original problem efficiently. For the Fibonacci
number problem, our generalisation will be to compute all of F(0), F(1), F(2),
. . . , F(n), rather than simply F(n).
2)
Once we have generalised our problem, we will then write down a recurrence (or,
more generally, a short algorithm) for solving one problem instance in terms of
“smaller” (in some sense) problem instances. It must be the case that the
smaller problem instances on the right-hand side of the recurrence lie within
the set of subproblems identified in dp1(a) above (and that this is true
recursively). dp1(a) and dp1(b) really must be done together. For the Fibonacci
number problem, our recurrence is as in the definition: Fn = Fn−1 + Fn−2, for n
≥ 2.
3)
Next step is to allocate storage for the results for each of the subproblems
(identified in 1), 2)) which we will solve during our algorithm. Usually it is
possible to store the subproblems in an table - hopefully, this will be
1-dimensional, or 2-dimensional. There are problems which require 3-dimensional
(or greater) tables, but we won’t see those in ADS. If we start designing a DP
algorithm and find that the set of identified subproblems from 1) will not fit
in a sensibly-structured table with a reasonable number of dimensions, and of a
reasonable size, this might indicate that there is no good DP algorithm for
that problem. The table we use for the Fibonacci number problem is an array of
length n + 1, indexed from 0 upwards. This array will store F(k) at the index
k.
4)
Finally, we must set up an algorithm to control the order in which subproblems
are solved (and their results stored in the appropriate cell of the table). It
is imperative that this be done in such a way that all of the subproblems
appearing on the right-hand side of the recurrence must be computed and stored
in the table in advance of the call to that recurrence (in cases where we can’t
see how to do this, it may be that our problem, or recurrence, is not amenable
to DP).
Computing
Fibonacci Numbers is a very elementary way of implementing the paradigm of
Dynamic Programming.
Here
are some other(more rigorous!) examples of Greedy Algorithms and Dynamic
Algorithms:
Greedy
Dynamic
You should go well
through the exercises to get a nice idea of DP (short for Dynamic Programmng)
and Greedy Algorithms as they are ideas central to CS.
Exercises
NOTE: You need to keep
in mind that your computer can’t perform more than 107 -108
Computations in a second, and need to develop an algorithm which has running
time falling between those boundaries. Also You’ll need to Incorporate all your
knowledge of Algorithms from Sorting & Searching to DP and Greedy
Algorithms in order to solve these Problems.
Try Solving Programming Exercises from the Following Links:
Comments
Post a Comment