Showing posts with label algorithms. Show all posts
Showing posts with label algorithms. Show all posts

Wednesday 6 November 2013

Recursion and Memoization - A Fibonacci Example

In this post, I will try to describe why memoization can be a great optmization technique in the recursive function implementations with an example of fibonacci sequence.

Straight from Wikipedia, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs.

Basically, we maintain a lookup table and store the computer values for particular cases which lets us query and use the corresponding value for particular case present in the lookup tables. This reduces function call overheads. Now in order to understand why this is a great optimization technique in recursion, lets first draw a recursion tree for finding nth term in fibonacci sequence.

                           fib(5)                          
                             /\                              
                            /  \
                           /    \
                          /      \                      
                     fib(4)       fib(3)                                 
                      /\               /\                          
                     /  \             /  \
                    /    \           /    \
                   /      \         /      \                         
               fib(3)    fib(2)     fib(2) fib(1) -> 1                                    
                  /\         /\          /\                          
                 /  \       /  \        /  \                         
                /    \     /    \      /    \
               /      \   /      \    /      \                        
          fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) -> 0                                        
          /\        |     |      |        |    |               
         /  \       1     1      0        1    0               
    fib(1) fib(0)                                                       
       |      |                                               
       1      0 


We can clearly see the calls to fib() with same arguments several times. For example, fib(1) is called 5 times and fib(2) 3 times. Thus, we are repeating same calculations multiple times and imagine how this would look like for large value of n. If we would have maintained the value of fib(n) in the lookup table when computed the value for the first time.

The python code without memoization looks like below and notice the runtime:
#!/usr/bin/python

def fib(n):
        if n == 0:
                return 0
        if n == 1:
                return 1
        val = fib(n-1) + fib(n-2)
        return val

print fib(50)


And, now with the memoization, you will notice significant improvement in runtime.

#!/usr/bin/python

known = {0:0, 1:1}

def fib(n):
        if n in known:
                return known[n]
        known[n] = fib(n-1) + fib(n-2)
        return known[n]

print fib(50)


If you run and compare above two codes, you will find that the addition of memoization significantly improves the performance of recursive functions. Recursion are generally known to be terribly slow however memoization can make the difference insignificant. Some languages now provide memoization as the language feature natively or via third party APIs such as groovy memoize.


Read more...

Sunday 29 April 2012

Answers To Introduction To Algorithms 1.2-2 and 1.2-3

Algorithm is a fun subject and we are starting from the very basics of algorithm. Here is my solution for selected questions from chapter 1 of Introduction To Algorithms by Cormen and others.

1.2-2) Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64nlg n steps. For which values of n does insertion sort beat merge sort?

Here, we need to determine the value of n such that 8n2 = 64nlgn

For the value n = 1, obviously the merge sort beats the insertion sort so we will start from 2 and find the higher limit up to which the insertion sort beats merge sort.

The above equation can be further reduced as n = 8lgn. We can now solve it to determine the value of n. A simple code in C that would do the job for us is as below:

#include <stdio.h>
#include <math.h>

int main()
{
 int i = 2;
 while (1)
 {
  int merge = 8 * log2(i);
  if (i > merge)
  {
   printf("Value of i: %d\n", i);
   break;
  }
  i++;
 }
 return 0;
}

Answer: 2 <= n < 44. 1.2-3) What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?

Here, we need to determine the smallest value of n such that 100n2 < 2n. The value of n evaluates to 15. The source code for above problem is as below:

#include <stdio.h>
#include <math.h>

int main()
{
 int i = 2;
 while (1)
 {
  int x = 100 * pow(i, 2);
  int y = pow(2,i);
  if (x < y)
  {
   printf("Value of i: %d\n", i);
   break;
  }
  i++;
 }
 return 0;
}

I hope this helps some of the algo beginners out there trying to solve the questions from "Introduction To Algorithms". Btw, they are basic maths however :P

Read more...