## Thursday, October 10, 2013

### Design and Analysis of Algorithms: Merge Sort

In computer science, a merge sort (also commonly spelled mergesort) is an O(n log ncomparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and Neumann as early as 1948.

The Divide and Conquer paradigm involves three steps at each level of the recursion.

1. Divide the problem into a number of subproblems. Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, just solve the subproblems in a straightforward manner. Sort the two subsequences using merge sort.
3. Combine the solutions to the subproblems into the solution for the original problem. Merge the two sorted subsequences to produce sorted answer.

Algorithm for Merge Sort:

Here A is an array p is start, q mid and r is the last item index. So A[p...r] is the full array that breaks up into A[p...q] and A[q+1...r]. So here is the Algorithm. The Algorithm is divided into two steps one is MERGE procedure that takes up two subsequences and merge them or combine them as per the values and MERGE-SORT that break up a Sequence into two subsequences.

MERGE(A,p,q,r):
n1 = q-p+1
n2 = r-q
create_arrays L[1...n1+1] and R[1...n2+1]
for i=1 to n1
do L[i] = A[p+i-1]
for j=1 to n2
do R[j] = A[q+j]
L[n1+1] = infinite
R[n2+1] = infinite
i = 1
j = 1
for k=p to r
do if L[i] <= R[j]
then A[k] = L[i]
i=i+1
else A[k] = R[j]
j=j+1

MERGE-SORT(A,p,r)
if p < r
then q = [(p+r)/2]
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE-SORT(A,p,q,r)

Merge Sort Implementation of the above algorithm taken from Introduction to Algorithms by CLRS.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48``` ```# implementing merge sort algorithm # p<=q

One more optional Implementation also.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45``` ```# implementing merge sort algorithm # p<=q
-->

## Saturday, September 7, 2013

### PyCon India 2013 Banglore: Great Event got Pythonicated

The event every python developer should attend to meetup the other python programming companions in the area. The event makes you learn, realize , sharpen and get motivated in your python development. PyCon 2013 with what it offered to the developers is a great combination and exposure up to what level you can use python. When I came to know that Armin Ronacher the Flask Maintainer not coming to the event , I thought the event would suffer his absence but I came out from the event very happy and enthusiastic that I really learned something and got motivated for the future to improve my learning.

PyCon from 30th August 2013 to 1st September 2013 came with lots of aspects of the python programming and python module that we see but do not use and also those that we have not seen but really good to know that

Please have a look at the conference site PyCon 2013 here: http://in.pycon.org/2013/. To see more about the conference slides and discussion. What I personally feel the best presentations that was really nice to listen is from Kenneth Reitz Keynote 1st September , Kiran Jonnalagadda Keynote 31st August was superb , Data Visualization in Power Point with Python from Anand S , Real Time stream computations on graphs using storms, neo4j and python , scrape the web using scrapy, Django Beyond Basics and the most important the Open Space where Many People shared their knowledge about Python , Google Summer of Code, Machine Learning using Scikit-learn Python.

-->

## Saturday, August 24, 2013

### colormycode a hilite.me fork by me

colormtcode is the fork of hilite.me and the current status of colormycode.herokuapp.com is same as hilite.me but I would like to let people know that colormycode.herokuapp.com can updated to make the code editing window larger enough to increase proper view to the users.

Moreover colormycode site future aspect would be an intuitive online editor like Python Fiddle , js Fiddle. It would not be like the github gist which also has version control in the code snippets but something the bloggers need to quickly test and deploy the colored code.

Production URL: http://colormycode.herokuapp.com/
Source code: http://colormycode.herokuapp.com/

-->

## Sunday, August 18, 2013

### Version Control Systems : governing Open Source Development

Revision control or Version Control System(VCS) is the diary of the software control management that keeps track of all the changes a software undergo after each commit from the user. The changes are usually identified by naming conventions like "changev1", "changev2". The version control has many advantages over the simple source code hosting mechanisms.

Advantages over simple source code hosting at hard drives:
1) Version control does not require to make different copies on the same drive, as we do with our source code. One for testing, One for development, instead version control system uses branching feature to make this task possible.

2) Version control system maintains proper history of all the changes made, but our simple source code management does not.

3) After certain failure in the source code, we need to go to our source code copy and make changes accordingly but version control system has the easy revert system that shifts back the development to the previous version.

4) Version control is good for collaborative development as each collaborator can see the respective changes in the source and for what reason they have been made, but in simple source code hosting each collaborator needs the copy of the code on their system and one maintainer manages the development code after comparing the main code from the collaborator's code.

