Zenith: May 2013

Saturday, May 18, 2013

For in-depth understanding of Data Structure and Algorithm concepts refer :

1) INTRODUCTION TO ALGORITHMS by Coremen Introduction to Algorithms, 3rd Edition From flipkart.com
Introduction to Algorithms, 3rd Edition From amazon.com
Introduction to Algorithms from amazon.in

2) DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron - DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron from flipkart.com
Data Structures Using C and C++ (2nd Edition) from amazon.com
Data Structures Using C and C++ from amazon.in

#include<iostream.h>
#include<stdio.h>
#include<conio.h>

class node
{
    public:
        float info;
        node *next,*prev;
        node(){next=prev=0;}
        node(int n, node *ptr=0, node *ptr1=0)
        {
            info=n;
            next=ptr;
            prev=ptr1;
        }
};

/* sort the link list of elements*/
void isort(node *head)
{
    if (head == 0)
        return;
    float key;
    node *j,*i, *q=0;

    for(i=head->next;i!=0;i=i->next)
    {
        q=0;
        key = i->info;
        j=i->prev;
        while(j!=0 && key < (j->info) )
        {
            j->next->info=j->info;
            q = j;
            j=j->prev;
        }

        if(q!=0)
            q->info = key;
    }

}

void bucket_sort(float *a,int n)
{
    /* create buckets */
    node* *b = new node* [n];
    for(int i=0; i<n;i++)
        b[i]=0;

    /* step 2 begins - insert a[i] into buckets */
    for(int i=0;i<n;i++)
    {
        int index=n*a[i];

        node *temp=new node(sizeof(node));
        temp->info=a[i];

        if(b[index]==NULL)
        {
            b[index]=temp;
        }
        else
        {
            temp->next=b[index];
            b[index]->prev=temp;
            b[index]=temp;
        }
    } // end of for
    /* step 2 ends */

    /* step 3 begins - sort each bucket */
    for(int i=0; i<n;i++)
    {
        isort(b[i]);
    }
    /* step 3 ends */

    /* step 4 begins - concatenate all the buckets */
    node *trav=0;
    cout<<"\n\nSorted array is: \n";
    for(int i=0; i<n;i++)
    {
        trav = b[i];
        while(trav != 0)
        {
            cout<<trav->info<<" ";
            trav = trav->next;
        }
    }
    /* step 4 ends */
}

void main()
{
    clrscr();

    int n;
    float *a;

    cout<<"\n\t Enter the size of array : ";
    cin>>n;

    cout<<"\n\t Enter the elements of an array :\n";
    a=new float[n];
    for(int l=0;l<n;l++)
        cin>>a[l];

    cout<<"\n\t Unsorted array is..\n";
    for(l=0;l<n;l++)
        cout<<a[l]<<" ";
    cout<<"\n" ;

    /* sort lements using buckt sort */
    bucket_sort(a,n);

    getch();
}

Radix sort c++ code

priority queue c++ code

For in-depth understanding of Data Structure and Algorithm concepts refer :

1) INTRODUCTION TO ALGORITHMS by Coremen Introduction to Algorithms, 3rd Edition From flipkart.com
Introduction to Algorithms, 3rd Edition From amazon.com
Introduction to Algorithms from amazon.in

2) DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron - DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron from flipkart.com
Data Structures Using C and C++ (2nd Edition) from amazon.com
Data Structures Using C and C++ from amazon.in

#include<iostream.h>
#include<conio.h>
#include<process.h>
int n;
void maxheapinsert(int [],int key);
void heapincreasekey(int a[],int i,int key);
int heapextractmax(int a[]);
int prioritymaximum(int a[]);
void max_heapify(int a[20],int n1);
int heapsize;
int left(int i)
{
    return(2*i);
}
int right(int i)
{
    return((2*i)+1);
}
void max_heapify(int A[20],int i)
{
    int l,r,largest,s;
    l=left(i);
    r=right(i);

    if(l<=heapsize && A[l]>A[i])
        largest=l;
    else
        largest=i;

    if(r<=heapsize && A[r]>A[largest])
        largest=r;

    if(largest!=i)
    {
        s=A[i];
        A[i]=A[largest];
        A[largest]=s;
        max_heapify(A,largest);
    }
}
int prioritymaximum(int a[])
{

    return a[1];
}
int heapextractmax(int a[])
{
    if(n<0)
        cout<<"Underflow"<<endl;
    int max=a[1];
    a[1]=a[n];
    n--;
    max_heapify(a,1);
    return max;
}

void heapincreasekey(int a[],int i,int k)
{
    if(k<a[i])
        cout<<"New key is smaller than current key"<<endl;
    a[i]=k;
    while(i>1&&a[i/2]<a[i])
    {
        int t=a[i];
        a[i]=a[i/2];
        a[i/2]=t;
        i=i/2;
    }
}
void maxheapinsert(int a[],int k)
{
    n=n+1;
    a[n]=-999;
    heapincreasekey(a,n,k);
}

