Patterns

In approaching a problem to be solved, it is beneficial to think of patterns which are applicable. One needs to have some experience in solving problems.

After a number of years of figuring out solutions, one becomes better at recognizing patterns which apply for the problem under consideration. It appears that one of the main strengths of human consciousness is that we can recognize patterns quite well in nature and in daily life when solving problems.

Algorithms

In programming, an algorithm is a way to codify a pattern which someone has recognized in solving a problem or a number of problems. In solving problems using mathematical tools, one comes up with theorems and rules. In computer programming, one comes up with algorithms.

Dynamic programming

As with many computer science algorithms and techniques, dynamic programming has a mathematical background. The concept of dynamic programming was conceived in the 1940s as a mathematical optimization technique.

There are two main ways of applying dynamic programming to a problem: one is called memoization and the other is the bottom up approach.

A prerequisite for dynamic programming is that the problem has an optimal substructure and overlapping subproblems.

Memoization usually involves coming up with a recursive algorithm for the problem and then, making  use of the already calculated results in the recursion so that the number of recursive calls are reduced significantly.

The bottom up approach involves coming up with the solution for the subproblem and then building the results in a bottom up way  by storing the results in a table. The result of this usually ends up in the last element of the table.

A common example for dynamic programming is the fibonacci series problem. The fibonacci series is defined as a number at index n being the sum of the numbers at the previous two indices in the series: n-1 and n-2. The base case is that the series always starts with 1, 1, 2,…

Using memoization, the solution to the fibonacci series problem is as follows:

memo = {}

def fibonacci(n):
    global memo

    if n in memo:
        return memo[n]

    if n <= 2:
        return 1

    f = fibonacci (n-1) + fibonacci (n-2)
    memo[n] = f
    return f

Using the bottom up approach, the solution to the fibonacci series problem is as follows:

def fibonacci(n):
    memo = {}

    for i in range(n):
        if i<=1:
            memo[i] = 1
            continue

        memo[i] = memo[i-1] + memo[i-2]

    return memo[n]

Solving problems

It is interesting to see the connectivity between mathematics and computer science. In mathematics, problems are solved by applying theorems and formulae. Many of the algorithms in computer science have mathematical proofs. We use these algorithms in the form of code to solve problems in computer science.

Algorithms

One of the reasons why computers have become so successful and ubiquitous in today’s culture is that over the several decades, computer scientists have been perfecting the art and science of algorithms. Algorithms were conceived in man’s mind and have been running machines using the awesome underlying power of semiconductors.