5) Even great addition to version control make it more better like issue tracking service, forums and discussions, make version control more easy and understandable means in keeping track of the source code than the simple source code hosting system.

6) Version control maintains user permissions and the users who are permitted to make changes can make changes other do not, others can post patches and code for review. This supports social coding (open source) a lot.

Version control is divided in two main types

1) Central Version System : Central Version Control system are based on a single "Central" repository, and all the programmers would commit their changes in this central repository. Now this change can be seen by all other programmers, these programmers can pull the changes to their system and version control also automatically updates the change made.
The best example for the Central Version System are Subversion and SourceSafe.

2) Distributed Version Control System: The distributed version control system do not necessarily rely on the central server to store all the versions instead every programmer clones the copy of the source and has the whole history on their machines.

The examples of Distributed Version Control System are: git , mercurial and bazaar.

Advantages of Distributed Version Control System over the Central Version System

• Performing actions other than pushing and pulling  is extremely fast because the tool only needs to access the hard drive , not the central server,
• Committing new changesets can be done locally without anyone else seeing them, Once you have a group of changesets ready you can push all of them at once.
• Everything but pushing and pulling can be done without an internet connection. So you can work on a plane, and you won't be forced to commit several bugfixes as one big changesets.
• Since each programmer has the full copy of the project repository, they can share changes with one or two other people at a time if they want to get some feedback before showing the changes to everyone.

## Friday, June 21, 2013

### New Cult of Learning: From Books to Digital Media

Technology has changed the living and yes it has changed the education very effectively. Before we used to study with out college or school mates only, and if we get into discussion that would be of very small circle where we find our friends , Teachers and colleagues. But now the Power of Internet has changed the learning. People might have heard of Digital books called e-books that has saved the paper a lot and served the society with one of the greatest thought supporting the steps to avoid the cutting of trees and Green Revolution.

But today I am not talking about that I am talking about the Online Education that has drastically changed the learning. People can learn , practice and get reviews of how they performed online. Online Courses have provided a way for distant students admiring to study in the top universities of the world. Well, you are not enrolled as an student in these universities but you get the knowledge that how people study in these top universities , what strategies the Teachers follow that make these top universities different than others.

Today Online Courses get good response from the students as millions of students are studying from home excelling their skills, and yes this help them making good knowledge as well as make each course counted to their professional accounts or Resume. Adding more to this Now you do not discuss your knowledge in the small local circles with friends and Teachers whom you meet but with the whole world and lots of intelligent people advise you, correct you , help you to make your learning experience better than you would have imagined before.

Now here I present some useful resources that may help people to find ways to learn online

In news
http://www.skilledup.com/blog/the-best-mooc-provider-a-review-of-coursera-udacity-and-edx/

## Thursday, June 13, 2013

programming paradigm is a fundamental style of computer programming. There are four main paradigms: imperativedeclarativefunctional(which is considered a subset of the declarative paradigm) and object-oriented. Programming Paradigms defines the problem with different approaches and are made for some particular purposes.

• Procedural Programming (Imperative Programming):

• The imperative programming paradigm assumes that the computer can maintain through environments of variables any changes in a computation process. Computations are performed through a guided sequence of steps, in which these variables are referred to or changed. The order of the steps is crucial, because a given step will have different consequences depending on the current values of variables when the step is executed.
• There are two reasons for such popularity:
1. the imperative paradigm most closely resembles the actual machine itself, so the programmer is much closer to the machine.
2. because of such closeness, the imperative paradigm was the only one efficient enough for widespread use until recently.
3. C, Python, FORTRAN , Pascal.
• efficient.
• Close to machine.
• familiar.
• The semantics of a program can be complex to understand or prove, because of referential transparency does not hold(due to side effects).
• Side effects also make debugging harder.
• Abstraction is more limited than with some paradigms.
• Order is crucial, which doesn't always suit itself to problems.

```#include <stdio.h>
void first()
{
printf("First Method");
}
void second()
{
printf("Second Method");
}
int main()
{
first();
second();
return 0;
}
```

• Logical Programming:
• The Logical Paradigm takes a declarative approach to problem-solving. Various logical assertions about a situation are made, establishing all known facts. Then queries are made. The role of the computer becomes maintaining data and logical deduction.
• A logical program is divided into three sections:
1. a series of definitions/declarations that define the problem domain.
2. statements of relevant facts.
3. statement of goals in the form of a query.
• The advantages of logic oriented programming are bi fold:
1. The system solves the problem, so the programming steps themselves are kept to a minimum.
2. Proving the validity of a given program is simple.

