Monthly Archives: July 2011

Recursion in Python

                   Recursion is a method where solution to a problem depends on solutions to the

smaller instances of the same problem.One of the most magical thing that a program can do

is to define a function that can call itself. Here is an example:

def countdown(n):

if n==0: return 0

else: return countdown(n-1)+ n

print countdown(3)

When we execute this program ,the output obtained will be 3.

We use a stack diagram to represent the state of a program during function call.Every time

a function gets called , a  new function frame containing local variables and parameters

are created by the Python.The following is the stack diagram for countdown() with n=3.

For a recursive function ,there might be more than one frame on the stack at the same time.

The top of the stack is the frame for __main__.The four countdown frames have different

values for the parameter n.The bottom of the stack ,where n=0,is called the base case.

When the base case is reached ,no more recursive calls are made,hence no more frames

are created.

If a recursion never reaches a base case, it goes on making recursive calls forever, and

the program never terminates.This is known as infinite recursion. Here is an example of

a minimal program with infinite recursion:

 

def recurse():

recurse()

One of the dangers of the code that calls itself is that,it will get into an endless loop and

so there will be a limit to the number of levels deep we can go.In Python that defaults to 1000.

But we can increase the limit of depth using the setrecursionlimit method of the sys class.

The following is an example code that uses the setrecursionlimit method to change the

depth level of the recursion:

import sys

sys.setrecursionlimit(1500)

def countdown(n):

if n==0: return 0

else: return countdown(n-1)+n

print countdown(1200)

When we run the code without that extra line,”RuntimeError: maximum recursion depth

exceeded” we will get the ouput 720600.

Heap Sort

                               

                         A heap is a specialized tree-based data structure that satisfies

the heap property: if B is a child node of A, then key(A) ≥ key(B). This

implies that an element with the greatest key is always in the root node,

and so such a heap is sometimes called a max-heap. Alternatively, if the

comparison is reversed, the smallest element is always in the root node,

which results in a min-heap. The heap is an efficient implementation of an

abstract data type called a priority queue. Heaps are crucial in several

efficient graph algorithms such as Dijkstra’s algorithm, and in the sorting

algorithm heap sort.

Heap sort is an implementation of a binary heap. Once we

have implemented the heap,we will easily deduce heap sort.The data

structure of the heap sort algorithm is a heap. The data sequence to be

sorted is stored as the labels of the binary tree.For each element at index i

in the tree:its left child is at index 2i+1,its right child is at index 2i+2 and its

parent  is at (i-1)/2.If the provided  list is not empty,it will be heapified and new

elements can be inserted to the heap.A new element   will be first put at the

end of the tree,then pulled up until the tree satisfies the heap priority.

To add an element to a heap we must perform an up-heap operation also

known as bubble-up in order to restore the heap property. We can do this

in O(logn) time, using a binary heap, by following this algorithm:


  1. Add the element to the bottom level of the heap.
  2. Compare the added element with its parent; if they are in the correct order, stop.
  3. If not, swap the element with its parent and return to the previous step.

 

An almost complete binary tree with n vertices has a depth of at most log(n).

This approach requires O(n.logn) time because each insertion takes

O(n.logn) time and there are n elements.Thus,the time complexity of

heap sort is T (n)=O(n·log(n)).

Python Classes and objects

             Python is fully object-oriented: we can define our own classes, inherit from our own or built-in classes,
 and instantiate the classes we have defined.
A Python class starts with the reserved word class, followed by the class name. 

A Simple Python Class

class Point(object):
	pass

1. The name of this class is Point, and it doesn't inherit from any other class. 

2. This class doesn't define any methods or attributes, but syntactically, there needs to be something in the 
   definition, so you use pass.

3. Everything in a class is indented, just like the code within a function, if statement, for loop, and while loop. 

Here the pass statement in Python is like an empty set of braces ({}) in Java or C.

A class efinition can also like this:

class Point(object):
    """represents a point in 2-D space"""

Here the body is a docstring that explains what the class is for.
Let us see what will be the output when we will print the calss Point.

>>> print Point
<class '__main__.Point'>

Since the class Point is defined at the top level, its “full name” is __main__.Point.

To create a Point,call Point as if it were a function.

>>> blank = Point()
>>> print blank
<__main__.Point object at 0xb7785a6c>

The output will be a return value,that is a reference to a Point object, which we assign to blank. Creating a new object is
 called instantiation, and the object is an instance of the class.

We can also assign values to an instance using dot notation.For example:

>>> blank.x = 3.0
>>> blank.y = 4.0

To read the value of an attribute we will use the following syntax:

>>> print blank.y
4.0
>>> x = blank.x
>>> print x
3.0

We can also define functions inside the class as same as the attributes.
ex:-

class Rectangle(object):
    """represent a rectangle.
       attributes: width, height, corner.
    """
To represent a rectangle, you have to instantiate a Rectangle object and assign values to the attributes:

box = Rectangle()
box.width = 100.0
box.height = 200.0
box.corner = Point()
box.corner.x = 0.0
box.corner.y = 0.0

The figure shows the state of this object:

An object that is an attribute of another object is embedded.

Here find_center takes a Rectangle as an argument and returns a Point that contains the coordinates of the center of the Rectangle:

def find_center(box):
    p = Point()
    p.x = box.corner.x + box.width/2.0
    p.y = box.corner.y + box.height/2.0
    return p

Here is an example that passes box as an argument and assigns the resulting Point to center:

>>> center = find_center(box)
>>> print_point(center)
(50.0, 100.0)