Think Dynamically!!!
In problem solving, there are two types of algorithms that we can use to find solutions for the problems.
1. Greedy algorithms — Provide greedy solutions.
2. Dynamic algorithms — Provide shortest way to for a problem.
In this article, I would like to talk about Dynamic approach to solving some complex problems. Before resolving complex problems, I would like to talk about the approach with a small selected problem. I selected finding fibonacci for a given n value. Later, I hope to go with such problems like finding the longest palindrome in a given string and knapsack (within few days :D).
Before move forward, we need to know about time complexity of a solution for a problem.
Time Complexity
The computational complexity that describes the time required to execute an algorithm. I will only go with names.
1. Constant — O(1)
2. Logarithmic — O(lg n)
3. Linear — O(n)
4. Linearithmic — O(n lg(n))
5. Quadratic — O(n**2)
6. Cubic — O(n**3)
7. Exponential — O(2**n)
8. Factorial — O(n!)
THE LEARNING PLAN!!!
We will convert the solution from exponential time complexity to linear time complexity step by step.
1. first, we will implement exponential solution.
2. Then, will reduce repeated calculations by using memoization technology.
3. Then, we will use bottom-up-approach.
So let’s have a cool dive into problem fibonacci!!!!
First! what is fibonacci,
https://en.wikipedia.org/wiki/Fibonacci_sequence
The easiest way to implement the solution is using recursive function like follows,
// assume n >= 0
public class RecursiveFibonacci {
public static int fibonacci(int n) throws Exception {
if (n < 0)
throw new Exception("Negative integers not accepted");
if (n <= 1)
return n;
else
return fibonacci(n-1) + fibonacci(n-2);
}
}Wow!!! It seems more simpler, Let’s have a look before coming to a conclusion. For the analysis perspective let’s draw a flow chart for above solution. Just imagine we are going to calculate fibonacci(10)
What is the time complexity of above algorithm? O(2**n)
More details https://www.youtube.com/watch?v=pqivnzmSbq4
Looking at above graph, we can see some fibonacci values calculate more than one time which is not necessary and we can avoid. To avoid this we can use memoization technology which is not complex, it is just keep the value when it calculates very first time and reuse when it request again.
public class RecursiveWithMemoization {
private static Integer[] fibMemory;
public static int fibonacci(int n) throws Exception {
fibMemory = new Integer[n + 1];
fibMemory[0] = 0;
fibMemory[1] = 1;
return calculateFibonacci(n);
}
private static int calculateFibonacci(int n) throws Exception {
if (n < 0)
throw new Exception("Negative integers not accepted");
else if (n <= 1)
return fibMemory[n];
else {
if (fibMemory[n] != null)
return fibMemory[n];
else {
int temp = calculateFibonacci(n - 1) + calculateFibonacci(n - 2);
fibMemory[n] = temp;
return temp;
}
}
}
}This is pretty good than first algorithm, is it? yes, we would not see the benefits of this when we consider small n values. Let’s imagine the n is 1000k. Then the computational power become too high than second algorithm.
Ooops!!!
Is the second solution the best way to solve fibonacci? If there are another best way, what are the drawbacks of second algorithm?
Think before Read rest of the post.
How this algorithm works, let’s draw the steps in a graph to find the value of fibonacci(5)
As per above diagram let’s start with fib(5) and go through the arrow order to understand the flow.
Note : Consider STEP-N as arrow number N in above image
Let’s summarize the flow, first, we should find fib(4) and fib(3) to calculate fib(5), but the both values are not known. For that this algorithm try to find fib(3) and fib(2) to calculate the value of fib(4). Likewise it’s reached step-4. Then the algorithm request for the value of fib(1) which is a known value stored in memory array. So the value get from memory array as step-5 and return to fib(2) as step-6, likewise algorithm gets the value of fib(0) from memory array. Now the values that need to calculate fib(2) is already available so we can execute fib(1) + fib(0) to find fib(2). After calculate the value of fib(2) we store the value of fib(2) in memory array (step-10) for the future usage and return the value to calculate fib(3) as step-11. So far Pretty clear. So let’s jump to the step-16 which returns the calculated fib(3) value to calculate fib(4). To calculate fib(4), it requires fib(2) as well but this time we not need to calculate fib(2) since we already calculated that value and stored in memory for future usages, so let’s grab the value from memory as step-18 and use it. Likewise we can calculate the value of fib(5).
So what is the drawback of this approach to find fibonacci?
Just look at the image above, do we actually need step-(1,2,3,4,7,12,17,22)s. No we not need, this is where the Bottom-up-approach will come to play.
Bottom-up-approach. What is that?
When we calculate fibonacci, we know the values of fibonacci(0) and fibonacci(1), from that we can calculate fibonacci(2), then we can find fibonacci(3) by using fibonacci(1) and fibonacci(2). If we continue this till n we can find fibonacci(n). So simple, is it? Yeah. This approach is called bottom-up-approach.
Bottom-up-approach is beginning from lower known values and reach the targeted value. Simple!!!
public class BottomUpFibonacci {
public static int fibonacci(int n) throws Exception {
if (n < 0)
throw new Exception("Negative integers not accepted");
else if (n <= 1)
return n;
else {
int temp1 = 0; // fibonacci(0) = 0
int temp2 = 1; // fibonacci(1) = 1
int temp = 0;
for (int i = 2; i <= n; i++) {
temp = temp1 + temp2;
temp1 = temp2;
temp2 = temp;
}
return temp;
}
}
}To better understanding refer the below graph and follow the step arrows.
Note: Temp1 and Temp2 is memory slots, blue color arrows for get from memory, black color arrows for save the value to memory and red color arrow is for calculate the value from fetched value.
Above approach is linear time O(n). Cool!!!!
We achieved, Nice!!!
Summary!!
We converted the solution from exponential time complexity to linear time complexity step by step.
1. first, we implement exponential solution.
2. Then, reduced repeated calculations by using memoization technology.
3. Then, we used bottom-up-approach.What is Next!!
Apply above learnt approaches to resolve complex problems like finding longest palindrome in a given string/ knapsack problem etc.You can find my more articles from my medium spreadsheet
Coming up next
Find the longest palindrome in a String.