Dynamic Programming or Memoization : Simple optimizing Concept yet Effective

Dynamic Programming or Memoization is a well known technique for optimization.  It is just a method that remembers your previously calculated results and stores it somewhere so that when time comes you can use it again.

Just to begin with, a straightforward example of Memoization is calculation of Factorials. When we calculate Factorial of 5, i.e.

5! = 1*2*3*4*5 = 120

Now when you're asked to calculate Factorial of 6, a normal human being wouldn't go on like 1*2*3*4*5*6 rather he would think that "Well, I just calculated upto 5! why not simply multiply 6 to the answer of 5! " This is exactly what we are going to make our computers to do.

So, How do I make computer to remember pre-calculated results?
Answer is as simple as the question, just store them at a particular location in any array/list/vector.

Have a look at this simple Python implementation for memoized Factorial.

C/C++ and Python Program to find GCD of a list of numbers

A very easy question though, yet thought posting about it thinking it may improve my explanation prowess.

Lets get back to old school math, how did we find Greatest Common Divisor (GCD) or you may call it Highest Common Factor(HCF) of two numbers?

Assuming you know primary Maths, I'd proceed further.

Lets take an example before we go ahead.

Find GCD of 54 and 24.

Divisors of 54 are: 1, 2, 3, 6, 9, 18, 27, 54.

Divisors of 24 are: 1, 2, 3, 4, 6, 8, 12, 24.

Common divisors of 54 and 24: 1, 2, 3, 6

The greatest of these is 6.

Hence gcd(54,24) = 6

Okay, lets write an algorithm for this. Well, one would say, there's nothing to think of any algorithm, things are crystal clear. Find out the factors of two numbers, then find common factors and then the largest of them.

But brother! There exists a better algorithm. Our Father of Geometry, Euclid, left us an algorithm already. We simply have to implement it.

Fast Power Algorithm: C/C++ and Python Code

In competitive programming, traditional way to finding power may not work sometimes.

By traditional way I mean if we have to find 2^10 (just as an example).

Or else simply by using library function after including math.h (in C) we can do it by pow(2,10)

Well, but this doesn't help us anymore when it comes to finding base to the power (base^power) where power could be anything in the range 0 to 1000000 or even greater value, same goes for base

Whilst you may think it impractical but in competitive programming questions ask us find Modulus of the answer by any prime number such as 1000000007, just to make sure answer remains in range of int data type.

i.e. pow(2,100)%1000000007 = 976371285

Lets come to the point and discuss what you have come for :)

Fast Algorithm:

result = 1
If power is odd:
    result = result*value
value = value*value
power = power/2

Yeah, I know, above algorithm more looks like a code & was nothing but a bouncer. ;)

6.00x MITx Python: Final Exam Preparation

Just thought of creating an online journal to revise things on the go, cause when I was reviewing video lectures from the beginning it took a lot of time. Sometimes I've to fast forward, normal pace at confusing situations & again fast forward made me sick of revising videos.

I'm only considering the Python language and use of its objects in this section.
This is just an index of all the topics upto Mid Term 1: (Still revising Classes is left for me :( )

Lets begin: (All the links lead to quick overview of respective topic and below the Titles I've briefly written about the stuff that topic contains)

Complexity or Order of Growth in Programming

Complexity or Order of Growth of a program plays a major role in efficient programming. It actually gives an idea of the time taken by your code to run and return correct answer.

• Constant Complexity O(1) : constant running time
• Linear Complexity O(n) : linear running time
• Logarithmic Complexity O(log n) : logarithmic running time
• Log-Linear Complexity O(n log n) : log-­linear running time
• Polynomial Complexity O(n^c) : polynomial running time (c is a constant)
• Exponential Complexity O(c^n) : exponential running time (c is a constant being raised to a power based on size of input)

But this doesn't explain anything, so lets go through some simple examples of each of them.

Python Objects: Dictionary (dict)

Dictionary or dict is generalization of Lists
In list we use [], while in dict {}

>>> l = ['three', 'five', 'one', 'seven']
>>> l[0] #here 0 in l[0] is called index and 0th index refers to three
'three'
>>> l[1]
'five'
>>> l[2]
'one'
>>> l[3]
'seven'

Python Objects: Lists: Mutation of List

Lists are almost same as Tuples, but a huge difference is, Lists are mutable i.e. Lists can be modified after they are created unlike Tuples and Strings

For example, consider a Tuple:

Objects of Python : Tuples

What are Tuples?
Just go through following operations.

>>> t1 = (1,'two',3) #declaring tuple
>>> t1
(1, 'two', 3)
>>> print t1 #does the same thing as above
(1, 'two', 3)
>>> type(t1) #lets check the type of tuple
<type 'tuple'>

Recursion in Programming - Explained

We'll take an example of multiplying two numbers without using multiplication operator. This can be done in typical way of iteration.

For eg: If we are asked to multiply x and y, we'll keep adding x to x for y times

See the following code:

Finding Roots - Advanced (in Python)

Following is the explanation for finding roots (square root, cube root.... nth root) It requires prior knowledge of Bisection Search

This is the advancement of basic version of finding square root of only perfect squares

Linear Search v/s Bisection (Binary) Search

Linear Search:

• It is a sequential search over a list.
• A simple searching technique.
• Used when elements in the list are Unsorted. 
• Its not efficient. (Efficiency discussed below) 

Finding Square Root: Examples of Guess & Check Algorithm

"Guess and Check" - The phrase itself says that we will guess the answer and check, if condition is satisfied, that guess is our answer, else iterate.

An example for this can be, lets say we want to find square root of any perfect square.

Iteration or Looping

Iteration:

• Start with a test
• If evaluates to True, then execute loop body once, and go back to reevaluate the test
• Repeat until test evaluates to False, after which code following iteration statement is executed

Branching Program: Using if, if else, nested if else, elif in Python

Branching programs

The simplest branching statement is a conditon

• A test (expression that evaluates to True or False) 
• A block of code to execute
• if the test is True!
• An optional block of code to execute if the test is False!

Operations on String & some Simple Program Scripts

How to declare a string:

>>> myString = "We are learning" #double quotes are necessary
>>> myStr2 = 'Python' #even a single quote can be used
>>> print myString #print a Python in-built function
We are learning
>>> myString
'We are learning' #single quote indicates that variable myString is a string
>>> myStr2
'Python'

Core Elements of Program: Compilation, Interpretation, Objects, Type Casting

For a code to run on your machine, machine should first understand the code and run the script accordingly.

There are two options for modern high level programming languages. A compiled language or an interpreted language.

Syntax, Static Semantics, Semantics of a Language

As the title suggests 'Learning Python' & also MIT's 6.00x course's Revision, we hereby will go through every aspect of the course as quickly as possible along with some frequently used Python tools.

I take this opportunity as a part of the Final Exam preparation. So we'll include all exam oriented points from the courseware. Best way to revise is to recall examples rather than going through all theory stuff.

Here we go.