24.3. End of Lecture

So, one way to get around this is to make sure that you never reevaluate a sub problem. So, you build up a table which is sometimes called a memory table and what does the table do? It just keeps track of every value for which you have computed the function before.

Memoization is a technique used to optimize recursive algorithms by storing previously computed values. Instead of recalculating the value for a subproblem each time it's needed, you check if the value is already in a storage table (the memory table). If it is, you return that value instead of computing it again, saving computational time and effort.

Think of memoization like using a recipe book. If you bake a cake and write down the recipe, the next time someone asks how to bake that cake, you don’t need to go through the entire process again. You just look it up in your book. Similarly, memoization helps you by storing results you've already computed.

So, how does memoization work? So, we have this memo table here, so this is our memo table, so in this memo table it is just a table where we fit different value of k and fib k has we compute them.

When using the memoization technique, you start with an empty memo table. Each time you compute a Fibonacci number, you first look in your memo table to see if that value has already been calculated. If not, you compute it and store it in the table. The next time you need that value, you can retrieve it directly from the table without needing to recalculate it.

Imagine storing phone numbers in your phone. When someone calls you, you don’t remember their number; you look it up in your contacts instead. Just like this, memoization allows your program to 'look up' values rather than 'remembering' them through repeated calculations.

What you can see in this is that the computation tree which used to be exponential is now linear.

Without memoization, calculating Fibonacci numbers grows exponentially in complexity due to repeated calculations of the same values. However, with memoization, you drastically reduce the number of calculations, turning the complexity from exponential to linear time. This means that instead of computing many values multiple times, you compute them only once and reuse them.

Consider a librarian who keeps retrieving the same book for multiple patrons. Each request takes time. If the librarian keeps a record of past requests and remembers who took which book, they could check the record and retrieve the book much faster. This is like transitioning from many recursive calls to a single linear process.

So, just to see what the memoized Fibonacci looks like? So, the green code is what we wrote earlier, fib of n, if n is 0 or 1, set the value to n.

Implementing memoization in a Fibonacci function involves creating an array (a table) that stores the results of previously computed Fibonacci numbers. Each time the function is called, it checks this table before computing the value. If the value is present, it uses it directly, which speeds up the program significantly.

Think of a student studying for exams. Instead of revising the entire syllabus repeatedly, they create a summary of what they've learned. Whenever they forget something, they check their summary instead of starting from scratch. This way, they save time and can focus on the new material.

So, the other term that we introduce in the last lecture is dynamic programming.

Dynamic programming is similar to memoization but differs in that it focuses on breaking down problems into simpler subproblems and solving them based on their dependencies rather than through recursion. It anticipates what entries will need to be filled in the table beforehand and fills them iteratively, typically leading to more optimized solutions.

Imagine a factory producing a product using various parts. Ideally, you want to produce each part first before you can assemble the product. Instead of building each part as needed, you produce all parts in one go based on a schedule, much like how dynamic programming organizes and solves subproblems efficiently.

--