Skip to main content

Posts

Showing posts with the label programming

Need of Open Source ?

You have already got what is  Open Source  from previous blogs. The simple reason is that why to pay if we get is free. Lets take an example you spend lots of money to buy an windows genuine some of the people don’t buy the licence copy of it but they buy an creak (DOS) version of windows but they have some problem in it. Some what same not a completely different OS are freely available in market then why should we pay for it ? You get high quality of software and hardware also in open source. They are very powerful and smooth running no lags get while working.They also give full support to solve your problem.Think an example of google you search on google and you get the result of what you search if google say that I want money for every search results then ?you will pay for it ? That the need of  open source .

Dynamic Programming optimizations for fibonacci series

  the sum of preceding two number. for example, f(n) = { 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , ……………..} mathematical function: f(n) = f(n-1) + f(n-2) , where n>=2 and f(0) = 0 , f(1) = 1 Sample program: /* simple recursive program for Fibonacci series */ int fibonacci(int n) { if (n<=1) return n; return fibonacci(n-1)+fibonacci(n-2); } Overlapping problem: In the above tree diagram we can see (for underlined subtrees) that the left subtree of fib(5) and right subtree of fib(4) are repeated likewise other subtrees are also repeated , to avoid this we use dynamic programming (here Memoization technique particularly). Optimized function code to reduce time complexity: int fibonacci(int n) { if (table [n] == -1) { if (n<=1) table [n] = n; else table [n] = fibonacci(n-1)+fibonacci(n-2); } return table [n]; } In above problem we created a lookup table to save values which are calculated first and use them again if required rather than recalculating it, it will reduce m...

What is Dynamic Programming ?

  What actually dynamic programming is ? In computer science or mathematics,  dynamic programming  is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. Also known as  dynamic   optimization . Dynamic programming is similar to divide and conquer only difference is that dynamic programming is used when there is overlapping subproblem property and in divide and conquer there is no overlapping subproblem property. example, fibonacci series. When to use dynamic programming ? Following two attributes suggests that a problem can be solved using  dynamic programming  : optimal substructure overlapping sub-problems. Ways to of using dynamic programming : Top-Down :  Firstly, Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been s...