Algorithms- Getting started

To learn the analysis of algorithms and to dive in the study of complexity for algorithms few mathematical concepts are required and used in almost all cases.
I am presenting few concepts in simple manner, so a beginner  can grasp it easily and use it in further study of algorithms.
Asymptotic notations:

Asymptotic notations

Big O notation  (middle image in above figure):
O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}.
It specifies that function gives a upper bound on the complexity of the algorithm and it's the highest value that an algorithm could achieve and not depends on any particular condition, whatever is the input its the highest bound on the time.
whenever we write f(n) = O(g(n)) then f(n) is upper bounded by g(n), it means g(n) is having more value than f(n) or in other words{though not technically correct, we can write value of f(n)<= g(n)}.

Θ-notation :(First image in above fig.)
Θ(g(n)) = {f(n) : there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}.
function f(n) is sandwiched between g(n) for any two arbitrary constants c1 and c2 such that for any value(eg c1=1/2) f(n) is smaller than g(n) as well as for any other value (eg c2=3/2) f(n) is greater than g(n).
Θ notation is more stronger than O notation and we can write Θ subset of O.
The definition of Θ(g(n)) requires that every member f(n) Θ(g(n)) be asymptotically non-negative, that is, that f(n) be non-negative whenever n is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large n.) Basically it is all related to set theory and we denote each set as a set of functions and complexity is based only for positive functions only.

Ω-notation: (Last image in above fig.) :
Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ no}.
it means function f(n) is greater than g(n) for a sufficient value of constant c.

Few facts:

• The constants(c1,c2 etc)  mentioned in each case should be only numerical constants and should not be any exponential or any other value , for example :

2ⁿ⁺¹== O(2ⁿ) but  2²ⁿ != O(2ⁿ) because  we can write 2ⁿ⁺¹  as 2*2ⁿ and consider 2 as constant(c1) but in case of  2²ⁿ  ,it can be written as 2ⁿ *2ⁿ and here 2ⁿ cannot be considered as a constant. So it can’t be considered as O(2ⁿ).

• f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n))  because in that way only it will be upper bounded by g(n) as well as lower bounded by g(n) for any constants c1,c2.
• We generally neglect lower order terms for analyzing the complexity of algorithm. eg( an²+bn+c)  could be written as O(n²))

Floors and ceilings:
floor(x) =  is the largest integer not greater than x and ceiling(x) =  is the smallest integer not less than x.
for example floor(9.6)=9 and ceiling(9.6)=10.

Complexity Analysis

I am presenting simple comlexity analysis of algorithms for that I'll use Insertion sort algorithm:

Insertion sort algo:

Insertion Sort(Array A)


 for int j=2 to A.length{    // it will loop through for n times, cost= c1*n

  key=A[j]   // it will loop for n-1 times, cost= c2*(n-1)

  i=j-1;   // it will loop for n-1 times, cost= c3*(n-1)    

  while( i>0 && A[i]> key){  // depends on condition being true, cost= c4 *(∑ tj where j=2 to n)

  A[i+1]= A[i];   //cost= c5 *(∑ tj-1 where j=2 to n)

  i--;   // cost= c6 *(∑ tj-1 where j=2 to n)

 }

  A[i+1]=key;   // cost= c7 *(n-1)

}

where all c1,c2 etc are constants, so the total time to excute this algorothms would be:
T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(∑ tj where j=2 to n)+ c5 *(∑ tj-1 where j=2 to n)+ c6 *(∑ tj-1 where j=2 to n)+c7 *(n-1)

In the worst case the inner while loop will execute for each element and hence will sum up as:
(∑ tj-1 where j=2 to n) = 1+2+3+4+-------+n-1 =  n*(n-1)/2
that will be equal to n^2.

So  now T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(n^2)+ c5*(n^2)+ c6*(n^2)+c7 *(n-1)

and since n^2 is the maximum term , ignoring lower order terms will give us :
T(n)=O(n^2).

This approach is very useful in analysis of all the algorithms which uses loops and gives basic idea of how to derive complexity.
Post comments if you face any issue to analyze complexity or any problems in this method to follow.

Connecting ad-hoc network from android devices

Connecting ad-hoc network from android devices 

I was trying to connect my android device using ad-hoc network on windows 7 and to my surprise android is not capable to discover ad-hoc network created by windows.

I tried to Google it and can't find much information.

So here is the solution : 

Microsoft included a virtual WiFi feature in Windows 7, so one can use this feature and turn network as a hot-spot for WiFi access.

There are two methods through which one can enable WiFi on windows 7 and the easiest one is using open source software such as Virtual router manager:

Download software from  http://virtualrouter.codeplex.com/

Using its GUI:

It's very simple to create a WiFi connection and then use it :)

-----------------------------------------------------------------------------------------------------------------

Another way of doing it by using command prompt:

Use a command-line tool called Netsh to create and manage the virtual router

First, enable the Internet Connection Sharing (ICS) feature of Windows 7 so the Internet access is shared with users on the Wireless Hosted Network.

Open the Network Connections window, right-click the network adapter that's connected to the Internet and select Properties. Then select the Sharing tab, check the Allow other network users to connect through this computer's Internet connection, choose the network connection name of the Microsoft Virtual WiFi Miniport Adapter from the drop-down box, and click OK.

