Memoization and Fibonacci Numbers

The assignment details the concept of memoization and its application in dynamic programming, particularly in calculating Fibonacci numbers. Memoization is used to eliminate the recursive nature of calculation, improving program execution performance. The document provides background information on dynamic programming, problem relevance, and importance, as well as a timeline and references for further reading.

Memoization and Fibonacci numbers
Name
Institution
Professor
Course
Date

Abstract
Dynamic programming is an algorithmic concept that came in place in 1950’s. It was
applicable in complex situation such as operation research and computer science where complex
calculation dominated. Generating a given value in a Fibonacci number sequence has been quite
hectic due to recursive nature of calculation required. To eliminate the problem of reclusiveness,
the concept of memoization comes in to settle the score. Memoization involves creating a buffer
that holds required optimal sub-solution when calculation of nth value is in progress. The optimal
sub-solution is held and combination of sub-optimal solution continues until the optimal solution
is generated. Dynamic programming involves combination of both recursive and memoization
with an objective of improving program execution performance. When implementing recursive
programs in the Fibonacci numbers generation, memoization must feature in to make process
more dynamic. With memoization, generation of a given nth value in a sequence of Fibonacci
numbers is faster.
Introduction
Dynamic programming involves breaking down complex problem into sub-programs that
can be solved easily. Once the sub-problem is solved, the answer is combined to get solution to
complex a problem. The main problem in this project would be using memoization and dynamic
programing concepts in Fibonacci numbers. In many cases, Fibonacci numbers calculation
makes use of recursion which is quite iterative in nature. Important to note is that, dynamic
programming application in Fibonacci numbers is used to avoid multiple sub-program
calculations experienced in recursive algorithms. Memoization in dynamic programming takes
both Bottom-pup and Top-down approach in solving the subject problem (Moerkotte &

Neumann, 2008). The Top-down approach breaks complex problem into sub-optimal problems
while Bottom-Up approach combines sub-optimal solutions to desirable solution. The process
starts by selecting a problem. Once problem has been identified, the best approach is chosen,
Top-down or Bottom-up. Generally, dynamic problem works in cases where problems have
right-left inherent order such as sequence of integers, strings ad trees graphs. Memoization
involves concepts of storing results from previously computed functions and calling them on
demand. On the other hand, recursion takes place when a program function calls itself several
times while giving similar results from provided inputs. When results from integers are
computed from provided inputs, they are stored in a buffer waiting to be conjoined to one
desirable but complex optimal solution. The process might look similar to recursion but dynamic
programming does not need recursion in order to work. Dynamic programing has its power on
being able to understand which partial results would be required in building up the final answer
(Dai, Chen & Zheng, 2018). Therefore, the goal of this project would be to implement dynamic
programming concepts when calculating an nth value in Fibonacci numbers through memoization.
Typical problems
There are many cases where dynamic programming has been applied but it is very
important to evaluate which approach would work best. To understand the concept of
memoization, dynamic programming and its application in Fibonacci numbers, some case studies
would feature in the discussion. This section would be analyzed intensively by breaking it down
into overview of memoization from inception to present. The background information would
give detailed concepts of memoization and its application in dynamic programming. Similarly, it
will involve evaluation of the problem, its importance and relevance to the study. It is at this
section where key important aspect of memoization and dynamic programming are incorporated.

It is at these two levels where implementation of memoization as it has been conjoined in the
dynamic programming is done.
Background information
Dynamic programming date back 1950’s when its concept was first introduced with an
objective of making complex calculation simple (Cormen et al, 2009). Its operation is based on
common phenomenon of principle of optimality. The principle implies that, the general optimal
solution is a mere combination of sub-optimal solutions to some of its sub-problems. An
evaluation of matrix chain multiplication problem shows that, it is quite wrong to assume the
only value of interest is optimal. All values in the matrix table serves as a representation of
optimal solution in the problem domain. It is important to note that Fibonacci numbers starts
with only two set of values; either integer 1 and 1 or 0 and 1 in relation to chosen starting point.
According to Stivala et al (2010), memoization and dynamic programming is applicable in
Fibonacci numbers due to the fact that, it can be expressed in a finite sequence of decisions at
several stages. The combination of both recursive and memoization was meant to come up with
more reliable methodology to increase the performance of program execution. It is very clear
from various evaluations of research that, dynamic programming through memoization has a
wide array of applications. Finally, though it is highly recommended in many projects, it presents
several challenges. However, it has been successfully implemented in various projects.
Problem relevance and importance
The problem is quite relevant to the study in that, with dynamic programming, the
recursive nature of the problem is eliminated in the program. A good example depicts itself when
a program to find for nth value such as 100 is run. In this case, instead of generating an array of

numbers recursively, the entire set of 99 arrays is generated once and stored in order to be used
in capturing desired results (Dai, Chen & Zheng, 2018). Similarly, when dynamic programming
is used in a program, memoization is the critical idea that improves program execution
performance by eliminating the recursive nature of execution. Dynamic programming makes use
of recursion and memoization to come up with more improved performance of generating and
locating a given set of Fibonacci value (Fender, 2014). Therefore, the most important aspect
would be to implement memoization in a program that generates a given value in Fibonacci
numbers to improve its performance index.
Timeline and milestones
Period
Milestones
1st Week 2nd Week 3rd Week 4th Week
Planning
Resources
acquisition
Coding
Testing and
deployment
References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms.
Cambridge: MIT Press.
Dai, H. P., Chen, D. D., & Zheng, Z. S. (2018). Effects of Random Values for Particle Swarm
Optimization Algorithm. Algorithms, 11(2), 23.
Fender, p. I. T. (2014). Efficient memoization algorithms for query optimization: top-down join
enumeration through... Memoization on the basis of hypergraphs: anchor academic
publishing.
Jaffar, J., Santosa, A. E., & Voicu, R. (2008). Efficient Memoization for Dynamic Programming
with Ad-Hoc Constraints. In AAAI (Vol. 8, pp. 297-303).
Moerkotte, G., & Neumann, T. (2008). Dynamic programming strikes back. In Proceedings of
the 2008 ACM SIGMOD international conference on Management of data. (pp. 539-
552). ACM.
Stivala, A., Stuckey, P. J., de la Banda, M. G., Hermenegildo, M., & Wirth, A. (2010). Lock-free
parallel dynamic programming. Journal of Parallel and Distributed Computing, 70(8),
839-848.