Monday, August 13, 2012

Switching From Perl to Python, Step 3 Python Data Structures

We read the Knuth, so you don't need to
-Tim Peters

After finishing first part of Python, today i decided to read about Python data structures.
Today's topics are:
Night -2-
10.  Modules
11.  Data Structures
12.  Problem Solving

While i was reading about the data structures in Python, list, tuple and dictionary implementations are very similar to corresponding Java collections list, set and map. Please check here to review some examples.

While reading about the dictionaries, defaultdict implementation was interesting, in addition, i really like the one liners, as an example:


myfile=open('names', 'r')
words=[line.rstrip() for line in myfile]
quote='''google
        excite
        yahoo
        bing
        altavista '''
#find the words that exits in file but not in quote
difference=[word for word in quote.split() if word not in words]
print difference

Some useful resources:
Python in High performance computing 
Official python documentation
Data Structures and Algorithms Using Python


Friday, August 10, 2012

Switching From Perl to Python, Step 2 Python Basics

 If you don't know any computer languages, I recommend starting with Python. It is cleanly designed, well documented, and relatively kind to beginners. Despite being a good first language, it is not just a toy; it is very powerful and flexible and well suited for large projects.
How To Become A Hacker, Eric Steven Raymond


From coffeeghost
Following topics are from Byte of Python which is a free Python book for completely beginners.
Today's topics:
Night -1-
1. → Translations
2. → Preface
3. → Introduction
4. → Installation
5. → First Steps
6. → Basics
7. → Operators and Expressions
8. → Control Flow
9. → Functions 

Resources that i have reviewed:

Switching From Perl to Python, Step 1 Which IDE to use for Python programming ?


 Python 2.x is the status quo, Python 3.x is the present and future of the language (http://wiki.python.org/moin/Python2orPython3)


i followed the instruction from vogella, however instead of installing python 2.7 directly from official python web page, i installed from enthought academic version which includes the numpy, Scipy and matplotlib. These modules will be useful when we start programming,
i do not give details for now.


Academic versions of Enthought:
Students or employees from degree-granting institutions may use these installations for an extended period free of cost.


After installing Eclipse and configuration of PyDev , i guess i'm ready for Python. Actually, i'd like to use netbeans instead but netbeans does not have python support after 7.0 versions.

Some experiments to be sure that everything works smoothly:

1-First (little) Python module (from vogella)

2- First (little)NumPy module
3-Scipy and Matplotlib module

Code is from oneau

Ok. then i'm ready for Night 1 for tomorrow:

1. → Translations
2. → Preface
3. → Introduction
4. → Installation
5. → First Steps
6. → Basics
7. → Operators and Expressions
8. → Control Flow
9. → Functions


Sunday, August 5, 2012

Binary Tree based algorithm questions


i will try to find the answers of following 4 algorithm questions which can be implemented using binary search tree (BST). Please refer to the original questions with the Python implementation at Arden's blog.
  • Binary Search Tree Check: Given a binary tree, check whether it’s a binary search tree or not
  • Tree Level Order Print: Given a binary tree of integers, print it in level order. The output will contain space between the numbers in the same level, and new line between different levels.
  • Tree Reverse Level Order Print: This is very similar to the previous post level order print. We again print the tree in level order, but now starting from bottom level to the root.
  • Trim Binary Search Tree: Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree.
To understand or polish your knowledge about BST, you can go over the great tutorial of Nick Parlenta and for the applications of binary trees you may read the answers posted in SO.

To implement BST in Java, we need to create class like:
 static class TreeNode {

        TreeNode leftReference;
        TreeNode rightReference;
        int nodeValue;

        public TreeNode(int nodeValue) {
            this.nodeValue = nodeValue;
        }
    }

With a given BST, there are 3 kind of walk can be defined, inorder tree walk, preorder tree walk and postorder tree walk. Refer to Wikipedia article to get details. While using inorder tree walk,  note that the BST property allows us to print out all the values in the Binary Search Tree in sorted order. Before, i start implementation we need to understand these terms in order to write the code.

we can implement inorder tree walk for binary search tree check and if BST is not sorted then we conclude that it's a not a BST. Both Tree Level Order Print and Tree Reverse Level Order Print can be implemented in similar way using recursion.

package pkg7binarysearchtreechk;

public class Main {

    static class TreeNode {

        TreeNode leftReference;
        TreeNode rightReference;
        int nodeValue;

        public TreeNode(int nodeValue) {
            this.nodeValue = nodeValue;
        }
    }

    public static void main(String[] args) {
        run();
    }

    public static void run() {
        // tree root node.
        int rootValue = 40;
        TreeNode rootnode = new TreeNode(rootValue);
        System.out.println("root node created, " + rootnode.nodeValue);
        // insertNode new element starting with rootnode.
        insertNode(rootnode, 11);
        insertNode(rootnode, 15);
        insertNode(rootnode, 16);
        insertNode(rootnode, 23);
        insertNode(rootnode, 79);
        
        System.out.println("print the content of  tree in inOrderTree walk");
        printTree(rootnode);
        System.out.println("print the content of  tree in preOrderTree walk");
        printPreOrderTree(rootnode);
        System.out.println("print the content of  tree in  postOrderTree walk");
        printPostOrderTree(rootnode);
    }

    private static void insertNode(TreeNode parentNode, int nodeValue) {
        if (nodeValue < parentNode.nodeValue) {
            if (parentNode.leftReference != null) {
                // Go more depth to left.
                insertNode(parentNode.leftReference, nodeValue);
            } else {
                System.out.println("LEFT: new node value " + nodeValue
                        + " ,its root  " + parentNode.nodeValue);
                parentNode.leftReference = new TreeNode(nodeValue);
            }
        } else if (nodeValue > parentNode.nodeValue) {

            if (parentNode.rightReference != null) {
                // Go more depth to right
                insertNode(parentNode.rightReference, nodeValue);
            } else {
                System.out.println("RIGHT: new node value  " + nodeValue + ", its root " + parentNode.nodeValue);
                parentNode.rightReference = new TreeNode(nodeValue);
            }
        }
    }

    // inorder tree walk
    private static void printTree(TreeNode node) {
        int comparison;
        if (node != null) {
            printTree(node.leftReference);
            comparison = node.nodeValue;
            if (comparison < node.nodeValue) {
                System.out.println("Error not BST");
            }
            System.out.println("node value  " + node.nodeValue);
            printTree(node.rightReference);
        }
    }
    
  // preorder tree walk 
    private static void printPreOrderTree(TreeNode node) {
        if (node != null) {
            System.out.println("node value  " + node.nodeValue);
            printTree(node.leftReference);
            printTree(node.rightReference);
        }
    }
  // postorder tree walk
     private static void printPostOrderTree(TreeNode node) {
        if (node != null) {
            printTree(node.leftReference);
            printTree(node.rightReference);
            System.out.println("node value  " + node.nodeValue);
        }
    }
}