Dynamic Programming

Computer software works like a stack of software. First comes the OS or Operating System, then all applications that run over it, like MS office over windows, which makes a personal computer mostly comfortable for personal use. However, OS itself works like an application, an application works by access to resources from OS, optimizes resources to better deliver its use cases. But OS provides stack, stack frames to applications from its conceptual resources. This being the case the application writers are bound to write programs with no recursion functions but looping in place. Due to recursion functions create a lot of stack frames. But this is not the case with OS software creating program itself where no of lines of source code also matters. So recursion is invited in OS level code not in application level code. There is a remedy to using recursion functions on scale with application level coding. That is dynamic programming.

Dynamic programming can't be applied in all problems but in problems with the following structures,

Optimal substructure

Overlapping sub problems

Taking the problem of finding the n-th fibinocci number, there is an optimal substructure in the fibinocci number generation itself by definition, that is,

f(n) = f(n-1) + f(n-2)

Overlapping sub problems is when calculating f(5), f(4) and f(3) needs to be calculated, but to calculate f(4) again f(3) needs to be calculated and it recurs in the tree of recursive calculation and storing all calculated values and making a check if the value is available in memory can save processing and stack frame of functions and it leads to great speed. Following is the python code for fibinocci with dynamic programming.

def fibi(n):
    if n==1:
        return 0
    elif n==2:
        return 1
    else:
        return fibi(n-1)+fibi(n-2)
        
        

d={}
def fibi(n):
    if n in d:
        return d[n]
    if n==1:
        d[1]=0
        return 0
    elif n==2:
        d[2]=1
        return 1
    else:
        d[n]=fibi(n-1)+fibi(n-2)
        return fibi(n-1)+fibi(n-2)        

The first program will not scale with memory, OS and will halt the system with RAM overflow with stack frames. The second program on other hand intelligently solves the stack overflow problem with dynamic programming. It simply uses a dictionary to store already calculated nth fibinocci number and always sees if the fibinocci number is there in the dictionary before calculation. This is a great way to reduce time and memory.

Various problems solved by dynamic programming includes Longest Increasing Subsequence, Maximum Profit in Job Scheduling, Palindromic Substrings.

Longest Increasing Subsequence:

This problem can be useful for OS software in finding the longest contiguous array used and occupied by program code. This lets the OS to equally block the arrays in one chunk in front or end to let way for more free access to all other memories.

Maximum Profit in Job Scheduling:

This problem of allocating resources to multiple applications by OS is in minimization of the total resources used and that is the profit in scheduling resources continuously between applications by OS. Dynamic programming written within OS code can handle it good.

Palindromic Substrings:

The problem of palindrome finding in a long string is useful for monitor in printing lets say in bringing up an entire article when opening an website. Palindrome can optimize writing over monitor screen pixels both sides. So identifying them prior can optimize monitor processing and on scale it optimizes most of the computing resources, due to so much processing power required for monitor display.

Code and see how dynamic programming really works, use advanced concepts like decorators in python for memoization technique which is memorizing nth fibinocci like here.

Happy coding,

Murukessan,

Artificial Intelligence Researcher