```domains
being = symbol

predicates
animal(being) % animals are good
dog(being) % all dogs are beings
die(being) % all beings die

clauses
animal(X) :- dog(X) % all dogs are    animals
dog(fido). % fido is a dog
die(X) :- animal(X) % all animals die
```

• Object Oriented Programming:
• Object Oriented Programming (OOP) is a paradigm in which real-world objects are each viewed as separate entities having their own state which is modified only by built in procedures, called methods.

Because objects operate independently, they are encapsulated into modules which contain both local environments and methods. Communication with an object is done by message passing.

Objects are organized into classes, from which they inherit methods and equivalent variables. The object-oriented paradigm provides key benefits of reusable code and code extensible.
• Features and Benefits
• A new class (called a derived class or subclass) may be derived from another class (called a base class or superclass) by a mechanism called inheritance. The derived class inherits all the features of the base class: its structure and behavior(response to messages). In addition, the derived class may contain additional state (instance variables), and may exhibit additional behavior (new methods to respond to new messages). Significantly, the derived class can also override behavior corresponding to some of the methods of the base class: there would be a different method to respond to the same message. Also, the inheritance mechanism is allowed even without access to the source code of the base class.

The ability to use inheritance is the single most distinguishing feature of the OOP paradigm. Inheritance gives OOP its chief benefit over other programming paradigms - relatively easy code reuse and extension without the need to change existing source code.

The mechanism of modeling a program as a collection of objects of various classes, and furthermore describing many classes as extensions or modifications of other classes, provides a high degree of modularity.

Ideally, the state of an object is manipulated and accessed only by that object's methods. (Most O-O languages allow direct manipulation of the state, but such access is stylistically discouraged). In this way, a class' interface (how objects of that class are accessed) is separate from the class' implementation (the actual code of the class' methods). Thus encapsulation and information hiding are inherent benefits of OOP.

```# python code for insertion sort
class InsertionSort:
def insertion_sort(self,lis):
for j in range(1,len(lis)):
key=lis[j]
i=j-1
while i>=0 and lis[i]>key: #  corrected the pseudocode i>=0
lis[i+1]=lis[i]
i=i-1
lis[i+1]=key
return lis

if __name__=='__main__':
li=[];count=0 # [6,5,4,3,2,1]
print "Enter any 6 numbers (Insertion Sort)"
while count<=5:
a=int(raw_input())
li.append(a)
count=count+1
Insort=InsertionSort()
na=Insort.insertion_sort(li)
print "The sorted list is: ",na
```

• Functional Programming:
• The Functional Programming paradigm views all subprograms as functions in the mathematical sense-informally, they take in arguments and return a single solution. The solution returned is based entirely on the input, and the time at which a function is called has no relevance. The computational model is therefore one of function application and reduction.
• Functional languages are created based on the functional paradigm. Such languages permit functional solutions to problems by permitting a programmer to treat functions as first-class objects(they can be treated as data, assumed to have the value of what they return; therefore, they can be passed to other functions as arguments or returned from functions).
The following are desirable properties of a functional language:
1. The high level of abstraction, especially when functions are used, supresses many of the details of programming and thus removes the possibility of commiting many classes of errors.
2. The lack of dependence on assignment operations, allowing programs to be evaluated in many different orders. This evaluation order independence makes function-oriented languages good candidates for programming massively parallel computers.
3. The absence of assignment operations makes the function-oriented programs much more amenable to mathematical proof and analysis than are imperative programs, because functional programs possess referential transparency.

```def calculate(x,y):
return (x*y)

print calculate(12,23)
```

## Monday, May 27, 2013

### Necessary aspects of Porting to Python3.x

Porting to Python 3.x

Python Software Foundation has announced that the Python 2.7 would be the last release and they would shift all the development work to Python 3.x. Still due to the popularity of Python 2.x the updates would come for some years. The Python Software Foundation success with the Python 2.x version should continue. The success among the developers it has is really great. Whosoever work on this language simply love it due to its small code , easy syntax that is understandable and extendibility and plug in behavior with other languages like C, C++ , Java , .net. Python has lots and lots of modules available that extends python capability to perform each and every specialized task and multiparadigm capability its has. All these were the benefits to use Python but still the version Python 2.x has some aspects that need cleanup.

According to Python Software Foundation Python 3.x will be more sophisticated language that the earlier versions.The guiding principle of Python 3 is: "reduce feature duplication by removing old ways of doing things". Python 3 concerned with "There should be one— and preferably only one —obvious way to do it".