void main()
{
    int x,i2,c,key,a[20];
    a[0]=-999;
    int m;
    for( ; ; )
    {
        cout<<"Menu:"<<endl;
        cout<<"1:To get the maximum value"<<endl;
        cout<<"2:To extract maximum value"<<endl;
        cout<<"3:To increase key value"<<endl;
        cout<<"4:To insert new value"<<endl;
        cout<<"5:Exit:"<<endl;
        cout<<"Enter your choice"<<endl;
        cin>>c;
        switch(c)
        {
            case 1:
                x=prioritymaximum(a);
                cout<<x<<endl;
                break;
            case 2:
                m=heapextractmax(a);cout<<"process with priority "<<m<<" is being processed";
                break;
            case 3:
                cout<<"Enter the index value that is to modified "<<endl;
                cin>>i2;
                cout<<"Enter the new value"<<endl;
                cin>>key;
                heapincreasekey(a,i2,key);
                cout<<"Value modified"<<endl;
                break;
            case 4:
                cout<<"Enter the new value"<<endl;
                cin>>key;
                maxheapinsert(a,key);
                break;
            case 5:
                exit(0);
            default:
                cout<<"Wrong code"<<endl;
        }
    }
    getch();
}

Merge sort C++ code

Insertion sort C++ code

Tuesday, May 14, 2013

Time/Space complexity of sorting algorithms

Sorting

Algorithm	Data Structure	Time Complexity			Worst Case Auxiliary Space Complexity
		Best	Average	Worst	Worst
Quicksort	Array	`O(n log(n))`	`O(n log(n))`	`O(n^2)`	`O(log(n))`
Mergesort	Array	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	Array	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	Array	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	Array	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Select Sort	Array	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`
Bucket Sort	Array	`O(n+k)`	`O(n+k)`	`O(n^2)`	`O(nk)`
Radix Sort	Array	`O(nk)`	`O(nk)`	`O(nk)`	`O(n+k)`

Six Interesting Facebook Tricks That You Might Not Know

Almost everyone of us have now been using Facebook since years, but there are a lot of things that we still are unaware of. Here are 6 interesting tricks that you might not know about Facebook.

1.Trick to update blank status:

Simply enter @[3:3: ] in your status update box. To update your blank status as a long statement, paste the code one below another as showed below:
@[3:3: ]
@[3:3: ]
@[3:3: ]

2. Download Full Facebook Album in a single click:

Now you can download a full Facebook album in a single click. Just visit this app called Facebook2zip. Facebook2zip.com

3. Go offline for a particular person:

Instead of going offline for all of your friends, now you can go OFFLINE for a particular person. Just open that person's chat pane and click on the settings button. You'll find a button saying 'Turn off chat for xyz', just click and you are done.

4. Facebook status update from Desired Device (via iPhone without an iPhone):

Login to your Facebook account and update your status, just visit and search for your desired device on top right corner of the page: http://statusvia.org/apps/Facebook/

5. Update Facebook status with symbols:

Facebook status symbols do not have to use the inbuilt facility. But we're cool with the status message through the use of symbols is a Facebook trick. Just visit: http://fsymbols.com/all/
Then double click copy and paste the desired symbol in your status.

6. Post Facebook update in blue

Paste the below mentioned code in your status update box and write your text in place of 'your text':
@@[1:[0:1: your text]]

Source - http://www.efytimes.com/e1/fullnews.asp?edid=106004&ntype=mor&edate=5/14/2013

Tuesday, May 7, 2013

Search algorithms time complexity table

Searching

Algorithm	Data Structure	Time Complexity		Space Complexity
		Average	Worst	Worst
Depth First Search (DFS)	Graph of \|V\| vertices and \|E\| edges	`-`	`O(\|E\| + \|V\|)`	`O(\|V\|)`
Breadth First Search (BFS)	Graph of \|V\| vertices and \|E\| edges	`-`	`O(\|E\| + \|V\|)`	`O(\|V\|)`
Binary search	Sorted array of n elements	`O(log(n))`	`O(log(n))`	`O(1)`
Linear (Brute Force)	Array	`O(n)`	`O(n)`	`O(1)`
Shortest path by Dijkstra, using a Min-heap as priority queue	Graph with \|V\| vertices and \|E\| edges	`O((\|V\| + \|E\|) log \|V\|)`	`O((\|V\| + \|E\|) log \|V\|)`	`O(\|V\|)`
Shortest path by Dijkstra, using an unsorted array as priority queue	Graph with \|V\| vertices and \|E\| edges	`O(\|V\|^2)`	`O(\|V\|^2)`	`O(\|V\|)`
Shortest path by Bellman-Ford	Graph with \|V\| vertices and \|E\| edges	`O(\|V\|\|E\|)`	`O(\|V\|\|E\|)`	`O(\|V\|)`

Zenith