Now open the Command Prompt: click Start > All Programs > Accessories > Command Prompt.

Set the network details:

netsh wlan set hostednetwork mode=allow ssid=YourVirtualNetworkName key=YourSecureNetworkPassword

Start the Wireless Hosted Network:

netsh wlan start hostednetwork

To stop the Wireless Hosted Network:

netsh wlan stop hostednetwork

To see the Wireless Hosted Network details, including the MAC addresses of connected users:

netsh wlan show hostednetwork

Enjoy WiFi on mobile and other devices :)

Probability puzzle

Puzzle: Given 50 white marbles, 50 black marbles, and 2 boxes, put the marbles into the boxes to maximize the chances of selecting a black marble.

Sol: probability to select a box would be 1/2, so if we put 50 marbles in a box and other 50 in other box then probability to select black marble will be:
0.5*1 + 0.5*0 = 50%
Instead we can improve it by putting 1 black marble in a box and other 49 B+50 W marbles in other box.
Now probability for selecting a black marble will improve:
0.5*1 + 0.5*(49/99)= 74.5 %
and that is a significant improvement from previous 50%.

Please comment if it could be more improved.

Diameter and maximum distance between two nodes in a Binary tree.

/*
  Function to find out maximum distance between two nodes in a binary tree.
  Ds for tree could be found here: Ds for Tree
*/

public int height(Node root){

        if(root==null)

            return 0;

        else

            return (1+max(height(root.getLeft()),height(root.getRight())));

    }

    

    public int max(int a, int b){

        return a>b?a:b;

    }

    

    public int diameter(Node root){

        if(root==null)

            return 0;

        else{

            int lh=height(root.getLeft());

            int rh=height(root.getRight());

            

            int ld=diameter(root.getLeft());

            int rd=diameter(root.getRight());

            

            return( max(1+lh+rh,max(ld,rd)));  //add 1 to the result if counting current node as well.

        }           

    }   

Iterative inorder tree traversal-Morris traversal

/*
   Morris traversal in Java:
   Inorder tree traversal without recursion.
   Helper class for Tree data-structure could be found here: DS for Tree
  
*/

/**
 * MorrisTraversal.java
 *
 */

/**
 * @author vikky.agrawal
 *
 */
public class MorrisTraversal {

    private TreeNode root;

    MorrisTraversal() {
        root = new TreeNode(49);
    }

    public static void main(String args[]) {
        new MorrisTraversal().traverse();
    }

    public void traverse() {
        System.out.println("Building tree with root value " + root.getData());
        for (int i = 0; i < 7; i++)
            this.insert(root, (int) (Math.random() * 100));
        this.morrisTraverse(root);

    }

    /**
     * Iterative inorder traversal using Morris traverse
     * 
     * @param root
     */
    public void morrisTraverse(TreeNode root) {

        while (root != null) {
            if (root.getLeft() == null) {
                System.out.println(root.getData());
                root = root.getRight();
            } else {
                TreeNode ptr = root.getLeft();

                while (ptr.getRight() != null && ptr.getRight() != root)
                    ptr = ptr.getRight();

                if (ptr.getRight() == null) {
                    ptr.setRight(root);
                    root = root.getLeft();
                }

                else {
                    ptr.setRight(null);
                    System.out.println(root.getData());
                    root = root.getRight();
                }
            }
        }
    }

    // Insertion as BST
    public void insert(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        } else {
            if (val < root.getData()) {
                if (root.getLeft() == null) {
                    System.out.println("inserting left to :" + root.getData()
                            + " val : " + val);
                    root.setLeft(new TreeNode(val));
                } else {
                    insert(root.getLeft(), val);
                }
            } else {
                if (root.getRight() == null) {
                    System.out.println("inserting right to :" + root.getData()
                            + " val : " + val);
                    root.setRight(new TreeNode(val));
                } else {
                    insert(root.getRight(), val);
                }
            }
        }
    }

    // DS for tree
    private static class TreeNode {

        private int data;
        private TreeNode right;
        private TreeNode left;

        TreeNode() {
        }

        TreeNode(int data) {
            this.setData(data);
            this.setLeft(null);
            this.setRight(null);
        }

        public int getData() {
            return this.data;
        }

        public TreeNode getRight() {
            return this.right;
        }

        public TreeNode getLeft() {
            return this.left;
        }

        public void setData(int data) {
            this.data = data;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }
    }

}

DS for tree and link list

public class Node {
private int data;
 private Node right;
 private Node left;

 Node() {
 }

 Node(int data) {
  this.setData(data);
  this.setLeft(null);
  this.setRight(null);
 }

 public int getData() {
  return this.data;
 }

 public Node getRight() {
  return this.right;
 }

 public Node getLeft() {
  return this.left;
 }

 public void setData(int data) {
  this.data = data;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public void setLeft(Node left) {
  this.left = left;
 }
}




/* Helper class for all Linked list data structures */

class LinkNode {

 private int data;
 private LinkNode link;

 LinkNode() {
 }

 LinkNode(int data) {
  this.setData(data);
  this.setLink(null);
 }

 public int getData() {
  return this.data;
 }

 public LinkNode getLink() {
  return this.link;
 }

 public void setData(int data) {
  this.data = data;
 }

 public void setLink(LinkNode link) {
  this.link = link;
 }
}