Python3porting: http://python3porting.com/2to3.html
Python Wiki: http://wiki.python.org/moin/PortingPythonToPy3k

Current Development in Python 3.x

Python 2.x community is very large as compared to Python 3.x. Python 3.x is still under  development and we could see some great capability in Python 3.x in the near future Python 3.3 has been very good and presented some mature behavior to the developers that could be some of the great aspects to think about and really excites a developer to adopt the Python 3.3 codebase.

Porting to Python 3.x

Python 2 code can be ported to Python 3 using a tool called 2to3 that comes with every installation of Python 2. 2to3 typically refactors all the Parts that needs modification to run in Python 3.x . This tool was made to produce the diffrence of file that requires minimum changes to be done manually , But this tools is behaved incorrectly and therefore some manual changes are required to be done.
# 2to3 python_port.py This results in the following

 ```1 2 3 4 5``` ```--- python_port.py (original) +++ python_port.py (refactored) @@ -1 +1 @@ -print u'Using Python Programming for my Project' +print('Using Python Programming for my Project') ```

using 2to3 to port python 2.x code to Python 3.2.

2to3 docs: http://wiki.python.org/moin/2to3
2to3 project: http://wiki.python.org/moin/2to3

Now when you port there are options that to take up two different branches and then let the setup.py decide at runtime which branch to choose for installation based on Python version. But this would need to make simultaneous changes in two branches that would also be a troublesome job.

Use try-except blocks

So the best way is to take the same codebase make it as compatible as possible with python 2 and python 3 one way is to use try and except blocks like:

 ```1 2 3 4``` ```try: print "I am in Python 2" except SyntaxError: print("I am in Python 3") ```

but this would cause checking each time and thus exceptions are handled to make the Program run. Moreover this does not benefit a lot as this is not a generalized codebase this also requires troublesome code changes to be done in the both the blocks.

Use six module

This method says to use 2to3 as a refactoring tool and some manual changes would be required at that part of the code that needs to be changed now this part of the code is replaced by using six module.
consider an example below of the for loop running with xrange() now this would not run on Python 3.x as Python 3.x would only take range() as a function. But xrange() and range() function are different in working as.

xrange() : is a sequence object or generator that evaluates at each iteration.
range() : range creates a list so range(0,9) , list in memory with 10 elements.

so if we use the following piece of code this would not work on Python 3.x

 ```1 2``` ```for i in xrange(0,10): print("Now Value of i is: ",i) ```

so at the time of refactoring using try catch is not a good choice as it would make the code worse to read and understand to the most other people. so the same piece of code can be used with six module that would be error free and would run on both the Python versions is.

 ```1 2 3``` ```from six.moves import xrange for i in xrange(0,10): print("Now the value of i is: ",i) ```

Now the above code would be easy to read and customize as compared to the code written above with try and except blocks.

One more thing that six module lacks is unicode literals (u'' ) and when it comes to raw unicode literals (ur'' ) .

Why unicode are important than simple string literals ?

Normal strings in Python are stored internally as 8-bit ASCII, while Unicode strings are stored as 16-bit Unicode. This allows for a more varied set of characters, including special characters from most languages in the world. Now Here using six.u('example') which stands for unicode wrapping of a string would work good on Python 2.x as it has good supporting for unicode string literals, but Python 3.2 has no support for unicode string literals so after the inclusion of unicode in Python 3.3 , unicode support is established but not at that level as it should be:
there is no unicode() , unichr() methods present

six module docs: http://pythonhosted.org/six/

Using Python-Modernize

Python-modernize is a thin wrapper around lib2to3  and the code it generates has a runtime dependency  on six module. Python-modernize supports unicode literals well.

```Unicode Literal Control:

By default modernize will wrap literals with the six helpers.This is useful if you want to support Python 3.1 and Python 3.2 without bigger changes.
Alternatively there is the ``--compat-unicode`` flag which does not change unicode literals at all which means that you can take advantage of PEP 414.
The last alternative is the ``--future-unicode`` flag which imports the ``unicode_literals`` from the ``__future__`` module.This requires Python 2.6 and later and will require that you mark bytestrings with ``b''`` and native strings in ``str(b'')`` or something similar that survives the transformation.

```

Recent Events regarding Python 3.x Support

Recent Python 3 porting for jinja2  using Python-Modernize by Thomas Waldmann from MoinMoin has produced a good codebase that gave desired resultson both the versions of Python. So for planning regarding the porting one must see how jinja2 got ported.