Showing posts with label

**algorithms**. Show all postsShowing 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 n

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:

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

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...

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 n

^{th}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...

Recursion and Memoization - A Fibonacci Example

2013-11-06T22:49:00+05:45

Cool Samar

algorithms|python|recursion|

Comments
Labels:
algorithms,
python,
recursion

Bookmark this post:blogger tutorials
Social Bookmarking Blogger Widget |

## 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.

Here, we need to determine the value of n such that 8n

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:

Answer: 2 <= n < 44.

Here, we need to determine the smallest value of n such that 100n2 < 2n. The value of n evaluates to

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...

**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 8n**^{2}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 8n

^{2}= 64nlgnFor 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 100n**^{2}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...

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

2012-04-29T20:51:00+05:45

Cool Samar

algorithms|C/C++|programming|

Comments
Labels:
algorithms,
C/C++,
programming

Bookmark this post:blogger tutorials
Social Bookmarking Blogger Widget |

Subscribe to:
Posts (Atom)