Learn. Share. Improve.

Data Structure: Implementing Circular Queue in C++

Data Structure: Implementing Priority Queue in C++

Data Structure: Binary Search Tree

Programming: Cpp Program to Implement Queue Using Linked Lists

Programming: C++ Program to Implement Stack Using Linked List

Programming: C++ program to implement Heap

Programming: C++ Program to Implement Hash Table

Programming: C Program to Represent Graph Using Adjacency Matrix

What is the difference between VoIP and VoLTE?

Knowledge: Some good computer tricks 2

Knowledge: Some good computer tricks

GSM: Difference between UMTS SIM (USIM) and GSM SIM

GSM: Why is the channel spacing in GSM 900 just 200KHz?

Programming: Reverse a stack using Recursion

Programming: C program to print all permutations of a given string

[Knowledge]: How are images displayed on screen by code ?

Algorithm: Inorder Tree Traversal without Recursion

Programming: Reverse alternate K nodes in a Singly Linked List

Programming: Print 100 to 1 without using any loops in the program

Programming: Variable Storage Classes

Programming: Converting Decimal into Binary & Binary Into Decimal

Programming: Finding first non-repeating character in given string [Improved Method]

Programming: Finding first non-repeating character in given string

Data Structures: Graph - Adjacency Matrix

Data Structures: Graph Concepts

Learn. Share. Improve.

Data Structure: Implementing Circular Queue in C++

Data Structure: Implementing Priority Queue in C++

Data Structure: Binary Search Tree

Programming: Cpp Program to Implement Queue Using Linked Lists

Programming: C++ Program to Implement Stack Using Linked List

Programming: C++ program to implement Heap

Programming: C++ Program to Implement Hash Table

Programming: C Program to Represent Graph Using Adjacency Matrix

What is the difference between VoIP and VoLTE?

Knowledge: Some good computer tricks 2

Knowledge: Some good computer tricks

GSM: Difference between UMTS SIM (USIM) and GSM SIM

GSM: Why is the channel spacing in GSM 900 just 200KHz?

Programming: Reverse a stack using Recursion

Programming: C program to print all permutations of a given string

[Knowledge]: How are images displayed on screen by code ?

Algorithm: Inorder Tree Traversal without Recursion

Programming: Reverse alternate K nodes in a Singly Linked List

Programming: Print 100 to 1 without using any loops in the program

Programming: Variable Storage Classes

Programming: Converting Decimal into Binary & Binary Into Decimal

Programming: Finding first non-repeating character in given string [Improved Method]

Programming: Finding first non-repeating character in given string

Data Structures: Graph - Adjacency Matrix

Data Structures: Graph Concepts

Optimization Hint: `register`

Static Storage: `static`

External References: `extern`

Private Variables: `static`

Variable Initialization

Optimization Hint: register

Static Storage: static

External References: extern

Private Variables: static

Variable Initialization

Optimization Hint: `register`

Static Storage: `static`

External References: `extern`

Private Variables: `static`

Output of the above program:

Output of the above program:

The diagram shows recursive execution of permute()

The diagram shows recursive execution of permute()

2015-10-19T11:51:00.001-07:00

Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node is connected back to the first node to make a circle. Circular linked list fallow the First In First Out principle. Elements are added at the rear end and the elements are deleted at front end of the queue.

This C++ Program demonstrates the implementation of Circular Queue.
Here is source code of the C++ Program to demonstrate the implementation of Circular Queue. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C++ Program to Implement Circular Queue
 */
#include < iostream >
#define MAX 5
using namespace std;
/*
 * Class Circular Queue
 */
class Circular_Queue
{
    private:
        int *cqueue_arr;
        int front, rear;
    public:
        Circular_Queue()
        {
            cqueue_arr = new int [MAX];
            rear = front = -1;
        }
        /*
         * Insert into Circular Queue
         */
        void insert(int item)
        {
            if ((front == 0 && rear == MAX-1) || (front == rear+1))
            {
                cout << "Queue Overflow \n";
                return;
            }
            if (front == -1)
            {
                front = 0;
                rear = 0;
            }
            else
            {
                if (rear == MAX - 1)
                    rear = 0;
                else
                    rear = rear + 1;
            }
            cqueue_arr[rear] = item ;
        }
        /*
         * Delete from Circular Queue
         */
        void del()
        {
            if (front == -1)
            {
                cout << "Queue Underflow\n";
                return ;
            }
            cout << "Element deleted from queue is : " << cqueue_arr[front] << endl;
            if (front == rear)
            {
                front = -1;
                rear = -1;
            }
            else
            {
                if (front == MAX - 1)
                    front = 0;
                else
                    front = front + 1;
            }
        }
        /*
         * Display Circular Queue
         */
        void display()
        {
            int front_pos = front, rear_pos = rear;
            if (front == -1)
            {
                cout << "Queue is empty\n";
                return;
            }
            cout << "Queue elements :\n";
            if (front_pos <= rear_pos)
            {
                while (front_pos <= rear_pos)
                {
                    cout<> choice;
        switch(choice)
        {
        case 1:
            cout << "Input the element for insertion in queue : ";
            cin >> item;	
            cq.insert(item);
	    break;
	case 2:
            cq.del();
	    break;
        case 3:
            cq.display();
	    break;
	case 4:
	    break;
	default:
	    cout << "Wrong choice\n";
	}/*End of switch*/
    }
    while(choice != 4);
    return 0;
}

Output

$ g++ circular_queue.cpp
$ a.out
 
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the element for insertion in queue : 3
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the element for insertion in queue : 2
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the element for insertion in queue : 6
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the element for insertion in queue : 4
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the element for insertion in queue : 1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue elements :
3  2  6  4  1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 2
Element deleted from queue is : 3
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue elements :
2  6  4  1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 4
 
------------------
(program exited with code: 1)
Press return to continue

2015-10-19T10:21:00.000-07:00

A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
More info: Wikipedia Link

This C++ Program demonstrates the implementation of Priority Queue.
Here is source code of the C++ Program to demonstrate the implementation of Priority Queue. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C++ Program to Implement Priority Queue
 */
#include < iostream >
#include < cstdio >
#include < cstring >
#include < cstdlib >
using namespace std;
 
/*
 * Node Declaration
 */
struct node
{
 int priority;
 int info;
 struct node *link;
};
/*
 * Class Priority Queue
 */
class Priority_Queue
{
    private:
        node *front;
    public:
        Priority_Queue()
        {
            front = NULL;
        }
        /*
         * Insert into Priority Queue
         */
        void insert(int item, int priority)
        {
            node *tmp, *q;
            tmp = new node;
            tmp->info = item;
            tmp->priority = priority;
            if (front == NULL || priority < front->priority)
            {
                tmp->link = front;
                front = tmp;
            }
            else
            {
                q = front;
                while (q->link != NULL && q->link->priority <= priority)
                    q=q->link;
                tmp->link = q->link;
                q->link = tmp;
            }
        }
        /*
         * Delete from Priority Queue
         */
        void del()
        {
            node *tmp;
            if(front == NULL)
                cout << "Queue Underflow\n";
            else
            {
                tmp = front;
                cout << "Deleted item is: " << tmp->info << endl;
                front = front->link;
                free(tmp);
            }
        }
        /*
         * Print Priority Queue
         */
        void display()
        {
            node *ptr;
            ptr = front;
            if (front == NULL)
                cout << "Queue is empty\n";
            else
            { cout << "Queue is :\n";
                cout << "Priority       Item\n";
                while(ptr != NULL)
                {
                    cout << ptr->priority << "                 " << ptr->info << endl;
                    ptr = ptr->link;
                }
            }
        }
};
/*
 * Main
 */
int main()
{
    int choice, item, priority;
    Priority_Queue pq; 
    do
    {
        cout << "1.Insert\n";
        cout << "2.Delete\n";
        cout << "3.Display\n";
        cout << "4.Quit\n";
        cout << "Enter your choice : "; 
        cin >> choice;
        switch(choice)
        {
        case 1:
            cout << "Input the item value to be added in the queue : ";
            cin >> item;
            cout << "Enter its priority : ";
            cin >> priority;
            pq.insert(item, priority);
            break;
        case 2:
            pq.del();
            break;
        case 3:
            pq.display();
            break;
        case 4:
            break;
        default :
            cout << "Wrong choice\n";
        }
    }
    while(choice != 4);
    return 0;
}

Output

$ g++ priority_queue.cpp
$ a.out
 
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 4
Enter its priority : 2
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 3
Enter its priority : 3
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 2
Enter its priority : 4
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Input the item value to be added in the queue : 1
Enter its priority : 5
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority       Item
1                 5
2                 4
3                 3
4                 2
5                 1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 2
Deleted item is: 5
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
Priority       Item
2                 4
3                 3
4                 2
5                 1
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 4
 
------------------
(program exited with code: 1)
Press return to continue

2015-10-18T09:43:00.005-07:00

Until now all data structures that we have covered (Stack,Queue,Linked List) are linear in nature ie. they have a definite order of placement. Now we shall study Binary Trees which requires a different thought process as it is a non linear data structure.

A Binary Tree consists of a main node known as the Root. The Root then has two sub-sections, ie. the left and the right half. The data subsequently stored after the root is created depends on it's value compared to the root. Suppose the root value is 10 and the Value to be added is 15, then the data is added to the right section of the root. The Basic idea is that every node can be thought of a binary tree itself. Each node has two pointers, one to the left and the other to the right. Depending on the value to be stored, it is placed after a node's right pointer if the value of the node is lesser than the one to be added or the node's left pointer if vice versa.

Let's take an Example. To add the Following List of Numbers, we end up with a Binary Tree like this:

32 16 34 1 87 13 7 18 14 19 23 24 41 5 53

Here's How:
**: KEEP ADDING DATA IN THE TREE ON PAPER AFTER EACH STEP BELOW TO UNDERSTAND HOW THE TREE IS FORMED.
(1). Since 32 is the First Number to be added, 32 becomes the root of the tree.
(2). Next Number is 16 which is lesser than 32 Hence 16 becomes left node of 32.
(3). 34. Since 34 > 32 , 34 becomes the right node of the ROOT.
(4). 1. Since 1 < 32 we jump to the left node of the ROOT. But since the left node
has already been taken we test 1 once again. Since 1 < 16, 1 becomes the left
node of 16.
(5). 87. Since 87 > 32 we jump to the right node of the root. Once again this
space is occupied by 34. Now since 87 > 34, 87 becomes the right node of 34.
(6). 13. Since 13 < 32 we jump to left node of the root. There, 13 < 16 so we
continue towards the left node of 16. There 13 > 1, so 13 becomes the right
node of 1.
(7). Similarly work out addition till the end ie. before Number 53.
(8). 53. Since 53 > 32 we jump to the right node of the root. There 53 > 34 so we
continue to the right node of 34. There 53 < 87 so we continue towards the
left node of 87. There 53 > 41 so we jump to the right node of 41. Since the
Right node of 41 is empty 53 becomes the right node of 41.

This should give you an idea of how a Binary Tree works. You must know that:
(1). The linking of nodes to nodes in a Binary Tree is one to one in nature
ie. a node cannot be pointed by more than 1 node.
(2). A Node can point to two different sub-nodes at the most.
Here in the binary tree above there are a few nodes whose left and right
pointers are empty ie. they have no sub-node attached to them. So Nodes 5,14,18,
19,23,24,41 have their left nodes empty.

There are three popular ways to display a Binary Tree. Displaying the trees contents is known as transversal. There are three ways of transversing a tree iw. in inorder, preorder, and postorder transversal methods. Description of each is shown below:

PREORDER:

Visit the root.
Transverse the left leaf in preorder.
Transverse the right leaf in preorder.

INORDER:

Transverse the left leaf in inorder.
Visit the root.
Transverse the right leaf in inorder.

POSTORDER:

Transverse the left leaf in postorder.
Transverse the right leaf in postorder.
Visit the root.

Writing code for these three methods are simple if we understand the recursive nature of a binary tree. Binary tree is recursive, as in each node can be thought of a binary tree itself. It's just the order of displaying data that makes a difference for transversal.

Deletion from a Binary Tree is a bit more difficult to understand. For now just remember that for deleting a node, it is replaced with it's next inorder successor. I'll explain everything after the Binary Tree code. Now that you've got all your Binary Tree Fundas clear, let's move on with the Source code.

#include < iostream >

using namespace std;

#define YES 1
#define NO 0

class tree
{
	private:
		struct leaf
		{
			int data;
			leaf *l;
			leaf *r;
		};
		struct leaf *p;

	public:
		tree();
		~tree();
		void destruct(leaf *q);
		tree(tree& a);
		void findparent(int n,int &found,leaf* &parent);
		void findfordel(int n,int &found,leaf *&parent,leaf* &x);
		void add(int n);
		void transverse();
		void in(leaf *q);
		void pre(leaf *q);
		void post(leaf *q);
		void del(int n);
};
		
tree::tree()
{
	p=NULL;
}

tree::~tree()
{
	destruct(p);
}

void tree::destruct(leaf *q)
{
	if(q!=NULL)
	{
		destruct(q->l);
		del(q->data);
		destruct(q->r);
	}
}
void tree::findparent(int n,int &found,leaf *&parent)
{
	leaf *q;
	found=NO;
	parent=NULL;

	if(p==NULL)
		return;

	q=p;
	while(q!=NULL)
	{
		if(q->data==n)
		{
			found=YES;
			return;
		}
		if(q->data > n)
		{
			parent=q;
			q=q->l;
		}
		else
		{
			parent=q;
			q=q->r;
		}
	}
}

void tree::add(int n)
{
	int found;
	leaf *t,*parent;
	findparent(n,found,parent);
	if(found==YES)
		cout << "\nSuch a Node Exists";
	else
	{
		t=new leaf;
		t->data=n;
		t->l=NULL;
		t->r=NULL;

		if(parent==NULL)
			p=t;
		else
			parent->data > n ? parent->l=t : parent->r = t;
	}
}

void tree::transverse()
{
	int c;
	cout << "\n1.InOrder\n2.Preorder\n3.Postorder\nChoice: ";
	cin >> c;
	switch(c)
	{
		case 1:
			in(p);
			break;

		case 2:
			pre(p);
			break;

		case 3:
			post(p);
			break;
	}
}

void tree::in(leaf *q)
{
	if(q!=NULL)
	{
		in(q->l);
		cout << "\t"<data<r);
	}
	
}

void tree::pre(leaf *q)
{
	if(q!=NULL)
	{
		cout << "\t"<data<l);
		pre(q->r);
	}
	
}

void tree::post(leaf *q)
{
	if(q!=NULL)
	{
		post(q->l);
		post(q->r);
		cout << "\t"<data<data==n)
		{
			found=1;
			x=q;
			return;
		}
		if(q->data>n)
		{
			parent=q;
			q=q->l;
		}
		else
		{
			parent=q;
			q=q->r;
		}
	}
}

void tree::del(int num)
{
	leaf *parent,*x,*xsucc;
	int found;

	// If EMPTY TREE
	if(p==NULL)
	{
		cout << "\nTree is Empty";
		return;
	}
	parent=x=NULL;
	findfordel(num,found,parent,x);
	if(found==0)
	{
		cout<<"\nNode to be deleted NOT FOUND";
		return;
	}

	// If the node to be deleted has 2 leaves
	if(x->l != NULL && x->r != NULL)
	{
		parent=x;
		xsucc=x->r;

		while(xsucc->l != NULL)
		{
			parent=xsucc;
			xsucc=xsucc->l;
		}
		x->data=xsucc->data;
		x=xsucc;
	}

	// if the node to be deleted has no child
	if(x->l == NULL && x->r == NULL)
	{
		if(parent->r == x)
			parent->r=NULL;
		else
			parent->l=NULL;

		delete x;
		return;
	}

	// if node has only right leaf
	if(x->l == NULL && x->r != NULL )
	{
		if(parent->l == x)
			parent->l=x->r;
		else
			parent->r=x->r;

		delete x;
		return;
	}

	// if node to be deleted has only left child
	if(x->l != NULL && x->r == NULL)
	{
		if(parent->l == x)
			parent->l=x->l;
		else
			parent->r=x->l;

		delete x;
		return;
	}
}

int main()
{
	tree t;
	int data[]={32,16,34,1,87,13,7,18,14,19,23,24,41,5,53};
	for(int iter=0 ; iter < 15 ; i++)
		t.add(data[iter]);

	t.transverse();
	t.del(16);
	t.transverse();
	t.del(41);
	t.transverse();
	return 0;
}

Output

1.InOrder
2.Preorder
3.Postorder
Choice: 1
1
5
7
13
14
16
18
19
23
24
32
34
41
53
87

1.InOrder
2.Preorder
3.Postorder
Choice: 2
32
18
1
13
7
5
14
19
23
24
34
87
41
53

1.InOrder
2.Preorder
3.Postorder
Choice: 3
5
7
14
13
1
24
23
19
18
53
87
34
32
Press any key to continue

NOTE: Visual C++ may give Runtime Errors with this code. Compile with Turbo C++.

Just by looking at the output you might realise that we can print out the whole tree in ascending order by using inorder transversal. Infact Binary Trees are used for Searching [ Binary Search Trees {BST} ] as well as in Sorting. The Addition of data part seems fine. Only the deletion bit needs to be explained.

For deletion of data there are a few cases to be considered:
1. If the leaf to be deleted is not found.
2. If the leaf to be deleted has no sub-leafs.
3. If the leaf to be deleted has 1 sub-leaf.
4. If the leaf to be deleted has 2 sub-leafs.

CASE 1:
Dealing with this case is simple, we simply display an error message.

CASE 2:
Since the node has no sub-nodes, the memory occupied by this should be freed and either the left link or the right link of the parent of this node should be set to NULL. Which of these should be set to NULL depends upon whether the node being deleted is a left child or a right child of its parent.

CASE 3:
In the third case we just adjust the pointer of the parent of the leaf to be deleted such that after deletion it points to the child of the node being deleted.

CASE 4:
The last case in which the leaf to be deleted has to sub-leaves of its own is rather complicated.The whole logic is to locate the inorder successor, copy it's data and reduce the problem to simple deletion of a node with one or zero leaves. Consider in the above program...(Refer to the previous tree as well) when we are deleting 16 we search for the next inorder successor. So we simply set the data value to 5 and delete the node with value 5 as shown for cases 2 and 3.

2015-10-17T12:31:00.002-07:00

This C++ program, using iteration, implements the list of elements removed from the queue in first in first out mode using a linked list. A linked list is an ordered set of data elements, each containing a link to its successor.

Here is the source code of the C program to display the list of elements removed from the queue. The C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.

/*
 * C++ Program to Implement Queue using Linked List
 */
#include < iostream >
#include < stdio.h >
#include < conio.h >
using namespace std;
struct node
{
    int data;
    node *next;
}*front = NULL,*rear = NULL,*p = NULL,*np = NULL;
void push(int x)
{
    np = new node;
    np->data = x;
    np->next = NULL;
    if(front == NULL)
    {
        front = rear = np;
        rear->next = NULL;
    }
    else
    {
        rear->next = np;
        rear = np;
        rear->next = NULL;
    }
}
int remove()
{
    int x;
    if(front == NULL)
    {
        cout << "empty queue\n";
    }
    else
    {
        p = front;
        x = p->data;
        front = front->next;
        delete(p);
        return(x);
    }
}
int main()
{
    int n,c = 0,x;
    cout << "Enter the number of values to be pushed into queue\n";
    cin >> n;
    while (c < n)
    {
 cout << "Enter the value to be entered into queue\n";
 cin >> x;
        push(x);
        c++;
     }
     cout << "\n\nRemoved Values\n\n";
     while(true)
     {
        if (front != NULL)
            cout << remove() << endl;
        else
            break;
     }
     getch();
}

Output of above program

Output
Enter the number of values to be pushed into queue
6
Enter the value to be entered into queue
5
Enter the value to be entered into queue
4
Enter the value to be entered into queue
3
Enter the value to be entered into queue
2
Enter the value to be entered into queue
1
Enter the value to be entered into queue
0
 
Removed Values
 
5
4
3
2
1
0

2015-10-17T12:16:00.003-07:00

This C++ program, using iteration, implements the list of elements removed from the stack in last in first out mode using a linked list. A linked list is an ordered set of data elements, each containing a link to its successor.

Here is the source code of the C++ program to display the list of elements removed from the stack. The C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.

*
 * C++ Program to Implement Queue using Linked List
 */
#include < iostream >
#include < stdio.h >
#include < conio.h >
using namespace std;
struct node
{
    int data;
    node *next;
}*front = NULL, *rear = NULL, *p = NULL, *np = NULL;
void push(int x)
{
    np = new node;
    np->data = x;
    np->next = NULL;
    if(front == NULL)
    {
        front = rear = np;
        rear->next = NULL;
    }
    else
    {
        rear->next = np;
        rear = np;
        rear->next = NULL;
    }
}
int remove()
{
    int x;
    if (front == NULL)
    {
        cout << "empty queue\n";
    }
    else
    {
        p = front;
        x = p->data;
        front = front->next;
        delete(p);
        return(x);
    }
}
int main()
{
    int n, c = 0, x;
    cout << "Enter the number of values to be pushed into queue\n";
    cin >> n;
    while (c < n)
    {
 cout << "Enter the value to be entered into queue\n";
 cin >> x;
        push(x);
        c++;
    }
    cout << "\n\nRemoved Values\n\n";
    while(true)
    {
        if (front != NULL)
            cout << remove() << endl;
 else
     break;
    }
    getch();
}

Here is the output of the program:

Output
Enter the number of values to be pushed into queue
6
Enter the value to be entered into queue
5
Enter the value to be entered into queue
4
Enter the value to be entered into queue
3
Enter the value to be entered into queue
2
Enter the value to be entered into queue
1
Enter the value to be entered into queue
0
 
Removed Values
 
5
4
3
2
1
0

2015-10-15T10:50:00.002-07:00

A heap is a partially sorted binary tree. Although a heap is not completely in order, it conforms to a sorting principle: every node has a value less (for the sake of simplicity, we will assume that all orderings are from least to greatest) than either of its children. Additionally, a heap is a "complete tree" -- a complete tree is one in which there are no gaps between leaves. For instance, a tree with a root node that has only one child must have its child as the left node. More precisely, a complete tree is one that has every level filled in before adding a node to the next level, and one that has the nodes in a given level filled in from left to right, with no breaks.

Why use a heap?

A heap can be thought of as a priority queue; the most important node will always be at the top, and when removed, its replacement will be the most important. This can be useful when coding algorithms that require certain things to processed in a complete order, but when you don't want to perform a full sort or need to know anything about the rest of the nodes. For instance, a well-known algorithm for finding the shortest distance between nodes in a graph, Dijkstra's Algorithm, can be optimized by using a priority queue.

C++ Implementation of Heap

 
/*
 * C++ Program to Implement Heap
 */
#include < iostream >
#include < cstdlib >
#include < vector >
#include < iterator >
using namespace std;
/*
 * Class Declaration
 */
class Heap
{
    private:
        vector < int > heap;
        int left(int parent);
        int right(int parent);
        int parent(int child);
        void heapifyup(int index);
        void heapifydown(int index);
    public:
        Heap()
        {}
        void Insert(int element);
        void DeleteMin();
        int ExtractMin();
        void DisplayHeap();
        int Size();
};

/*
 * Return Heap Size
 */
int Heap::Size()
{
    return heap.size();
}
 
/*
 * Insert Element into a Heap
 */
void Heap::Insert(int element)
{
    heap.push_back(element);
    heapifyup(heap.size() -1);
}
/*
 * Delete Minimum Element
 */
void Heap::DeleteMin()
{
    if (heap.size() == 0)
    {
        cout << "Heap is Empty" << endl;
        return;
    }
    heap[0] = heap.at(heap.size() - 1);
    heap.pop_back();
    heapifydown(0);
    cout << "Element Deleted" << endl;
}
 
/*
 * Extract Minimum Element
 */
int Heap::ExtractMin()
{
    if (heap.size() == 0)
    {
        return -1;
    }
    else
        return heap.front();
}
 
/*
 * Display Heap
 */
void Heap::DisplayHeap()
{
    vector < int >::iterator pos = heap.begin();
    cout << "Heap -->  ";
    while (pos != heap.end())
    {
        cout << *pos << " ";
        pos++;
    }
    cout << endl;
}
 
/*
 * Return Left Child
 */
int Heap::left(int parent)
{
    int l = 2 * parent + 1;
    if(l < heap.size())
        return l;
    else
        return -1;
}
 
/*
 * Return Right Child
 */
int Heap::right(int parent)
{
    int r = 2 * parent + 2;
    if(r < heap.size())
        return r;
    else
        return -1;
}
 
/*
 * Return Parent
 */
int Heap::parent(int child)
{
    int p = (child - 1)/2;
    if(child == 0)
        return -1;
    else
        return p;
}
 
/*
 * Heapify- Maintain Heap Structure bottom up
 */
void Heap::heapifyup(int in)
{
    if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in])
    {
        int temp = heap[in];
        heap[in] = heap[parent(in)];
        heap[parent(in)] = temp;
        heapifyup(parent(in));
    }
}
 
/*
 * Heapify- Maintain Heap Structure top down
 */
void Heap::heapifydown(int in)
{
 
    int child = left(in);
    int child1 = right(in);
    if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
    {
       child = child1;
    }
    if (child > 0)
    {
        int temp = heap[in];
        heap[in] = heap[child];
        heap[child] = temp;
        heapifydown(child);
    }
}
 
/*
 * Main Contains Menu
 */
int main()
{
    Heap h;
    while (1)
    {
        cout << "------------------" << endl;
        cout << "Operations on Heap" << endl;
        cout << "------------------" << endl;
        cout << "1.Insert Element" << endl;
        cout << "2.Delete Minimum Element" << endl;
        cout << "3.Extract Minimum Element" << endl;
        cout << "4.Print Heap" << endl;
        cout << "5.Exit" << endl;
        int choice, element;
        cout<<"Enter your choice: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout << "Enter the element to be inserted: ";
            cin >> element;
            h.Insert(element);
            break;
        case 2:
            h.DeleteMin();
            break;
        case 3:
            cout << "Minimum Element: ";
            if (h.ExtractMin() == -1)
            {
                cout << "Heap is Empty" << endl;
            }
            else
                cout << "Minimum Element:  " << h.ExtractMin() << endl;
            break;
        case 4:
            cout << "Displaying elements of Hwap:  ";
            h.DisplayHeap();
            break;
        case 5:
            exit(1);
        default:
            cout << "Enter Correct Choice" << endl;
        }
    }
    return 0;
}

$ g++ heap.cpp
$ a.out
/*
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 4
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  4 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  4 7 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  3 4 9 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element:  3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 5
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  3 4 9 7 5
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 11
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  3 4 9 7 5 11
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 2
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  2 4 3 7 5 11 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 2
Element Deleted
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  3 4 11 7 5 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element:  3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 2
Element Deleted
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  4 5 11 7 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element:  4
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 5
 
------------------
(program exited with code: 0)
Press return to continue

2015-10-14T08:25:00.001-07:00

What is hash table ?
Do not confuse this with Hash List or Hash Tree.
From Wikipedia about hash table

In computing, a hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Ideally, the hash function will assign each key to a unique bucket, but it is possible that two keys will generate an identical hash causing both keys to point to the same bucket. Instead, most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be accommodated in some way.

This C++ Program demonstrates operations on Hash Tables

Here is source code of the C++ Program to demonstrate Hash Tables. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 *C++ Program to Implement Hash Tables
 */
#include
#include
#include
#include
using namespace std;
const int TABLE_SIZE = 128;
 
/*
 * HashEntry Class Declaration
 */
class HashEntry
{
    public:
        int key;
        int value;
        HashEntry(int key, int value)
        {
            this->key = key;
            this->value = value;
        }
};
 
/*
 * HashMap Class Declaration
 */
class HashMap
{
    private:
        HashEntry **table;
    public:   
        HashMap()
	{
            table = new HashEntry * [TABLE_SIZE];
            for (int i = 0; i< TABLE_SIZE; i++)
            {
                table[i] = NULL;
            }
        }
        /*
         * Hash Function
         */
        int HashFunc(int key)
        {
            return key % TABLE_SIZE;
        }
        /*
         * Insert Element at a key
         */
	void Insert(int key, int value)
	{
            int hash = HashFunc(key);
            while (table[hash] != NULL && table[hash]->key != key)
            {
                hash = HashFunc(hash + 1);
            }
            if (table[hash] != NULL)
                delete table[hash];
            table[hash] = new HashEntry(key, value);
	}
        /*
         * Search Element at a key
         */
        int Search(int key)
	{
	    int  hash = HashFunc(key);
	    while (table[hash] != NULL && table[hash]->key != key)
	    {
	        hash = HashFunc(hash + 1);
	    }
	    if (table[hash] == NULL)
	        return -1;
	    else
	        return table[hash]->value;
        }
 
        /*
         * Remove Element at a key
         */
        void Remove(int key)
	{
	    int hash = HashFunc(key);
	    while (table[hash] != NULL)
	    {
	        if (table[hash]->key == key)
	            break;
	        hash = HashFunc(hash + 1);
	    }
            if (table[hash] == NULL)
	    {
                cout<<"No Element found at key "<>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter element to be inserted: ";
            cin>>value;
            cout<<"Enter key at which element to be inserted: ";
            cin>>key;
            hash.Insert(key, value);
            break;
        case 2:
            cout<<"Enter key of the element to be searched: ";
            cin>>key;
            if (hash.Search(key) == -1)
            {
	        cout<<"No element found at key "<>key;
            hash.Remove(key);
            break;
        case 4:
            exit(1);
        default:
           cout<<"\nEnter correct option\n";
       }
    }
    return 0;
}

$ g++ hash_table.cpp
$ a.out
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 12
Enter key at which element to be inserted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 24
Enter key at which element to be inserted: 2
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 36
Enter key at which element to be inserted: 3
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 48
Enter key at which element to be inserted: 4
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 60
Enter key at which element to be inserted: 5
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 3
Element at key 3 : 36
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 5
Element at key 5 : 60
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 4
Element Deleted
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 4
No element found at key 4
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 2
Element at key 2 : 24
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4
 
 
------------------
(program exited with code: 1)
Press return to continue

2015-10-14T08:13:00.001-07:00

This C program generates graph using Adjacency Matrix Method.

A graph G,consists of two sets V and E. V is a finite non-empty set of vertices.E is a set of pairs of vertices,these pairs are called as edges V(G) and E(G) will represent the sets of vertices and edges of graph G.

Undirected graph – It is a graph with V vertices and E edges where E edges are undirected. In undirected graph, each edge which is present between the vertices Vi and Vj,is represented by using a pair of round vertices (Vi,Vj).

Directed graph – It is a graph with V vertices and E edges where E edges are directed.In directed graph,if Vi and Vj nodes having an edge.than it is represented by a pair of triangular brackets Vi,Vj.

Here is the source code of the C program to create a graph using adjacency matrix. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

//... A Program to represent a Graph by using an Adjacency Matrix method
#include 
#include 
int dir_graph();
int undir_graph();
int read_graph(int adj_mat[50][50], int n );

void main()
{
   int option;
   do
   {     
        printf("\n A Program to represent a Graph by using an ");
  printf("Adjacency Matrix method \n ");
  printf("\n 1. Directed Graph ");
  printf("\n 2. Un-Directed Graph ");
  printf("\n 3. Exit ");
  printf("\n\n Select a proper option : ");
  scanf("%d", &option);
  switch(option)
  {
    case 1 : dir_graph();
       break;
    case 2 : undir_graph();
       break;
    case 3 : exit(0);
  } // switch
    }while(1);
}
 
int dir_graph()
{
    int adj_mat[50][50];
    int n;
    int in_deg, out_deg, i, j;
    printf("\n How Many Vertices ? : ");
    scanf("%d", &n);
    read_graph(adj_mat, n);
    printf("\n Vertex \t In_Degree \t Out_Degree \t Total_Degree ");
    for (i = 1; i <= n ; i++ )
    {
        in_deg = out_deg = 0;
 for ( j = 1 ; j <= n ; j++ )
 {
            if ( adj_mat[j][i] == 1 )
                in_deg++;
 } 
        for ( j = 1 ; j <= n ; j++ )
            if (adj_mat[i][j] == 1 )
                out_deg++;
            printf("\n\n %5d\t\t\t%d\t\t%d\t\t%d\n\n",i,in_deg,out_deg,in_deg+out_deg);
    }
    return;
}
 
int undir_graph()
{
    int adj_mat[50][50];
    int deg, i, j, n;
    printf("\n How Many Vertices ? : ");
    scanf("%d", &n);
    read_graph(adj_mat, n);
    printf("\n Vertex \t Degree ");
    for ( i = 1 ; i <= n ; i++ )
    {
        deg = 0;
        for ( j = 1 ; j <= n ; j++ )
            if ( adj_mat[i][j] == 1)
                deg++;
        printf("\n\n %5d \t\t %d\n\n", i, deg);
    } 
    return;
} 
 
int read_graph ( int adj_mat[50][50], int n )
{
    int i, j;
    char reply;
    for ( i = 1 ; i <= n ; i++ )
    {
        for ( j = 1 ; j <= n ; j++ )
        {
            if ( i == j )
            {
                adj_mat[i][j] = 0;
  continue;
            } 
            printf("\n Vertices %d & %d are Adjacent ? (Y/N) :",i,j);
            scanf("%c", &reply);
            if ( reply == 'y' || reply == 'Y' )
                adj_mat[i][j] = 1;
            else
                adj_mat[i][j] = 0;
 }
    } 
    return;
}

$ gcc graph.c -o graph
$ ./graph
 A Program to represent a Graph by using an Adjacency Matrix method 
 
 1. Directed Graph 
 2. Un-Directed Graph 
 3. Exit 
 
 Select a proper option : 
 How Many Vertices ? : 
 Vertices 1 & 2 are Adjacent ? (Y/N) : N
 Vertices 1 & 3 are Adjacent ? (Y/N) : Y
 Vertices 1 & 4 are Adjacent ? (Y/N) : Y
 Vertices 2 & 1 are Adjacent ? (Y/N) : Y
 Vertices 2 & 3 are Adjacent ? (Y/N) : Y
 Vertices 2 & 4 are Adjacent ? (Y/N) : N
 Vertices 3 & 1 are Adjacent ? (Y/N) : Y
 Vertices 3 & 2 are Adjacent ? (Y/N) : Y
 Vertices 3 & 4 are Adjacent ? (Y/N) : Y
 Vertices 4 & 1 are Adjacent ? (Y/N) : Y
 Vertices 4 & 2 are Adjacent ? (Y/N) : N
 Vertices 4 & 3 are Adjacent ? (Y/N) : Y
 Vertex   In_Degree   Out_Degree   Total_Degree 
 
     1   2  0  2
 
 
 
     2   1  2  3
 
 
 
     3   0  1  1
 
 
 
     4   1  1  2
 
 
 A Program to represent a Graph by using an Adjacency Matrix method 
 
 1. Directed Graph 
 2. Un-Directed Graph 
 3. Exit

2015-10-14T07:57:00.001-07:00

VoIP refers to Voice Over IP, which is a methodology of delivering the voice communication data over the internet. Voice over IP (VoIP) refers to sending voice data over the internet. Initially this was only possible using computers (connected or WiFi). An example would be Skype.

With mobile phones becoming popular (pre-smartphone mostly but also some smartphones) there was an attempt to port VoIP over mobile phones and this was generally referred to as mobile VoIP (mVoIP). You could use cellular data connectivity or WiFi for VoIP in this case. Nowadays, VoIP is referred for Over The Top (OTT) applications that may use PC's, tablets, smartphones, etc. Example would be Skype, Viber, WhatsApp, etc.

Packets are packets and the only thing that knows they are voice is the application that receives than & processes them eg your Skype app. As such that is Layer 7 and they go through L1-L6 exactly as every other packet. They could be going over LTE, over WiFi or over ADSL - it doesn't matter = packets are packets.

The cellular world used to have 2 separate core networks called CS (circuit switched) that was used for voice and PS (packet switched) for data. To simplify the network, they started moving Voice over to PS part. For 3G/HSPA this became known as VoHSPA (Voice over HSPA) and for 4G/LTE it is known as VoLTE (Voice over LTE). Since HSPA/LTE is data only network, the networks realised that they can use WiFi for the access network in the same way. Hence VoWiFi is using WiFi for access but the PS network for guaranteeing the quality of service (QoS).

The Voice over LTE, VoLTE scheme was devised as a result of operators seeking a standardised system for transferring traffic for voice over LTE. Originally LTE was seen as a completely IP cellular system just for carrying data, and operators would be able to carry voice either by reverting to 2G / 3G systems or by using VoIP in one form or another.

VoLTE is a specific type of VoIP designed into the LTE standard, so it has lots of very specific optimisations and accelerations. In effect, the packets are treated as "special" by the whole LTE network.

That means it will work better (lower latency, less power, etc) - and as you say, be able to handover to other LTE cells or to 3G/2G legacy networks.

Signals Research Group (very good, very respected consultancy) & Spirent did some testing and confirmed this.

Commercially deployed Voice-over-LTE (VoLTE) technology provides better service than 3G Circuit Switched (CS) voice and Internet calling services and Skype software.
The analysis found that VoLTE users enjoyed considerably better call quality, faster connectivity and substantially less drain on the batteries of their mobile devices.

The report evaluates several attributes including call setup time, call reliability, call quality, network resource requirements, and the impact on battery life. The report’s highlights include:

VoLTE call quality greatly exceeded that of 3G CS voice and was measurable higher than the HD voice service offered by Skype
With network loading, and in particular with background applications running on the mobile phone and transferring data with the network, the VoLTE results were considerably better than Skype
VoLTE call setup time was nearly twice as fast as 3G Circuit Switched Fallback (CSFB) call setup
VoLTE used substantially fewer network resources than Skype voice, which in turn resulted in longer estimated device battery life for the subscriber and a more efficient network for the operator
When leaving LTE coverage, VoLTE calls were successfully handed over to 3G CS voice. The network’s enhanced Single Radio Voice Call Continuity ensures calls continue without interruption

“The clear choice for mobile network operators should be a no brainer,” said Emil Olbrich, vice president of Network Technologies for SRG. “VoLTE delivers a consistently higher call quality than OTT voice applications. Operators should also strongly consider the long-term network savings associated with VoLTE, given that it takes advantage of advanced features that allow it to use far less network resources when it comes to supporting a voice call when compared with current OTT voice applications.”

So how do you compare VoLTE, VoWiFi and VoIP. I found this interesting table

As can be seen in the table, VoLTE should provide you the best quality, followed by VoWiFi (SIP VoIP) and VoIP would be the worst. Again, the worst may still be good enough for most people most of the time.

2015-10-13T08:15:00.004-07:00

1. Some trick for Gmail users

To open only unread emails , just type is:unread in search box.
You can also open is:starred , is:read , is:muted , is:chat.

if you want to open unread emails from inbox only then type
is:unread label:inbox in search box.

For other labels just use label:spam , label:chats e.t.c and You can combine the keywords according to use.

2. How to enable GodMode on Windows.

This is a very simple trick.
a. In any drive of your computer create a New Folder and rename it as GodMode.

b. Now append the string (without quotes) “.{ED7BA470-8E54-465E-825C-99712043E01C}” after the name of the folder so that the resultant string looks like “GodMode.{ED7BA470-8E54-465E-825C-99712043E01C}”

c. Once you renamed the folder, the icon of the folder will change automatically and the name will be changed to GodMode.

PS: Note that any changes that you make on the God Mode will be made directly to the system so don’t make any major changes unless you are very sure about it.
You may rename it i.e. instead of GodMode any other name can be used.

GodMode contains list of all computer settings.

Below are the two screenshot of the settings. Apart from that there are many more settings you will find in GodMode (all categorized and accessible from one folder- GodMode)

More to come.. Stay tuned.. :)

2015-10-13T08:05:00.001-07:00

1. Finding Windows Product Key

Assuming you can boot your computer without any problems, you can easily create a simple VBscript that will read the value out of the registry and then translate it into the format that you need for reinstalling.

Copy and paste the following into a Notepad window:

Set WshShell = CreateObject("WScript.Shell")
MsgBox ConvertToKey(WshShell.RegRead("HKLM\SOFTWARE\Microsoft\Windows NT\CurrentVersion\DigitalProductId"))
 
Function ConvertToKey(Key)
Const KeyOffset = 52
i = 28
Chars = "BCDFGHJKMPQRTVWXY2346789"
Do
Cur = 0
x = 14
Do
Cur = Cur * 256
Cur = Key(x + KeyOffset) + Cur
Key(x + KeyOffset) = (Cur \ 24) And 255
Cur = Cur Mod 24
x = x -1
Loop While x >= 0
i = i -1
KeyOutput = Mid(Chars, Cur + 1, 1) & KeyOutput
If (((29 - i) Mod 6) = 0) And (i <> -1) Then
i = i -1
KeyOutput = "-" & KeyOutput
End If
Loop While i >= 0
ConvertToKey = KeyOutput
End Function

You’ll need to use File -> Save As, change the “Save as type” to “All Files” and then name it productkey.vbs or something similar ending with the vbs extension. We’d recommend saving to the desktop for easy access.

Once you’ve saved it, you can just double-click and the popup window will show you your product key.

Note :- If you use CTRL + C when the popup window is active, it will copy the contents of the window to the clipboard, and then you can paste it into Notepad or somewhere else.

2. Locate Your Android Phone Easily

It is very common situation when you can't find your phone. Then you start looking for it , searching in places like under the pillow , in some jeans pocket, bag etc, or may be that you left it in some place which definitely you don't recall. Then you find some one who could make a call , but you realize that its on silent mod.

There are some apps available but what if you are just like me and a lot of us who don't have it installed. Here comes a Giant to save you all and search your android Phone in minutes. You don't need to find some other phone to ring your to find or to find the location of the phone if it is lost/stolen. The Giant named Google has it all figured out.

on Google just search "find my phone"
Baam!, There you go.
Google will now locate your phone.

You can now Ring you phone for 5 min in full volume even if it was in silent mod. It actually schedules a ring if the phone cannot be reached instantly.
You can in worst case erase your phone, helpful when phone gets stolen and sensitive data is there.
You can now be little more careless.

3. Create your own wifi hotspot on Windows 7 or 8 without using any external applications

You don't need "Connectify" or any other software for it. Also, you can save yourself from that 90 minutes counter in connectify.

All you need to do is run the following two commands in cmd -

Open cmd with Run as Administrator.

1) netsh wlan set hostednetwork mode=allow ssid=wifiname key=wifipassword

2) netsh wlan start hostednetwork

Best solution - Make a batch file of it and just run the file every time when you start the pc.

To make a batch file -

First write the commands on a notepad

Then save it with the extension bat. e.g. wifi.bat

Your batch file is made and now execute the file with Admin Privileges.

Important - For this to work, your sharing should be on in network properties for the network/ethernet connection that you want to share through your wifi:

Go to Open Network and Sharing Centre ->Change Adapter Settings(On left panel)\

Your wifi hotspot would be Microsoft Hosted Network Virtual Adaptor in the Network Connections.

Go to the properties of the LAN/ethernet/WiFi connection and make the changes accordingly.

Your wifi hotspot would be ready. :)

To stop the wifi hotspot -

Write the following in command prompt (or create a batch file similar to above) : netsh wlan stop hostednetwork.

More coming soon.. :)

2015-10-13T07:42:00.002-07:00

SIM and USIM

SIM cards (Subscriber Identity Module) are used to communicate on GSM networks and USIMs were introduced together with UMTS or 3G network.

Although it's possible to access 3G with a simple SIM card, the USIM have many advantages as compared to the SIM:

• A USIM is a tiny computer which is able to handle several mini internal applications, for instance a contact-less e-purse for the subway, a local service portal giving you access to your phone bill, etc, while SIM's analog is simple SIM menu which can't compute something by own other than communicating with carrier's server;
Bigger and Improved phone-book: USIM allows you to store thousands of contacts (limit on SIM is 255). Each contact can now contain email id and more than one phone number;

• A 3G (UMTS) handset equipped with a USIM card can be used to make video calls on 3g network;

• New and improved security algorithms are used to prevent unauthorized access to phone line, encrypt your calls and internet traffic and store contacts securely;

2015-10-13T07:37:00.005-07:00

I've came across this question so many times in the period of telecommunication learning. Every time I asked the question, there was no one to properly answer the question, may be it was because I couldn't phrase the question in easily understandable way. Eventually I came across a few answers, here is the most convincing one from quora..

Why the channel spacing in GSM 900 is just 200KHz ?

It was a trade-off: wider channels = more bandwidth and more users.

Narrower channels are easier to implement (the equalizer) *

Other, very similar TDMA/FDD chose different channel sizes:
US D-AMPS / IS136 used 30KHZ (but only had three users instead of 8 or 16)
Japan's PDC used 25KHz, again for 3 users

GSM beat both of those. I don't know that proves 200KHz was "better"

There is no unique "right answer"

If you do an archive trawl through 3GPP standards from early 90s you'll probably find the analysis (I wish you luck...!)

* Remember these decisions were taken 20 years ago: the technology at the time is relevant, not what you can do now.

NOTE
It uses 25MHz each in 890-915 MHz and 935-960 MHz ranges with 200khz channel spacing
That is not completely correct: GSM uses many more ranges than that e around 850 and 1800.

2015-10-12T09:16:00.001-07:00

You are not allowed to use loop constructs like while, for..etc, and you can only use the following ADT functions on Stack S:

1. isEmpty(S)
2. push(S)
3. pop()

Solution

The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.

1 -> top of the STACK
2
3
4 -> bottom of the STACK

First 4 is inserted at the bottom.
4

Then 3 is inserted at the bottom.
4 
3

Then 2 is inserted at the bottom.
4 
3
2

Then 1 is inserted at the bottom
4 
3
2
1 -> bottom of the STACK

So we need a function that inserts at the bottom of a stack using the above given basic stack function.

//Below is a recursive function that inserts an element at the bottom of a stack.

void insertAtBottom(struct sNode** top_ref, int item)
{
   int temp; 
   if(isEmpty(*top_ref))
   { 
       push(top_ref, item);
   }
   else
   {     
     /* Hold all items in Function Call Stack until we reach end of
       the stack. When the stack becomes empty, the isEmpty(*top_ref)
       becomes true, the above if part is executed and the item is
       inserted at the bottom */
     temp = pop(top_ref);
     insertAtBottom(top_ref, item);

     /* Once the item is inserted at the bottom, push all the
          items held in Function Call Stack */
     push(top_ref, temp);
   }            
}

//Below is the function that reverses the given stack using insertAtBottom()

void reverse(struct sNode** top_ref)
{
  int temp;  
  if(!isEmpty(*top_ref))
  {

    /* Hold all items in Function Call Stack until we reach end of
     the stack */
    temp = pop(top_ref);                       
    reverse(top_ref);

    /* Insert all the items (held in Function Call Stack) one by one
       from the bottom to top. Every item is inserted at the bottom */
    insertAtBottom(top_ref, temp);
  }     
}

//Below is a complete running program for testing above functions.

#include
#include
#define bool int
/* structure of a stack node */
struct sNode
{
   char data;
   struct sNode *next;
};
/* Function Prototypes */
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isEmpty(struct sNode* top);
void print(struct sNode* top);
/* Driveer program to test above functions */
int main()
{
  struct sNode *s = NULL;
  push(&s, 4);
  push(&s, 3);
  push(&s, 2);
  push(&s, 1); 
  printf("\n Original Stack ");
  print(s);
  reverse(&s);
  printf("\n Reversed Stack "); 
  print(s);
  getchar();
}   
/* Function to check if the stack is empty */
bool isEmpty(struct sNode* top)
{
  return (top == NULL)? 1 : 0;
}
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
  /* allocate node */
  struct sNode* new_node =
            (struct sNode*) malloc(sizeof(struct sNode));
  if(new_node == NULL)
  {
     printf("Stack overflow \n");
     getchar();
     exit(0);
  }         
  /* put in the data  */
  new_node->data  = new_data;
  /* link the old list off the new node */
  new_node->next = (*top_ref);
  /* move the head to point to the new node */
  (*top_ref)    = new_node;
}
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
  char res;
  struct sNode *top;
  /*If stack is empty then error */
  if(*top_ref == NULL)
  {
     printf("Stack overflow \n");
     getchar();
     exit(0);
  }
  else
  {
     top = *top_ref;
     res = top->data;
     *top_ref = top->next;
     free(top);
     return res;
  }
}
/* Functrion to pront a linked list */
void print(struct sNode* top)
{
  printf("\n");
  while(top != NULL)
  {
    printf(" %d ", top->data);
    top =  top->next;
  }
}

Later...

2015-10-12T08:44:00.000-07:00

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself.

A string of length n has n! permutation. Source: Mathword(http://mathworld.wolfram.com/Permutation.html)

Below are the permutations of string
ABC. ABC, ACB, BAC, BCA, CAB, CBA

Here is a solution using backtracking.

These permute2 values themselves can be broken down to smaller subproblems.

Here, it is obvious that permute1(any char) = char itself. This is the base case of this recursion. Unrolling the recursion for the 3 required values yields:

permute2(“BC”) = { “BC”, “CB” }
permute2(“AC”) = { “AC”, “CA”}
permute2(“AB”) = {“AB”, “BA”}

So the resultant sets of strings are:
permute3(“ABC”) = {“ABC”, “ACB”} U {“BAC”, “BCA”} U {“CAB”, “CBA”}

which is the set of all permutations of the string “ABC”. It is obvious to see that we are in fact just choosing the starting prefix of the permutation and then requesting the permute function to run on a smaller sub-problem of permuting a smaller string.

To generalize, we can state that we can get all the permutations of a string using the general recurrence:

C
# include 
 
/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
  
/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
}
 
/* Driver program to test above functions */
int main()
{
   char a[] = "ABC"; 
   permute(a, 0, 2);
   getchar();
   return 0;
}

Output:

ABC
ACB
BAC
BCA
CBA
CAB

Algorithm Paradigm: Backtracking Time Complexity: O(n*n!)

Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.

For i = 0 and j = 0
A is fixed at first place using below line
swap((a+i), (a+j)) /*A is swapped with A*/
Then all the permutations of BC (sub-string after A) are printed
permute(a, i+1, n);  /*Call permute for BC  with i = 1  */
Finally swap the characters back
swap((a+i), (a+j)) /*A is swapped with A*/
For i = 0 and j = 1
B is fixed at first place using below line
swap((a+i), (a+j)) /*A is swapped with B*/
Then all the permutations of BC (sub-string after A) are printed
permute(a, i+1, n);  /*Call permute for AC  with i = 1 */
Finally, swap the characters back
swap((a+i), (a+j)) /*B is swapped with A*/
For i = 0 and j = 2
C is fixed at first place using below line
swap((a+i), (a+j)) /*A is swapped with C*/
Then all the permutations of BC (sub-string after A) are printed
permute(a, i+1, n);  /*Call permute for BA with i = 1 */
Finally, swap the characters back
swap((a+i), (a+j)) /*C is swapped with A*/
For i = 1, second character is swapped one by one with the other characters (after second character). Same way is continued for i = 2, 3..

To understand how this works, just look at the string “ABC”.

Let us assume that we have a magic function permute2 that generates all possible permutations of a given string of length 2.

Then, the permutations problem for the string “ABC” can then be broken down as:

Hope it will be useful to you.. Source: http://www.eandbsoftware.org/

2013-11-13T02:06:00.001-08:00

First, a little about how we perceive images and then the details about how it is displayed on the computer screen.

Every object's color we see is a composite of Red, Green and Blue components. The mixture of these primary colors in different proportions produces the entire spectrum of colors we can see. There are two ways we can understand this - One is the additive color system and the second is the subtractive color system.

In an additive color scheme, we understand colors as a mixture of primary colors - Red, Green and Blue (RGB). For example, Yellow is an equal mixture of Red and Green colors. White is an equal mixture or red, green, blue components.

In the subtractive scheme, we understand colors based on what quantities of primary colors are absorbed by an object and what is reflected off of it. For example, an object in white light that absorbs no wavelengths of the visible light spectrum appears white because it reflects everything. Similarly, an object appears black because it absorbs everything and reflects nothing.

How colors are represented in a computer and rendered on the screen:

In a computer, the primary colors Red, Green and Blue are represented by bits. These bits are rendered by tiny display units called pixels. The display unit is a huge grid of individual pixels and each pixel can display a mixture of primary colors. Now if you have one bit for each color RGB, how many different colors could be represented with it? The answer is 2^3=8 colors. Each bit can take a value 0 or 1.

R G B R G B R G B R G B

0 0 0 = Black 1 0 0 = Red 0 1 0 = Green 0 0 1 = Blue

R G B R G B R G B R G B

1 1 1 = White 1 1 0 = Yellow 0 1 1 = Cyan 1 0 1 = Magenta

Computers usually deal with 8 bits of information for every color for each pixel. So each component R,G or B can take 256 different values. That's 256 different shades of Red, Green and Blue or 256^3 = 16 million different color combinations that can represent virtually any color possible.

An image file like bitmap (.bmp) consists of color data for each pixel and color in a grid called the raster. You can visualize the raster as follows:

Each square represents a pixel and for each pixel, the image file holds the exact mixture of Red, Green and Blue colors. On a monitor, there are thousands of pixels close to each other. They are so tiny that the human eye cannot spot them. This is the secret of producing a life like image on screen. Because the pixels are so densely packed (On a 15 inch screen with resolution of 1366x768, there are 104 pixels per inch (PPI), the human eye cannot distinguish between individual pixels.

This raster data is then mapped to the screen where it is displayed. Each pixel takes the color corresponding to it's position in the raster data. See the image below. On the left side is the image that you normally see. But when you zoom in, you can see individual pixels taking different colors.

How are pixels actually rendered on screen?

This depends on the type of monitor. In the old days, we had the Cathode Ray Tube (CRT monitor).

In a CRT monitor, there exists a device called the electron gun which shoots electrons onto a phosphor screen. Phosphor is a fluorescent material and glows when electrons bombard them. The color produced by the phosphor element depends of the energy of the electrons which is controlled by the electron gun.

The electron gun shoots electrons and the trajectory of electrons is controlled by magnetic deflections. Based on the raster data, the electron gun starts at the top left and shoots electrons line by line at the desired energy based on the color that is to be produced at that point. Once it reaches the bottom of the screen, it goes back up and repeats. This process is called scanning and the rate at which it happens is called the refresh rate.

We have come a far way from CRTs and now have TFT LCD (Thin film transistor Liquid Crystal Display) screens. These screens work very differently. They rely on a special property of Liquid Crystals in the presence/absence of an electric field. Liquid crystals in a twisted nematic state reorient polarized light.

In a LCD display, the liquid crystal is sandwiched between two polarizers that are 90 degrees out of phase (1 and 5 in the figure below are polarizers).

When light passes through the first polarizer, it gets horizontally oriented. When there is no electric field, the Liquid crystal reorients this light and brings it in phase with the second polarizer. When an electric field is applied, the molecules in the liquid crystal align with the field and untwist. In this state, it doesn't reorient the light. Since the light is 90 degrees out of phase with the second polarizer, it cannot pass through it. White light source is used to illuminate the panel and filters are used to produce color.

In a TFT LCD, the electric field is controlled by thin silicon transistors arranged in a grid. Each pixel in the grid has a liquid crystal element sandwiched between two capacitive plates supplied by the transistors. By turning the transistors on and off, we can control the intensity and color produced by the pixels.

The hardware takes care of rendering the image and the device drivers know how to communicate the raster to the hardware (it's hardware specific). The only thing left is to create the image file. There are different formats, but they all contain the RGB information about pixels.

fffeewww.... Thats huge... Hope now you know how these things actually work. This article has been contributed by someone on quora so I thought its useful..

Later, people.... :)

2013-11-12T20:50:00.000-08:00

Its been a long time since I'd posted something about programming and algorithms. I've been reading a lot more about algorithms, so found one perfectly explained article, thought I should share it with you people.

Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack.
See this for step wise step execution of the algorithm.

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Let us consider the below tree for example:

1
/ \
2 3
/ \
4 5

Step 1 Creates an empty stack: S = NULL

Step 2 sets current as address of root: current -> 1

Step 3 Pushes the current node and set current = current->left until current is NULL
current -> 1
push 1: Stack S -> 1
current -> 2
push 2: Stack S -> 2, 1
current -> 4
push 4: Stack S -> 4, 2, 1
current = NULL

Step 4 pops from S
a) Pop 4: Stack S -> 2, 1
b) print "4"
c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything.

Step 4 pops again.
a) Pop 2: Stack S -> 1
b) print "2"
c) current -> 5/*right of 2 */ and go to step 3

Step 3 pushes 5 to stack and makes current NULL
Stack S -> 5, 1
current = NULL

Step 4 pops from S
a) Pop 5: Stack S -> 1
b) print "5"
c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything

Step 4 pops again.
a) Pop 1: Stack S -> NULL
b) print "1"
c) current -> 3 /*right of 5 */

Step 3 pushes 3 to stack and makes current NULL
Stack S -> 3
current = NULL

Step 4 pops from S
a) Pop 3: Stack S -> NULL
b) print "3"
c) current = NULL /*right of 3 */

Traversal is done now as stack S is empty and current is NULL.

Implementation:

#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree tNode has data, pointer to left child
   and a pointer to right child */
struct tNode
{
   int data;
   struct tNode* left;
   struct tNode* right;
};

/* Structure of a stack node. Linked List implementation is used for
   stack. A stack node contains a pointer to tree node and a pointer to
   next stack node */

struct sNode
{
  struct tNode *t;
  struct sNode *next;
};

/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);

/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
  /* set current to root of binary tree */
 struct tNode *current = root;
  struct sNode *s = NULL;  /* Initialize stack s */
  bool done = 0;
  while (!done)
  {
    /* Reach the left most tNode of the current tNode */
    if(current !=  NULL)
    {
      /* place pointer to a tree node on the stack before traversing
        the node's left subtree */
      push(&s, current);                                              
      current = current->left; 
    }      
    /* backtrack from the empty subtree and visit the tNode
       at the top of the stack; however, if the stack is empty,
      you are done */
    else                                                            
    {
      if (!isEmpty(s))
      {
        current = pop(&s);
        printf("%d ", current->data);

        /* we have visited the node and its left subtree.
          Now, it's right subtree's turn */
        current = current->right;
      }
      else
        done = 1;
    }
  } /* end of while */
}    

/* UTILITY FUNCTIONS */

/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
  /* allocate tNode */
  struct sNode* new_tNode =
            (struct sNode*) malloc(sizeof(struct sNode));
  if(new_tNode == NULL)
  {
     printf("Stack Overflow \n");
     getchar();
     exit(0);
  }           
  /* put in the data  */
  new_tNode->t  = t;

  /* link the old list off the new tNode */
  new_tNode->next = (*top_ref);  

  /* move the head to point to the new tNode */
  (*top_ref)    = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
   return (top == NULL)? 1 : 0;
}  
/* Function to pop an item from stack*/

struct tNode *pop(struct sNode** top_ref)
{
  struct tNode *res;
  struct sNode *top;

  /*If sNode is empty then error */
  if(isEmpty(*top_ref))
  {
     printf("Stack Underflow \n");
     getchar();
     exit(0);
  }
  else
  {
     top = *top_ref;
     res = top->t;
     *top_ref = top->next;
     free(top);
     return res;
  }
}

/* Helper function that allocates a new tNode with the
   given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
  struct tNode* tNode = (struct tNode*)
                       malloc(sizeof(struct tNode));
  tNode->data = data;
  tNode->left = NULL;
  tNode->right = NULL;

  return(tNode);
}

/* Driver program to test above functions*/
int main()
{

  /* Constructed binary tree is

            1

          /   \

        2      3

      /  \

    4     5

  */
  struct tNode *root = newtNode(1);
  root->left        = newtNode(2);
  root->right       = newtNode(3);
  root->left->left  = newtNode(4);
  root->left->right = newtNode(5);

  inOrder(root);

  getchar();
  return 0;
}

Time Complexity: O(n)

This article has been shared from Geeks for Geeks. Please let me know if you have any concern about anything in this article.

Later folks.... :)

2013-10-30T01:54:00.001-07:00

Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm.

Example:
Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3
Output: 3->2->1->4->5->6->9->8->7->NULL.

Method 1 (Process 2k nodes and recursively call for rest of the list)

This method is basically an extension of the method discussed in this post.
kAltReverse(struct node *head, int k)
1) Reverse first k nodes.
2) In the modified list head points to the kth node. So change next
of head to (k+1)th node
3) Move the current pointer to skip next k nodes.
4) Call the kAltReverse() recursively for rest of the n - 2k nodes.
5) Return new head of the list.

#include<stdio.h>

#include<stdlib.h>



/* Link list node */

struct node

{

    int data;

    struct node* next;

};



/* Reverses alternate k nodes and

   returns the pointer to the new head node */

struct node *kAltReverse(struct node *head, int k)

{

    struct node* current = head;

    struct node* next;

    struct node* prev = NULL;

    int count = 0;  



    /*1) reverse first k nodes of the linked list */

    while (current != NULL && count < k)

    {

       next  = current->next;

       current->next = prev;

       prev = current;

       current = next;

       count++;

    }

  

    /* 2) Now head points to the kth node.  So change next

       of head to (k+1)th node*/

    if(head != NULL)

      head->next = current;  



    /* 3) We do not want to reverse next k nodes. So move the current

        pointer to skip next k nodes */

    count = 0;

    while(count < k-1 && current != NULL )

    {

      current = current->next;

      count++;

    }



    /* 4) Recursively call for the list starting from current->next.

       And make rest of the list as next of first node */

    if(current !=  NULL)

       current->next = kAltReverse(current->next, k);



    /* 5) prev is new head of the input list */

    return prev;

}



/* UTILITY FUNCTIONS */

/* Function to push a node */

void push(struct node** head_ref, int new_data)

{

    /* allocate node */

    struct node* new_node =

            (struct node*) malloc(sizeof(struct node));



    /* put in the data  */

    new_node->data  = new_data;



    /* link the old list off the new node */

    new_node->next = (*head_ref);   



    /* move the head to point to the new node */

    (*head_ref)    = new_node;

}



/* Function to print linked list */

void printList(struct node *node)

{

    int count = 0;

    while(node != NULL)

    {

        printf("%d  ", node->data);

        node = node->next;

        count++;

    }

}   



/* Drier program to test above function*/

int main(void)

{

    /* Start with the empty list */

    struct node* head = NULL;



    // create a list 1->2->3->4->5...... ->20

    for(int i = 20; i > 0; i--)

      push(&head, i);



     printf("\n Given linked list \n");

     printList(head);

     head = kAltReverse(head, 3);



     printf("\n Modified Linked list \n");

     printList(head);



     getchar();

     return(0);

}

Output:
Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Modified Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

Time Complexity: O(n)

Method 2 (Process k nodes and recursively call for rest of the list)

The method 1 reverses the first k node and then moves the pointer to k nodes ahead. So method 1 uses two while loops and processes 2k nodes in one recursive call.

This method processes only k nodes in a recursive call. It uses a third bool parameter b which decides whether to reverse the k elements or simply move the pointer.

_kAltReverse(struct node *head, int k, bool b)
1) If b is true, then reverse first k nodes.
2) If b is false, then move the pointer k nodes ahead.
3) Call the kAltReverse() recursively for rest of the n - k nodes and link
rest of the modified list with end of first k nodes.
4) Return new head of the list.

#include<stdio.h>

#include<stdlib.h>



/* Link list node */

struct node

{

    int data;

    struct node* next;

};



/* Helper function for kAltReverse() */

struct node * _kAltReverse(struct node *node, int k, bool b);



/* Alternatively reverses the given linked list in groups of

   given size k. */

struct node *kAltReverse(struct node *head, int k)

{

  return _kAltReverse(head, k, true);

}

 

/*  Helper function for kAltReverse().  It reverses k nodes of the list only if

    the third parameter b is passed as true, otherwise moves the pointer k

    nodes ahead and recursively calls iteself  */

struct node * _kAltReverse(struct node *node, int k, bool b)

{

   if(node == NULL)

       return NULL;



   int count = 1;

   struct node *prev = NULL;

   struct node  *current = node;

   struct node *next;

 

   /* The loop serves two purposes

      1) If b is true, then it reverses the k nodes

      2) If b is false, then it moves the current pointer */

   while(current != NULL && count <= k)

   {

       next = current->next;



       /* Reverse the nodes only if b is true*/

       if(b == true)

          current->next = prev;

            

       prev = current;

       current = next;

       count++;

   }

   

   /* 3) If b is true, then node is the kth node.

       So attach rest of the list after node.

     4) After attaching, return the new head */

   if(b == true)

   {

        node->next = _kAltReverse(current,k,!b);

        return prev;       

   }

   

   /* If b is not true, then attach rest of the list after prev.

     So attach rest of the list after prev */  

   else

   {

        prev->next = _kAltReverse(current, k, !b);

        return node;      

   }

}

 



/* UTILITY FUNCTIONS */

/* Function to push a node */

void push(struct node** head_ref, int new_data)

{

    /* allocate node */

    struct node* new_node =

            (struct node*) malloc(sizeof(struct node));

 

    /* put in the data  */

    new_node->data  = new_data;

 

    /* link the old list off the new node */

    new_node->next = (*head_ref);

 

    /* move the head to point to the new node */

    (*head_ref)    = new_node;

}

 

/* Function to print linked list */

void printList(struct node *node)

{

    int count = 0;

    while(node != NULL)

    {

        printf("%d  ", node->data);

        node = node->next;

        count++;

    }

}

 

/* Drier program to test above function*/

int main(void)

{

    /* Start with the empty list */

    struct node* head = NULL;

    int i;

 

    // create a list 1->2->3->4->5...... ->20

    for(i = 20; i > 0; i--)

      push(&head, i);

 

    printf("\n Given linked list \n");

    printList(head);

    head = kAltReverse(head, 3);

 

    printf("\n Modified Linked list \n");

    printList(head);

 

    getchar();

    return(0);

}

Output: Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19 Time Complexity: O(n)

2013-10-24T23:50:00.001-07:00

Hello folks, hope you people are doing well..

I have tried some of the techniques to print 100 to 1 without using any loops in the program. So here are some of the best suitable techniques. Actually I only have one right now, but will surely share others as soon as I get some better differences between them to share.

Main concept here is to use Recursion.

Method #1:

#include <iostream>

using namespace std;

void printvals(int);



void printvals(int n)

{

  if(n!=0)

  {

  cout<<n<<" ";

  printvals(--n);

  }

}

int main()

{

  int i=100;

  printvals(i);

  return 0;

}

Later Folks...... :)

2013-10-17T21:44:00.003-07:00

Automatic: auto

storage is automatically allocated on function/block entry and automatically freed when the function/block is exited
may not be used with global variables (which have storage space that exists for the life of the program)
auto is the default for function/block variables

auto int a is the same as int a
because it is the default, it is almost never used

register provides a hint to the compiler that you think a variable will be frequently used
compiler is free to ignore register hint
if ignored, the variable is equivalent to an auto variable with the exception that you may not take the address of a register (since, if put in a register, the variable will not have an address)
rarely used, since any modern compiler will do a better job of optimization than most programmers

if used inside a block or function, the compiler will create space for the variable which lasts for the life of the program

  int
  counter(void)
  {
 static int cnt = 0;

 return cnt++;
  }

causes the counter() function to return a constantly increasing number

If a variable is declared (with global scope) in one file but referenced in another, the extern keyword is used to inform the compiler of the variable's existence:
- In declare.c:
```
int farvar;
```
- In use.c:
```
{
 extern int farvar;
 int a;
 a = farvar * 2;
}
```
Note that the extern keyword is for declarations, not definitions

An extern declaration does not create any storage; that must be done with a global definition

another use for the static keyword is to ensure that code outside this file cannot modify variables that are globally declared inside this file
- If declare.c had declared farvar as:
```
static int farvar;
```
  then the extern int farvar statement in use.c would cause an error
- This use of static is commonly used in situations where a group of functions need to share information but do not want to risk other functions changing their internal variables
```
static int do_ping = 1; /* start with `PING' */

void
ping(void)
{
 if (do_ping == 1) {
  printf("PING ");
  do_ping = 0;
 }
}

void
pong(void)
{
 if (do_ping == 0) {
  printf("PONG\n");
  do_ping = 1;
 }
}
```

auto, register and static variables may be initialized at creation:

  int
  main(void)
  {
 int a = 0;
 register int start = 1234;
 static float pi = 3.141593;
  }

Any global and static variables which have not been explicitly initialized by the programmer are set to zero
If an auto or register variable has not been explicitly initialized, it contains whatever was previously stored in the space that is allocated to it
- this means that auto and register variables should always be initialized before being used
- compiler may provide a switch to warn about uninitialized variables

2013-10-10T01:12:00.001-07:00

Its been very important that you know all the techniques of converting a decimal into binary or vice-versa. Here I am going to show two techniques of converting a decimal into binary, one of them is using bit-manipulation and the other one is conventional.

One conventional method of converting decimal into binary is shown below:

Here is the implementation:

#include <iostream>

#include <math.h>

using namespace std;



void dec2bin(unsigned n, int a[])

/* This method is bit-manipulation */ 

{

   unsigned i, j=0;

   for(i = 1 << 15; i>0; i = i/2)

   {
a
  if(n & i)

  {

   a[j++] = 1;

  }

  else

  {

   a[j++] = 0;

  }

   }

}



void dec2bin2(int n)

/* Conventional Method */ 

{

   if(n>1)

  dec2bin2(n/2);

  

   printf("%d", n%2);

}



int main()

{

   int a[16] = {0}, i, sum=0;

   dec2bin(4, a);

   for(i=0; i<=15; i++)

  cout<<a[i];

   cout<<endl;

   //dec2bin2(65535);

   

   /* Below method will convert the binary into Decimal */
   for(i=0; i<16; i++)

   {

  sum+=((pow(2, (15-i)))*a[i]);

   }

   cout<<"Decimal: "<<sum;

   return 0;

}

I have shown two methods of converting the decimal number into binary and one method in the main() to show the conversion of binary in decimal number...

Let me know if you have any queries or above program requires any correction...
.... Next time... :)

2013-10-08T23:28:00.002-07:00

I have discussed O(n) method for finding first non-repeating character in a given string.
You can find it here Method-1

The above approach takes O(n) time, but in practice it can be improved. The first part of the algorithm runs through the string to construct the count array (in O(n) time). This is reasonable. But the second part about running through the string again just to find the first non-repeater is not good in practice. In real situations, your string is expected to be much larger than your alphabet. Take DNA sequences for example: they could be millions of letters long with an alphabet of just 4 letters. What happens if the non-repeater is at the end of the string? Then we would have to scan for a long time (again).

We can augment the count array by storing not just counts but also the index of the first time you encountered the character e.g. (3, 26) for ‘a’ meaning that ‘a’ got counted 3 times and the first time it was seen is at position 26. So when it comes to finding the first non-repeater, we just have to scan the count array, instead of the string. Thanks to Ben for suggesting this approach.

#include <stdlib.h>

#include <stdio.h>

#include <limits.h>

#define NO_OF_CHARS 256



// Structure to store count of a character and index of the first

// occurrence in the input string

struct countIndex {

   int count;

   int index;

};



/* Returns an array of above structure type. The size of

   array is NO_OF_CHARS */

struct countIndex *getCharCountArray(char *str)

{

   struct countIndex *count =

        (struct countIndex *)calloc(sizeof(countIndex), NO_OF_CHARS);

   int i;

   for (i = 0; *(str+i);  i++)

   {

      (count[*(str+i)].count)++;



      // If it's first occurrence, then store the index

      if (count[*(str+i)].count == 1)

         count[*(str+i)].index = i;

   }

   return count;

}



/* The function returns index of first non-repeating

   character in a string. If all characters are repeating

   then reurns INT_MAX */

int firstNonRepeating(char *str)

{

  struct countIndex *count = getCharCountArray(str);

  int result = INT_MAX, i;



  for (i = 0; i < NO_OF_CHARS;  i++)

  {

    // If this character occurs only once and appears

    // before the current result, then update the result

    if (count[*(str+i)].count == 1 &&

        result > count[*(str+i)].index)

      result = i;

  }

  

  free(count); // To avoid memory leak

  return result;

}



/* Driver program to test above function */

int main()

{

  char str[] = "HelloWorldHowAreYou";

  int index =  firstNonRepeating(str);

  if(index == INT_MAX)

    printf("Either all characters are repeating or string is empty");

  else

   printf("First non-repeating character is %c", str[index]);

  getchar();

  return 0;

}

Hope it helps... ....Next time... :)

2013-10-08T21:47:00.000-07:00

Given a string, find the first non-repeating character in it. For example, if the input string is “HelloWorld”, then output should be ‘H’ and if input string is “HelloHowAreYou”, then output should be ‘w’.

We can use string characters as index and build a count array. Following is the algorithm.

1) Scan the string from left to right and construct the count array.
2) Again, scan the string from left to right and check for count of each
character, if you find an element who's count is 1, return it.

Example:

Input string: str = helloworld
1: Construct character count array from the input string.

count['h'] = 1
count['e'] = 1
count['l'] = 3
count['o'] = 2
count['w'] = 1
……
2: Get the first character who's count is 1 ('h').

Implementation:

#include <iostream>

#include <malloc.h>

#define NO_OF_CHAR 256

using namespace std;



int *getcharcountarray(char *str)

{

    int *count = (int *)calloc(sizeof(int), NO_OF_CHAR);

    int i;

    for(i=0; *(str+i); i++)

     count[*(str+i)]++;

    return count;

}



int gettheindex(char *str)

{

    int *count = getcharcountarray(str);

    int index = -1, i;

    

    for(i=0; *(str+i); i++)

    {

     if(count[*(str+i)] == 1)

     {

         index = i;

         break;

     }

    }

    free(count);

    return index;

}



int main()

{

    char str[] = "samsungelectronics";

    int index = gettheindex(str);

    if(index == -1)

     cout<<"Either all characters are repeating or string is empty"<<endl;

    else

     cout<<"First repeating character is "<<str[index]<<endl;

    return 0;



}

2013-10-07T21:31:00.001-07:00

As I have explained basic concepts of the Graph in my previous post, I hope it is clear to you people. Now, I am going to show, how you can represent this graph in programming.

Now, if I call these vertices as to be the pieces of similar information and the edges as to be the various linkages between them, then, you can certainly think of representing any Graph with the help of Linked Lists, can't you?
Well, we'll see that implementation in our next section. But for now, you've a bit simpler representation of Graphs, the Adjacency Matrix. This matrix shows you all the direct linkages between the vertices; meaning the direct edges between the vertices. Let me explain this with the help of an example -

Consider, this directed graph. It has five vertices and five edges - AD, BD, CB, DE and EC. The Adjacency matrix for this will be -

Now you know why it is called as an adjacency matrix. It only shows the direct paths between the vertices but you can see there exist paths which have intermediate vertices also; like from A to B you have D->E->C.

Remember, it does not matter if the graph is weighted, the adjacency matrix is gonna remain the same.

Note:- When I say route, I mean the direct path between the vertices and that no other vertex is there in that path except the two adjacent vertices forming the edge. I guess you know how to store a 2D-matrix in an array! That is left for your practice.

#include <iostream>

#define MAX 5

using namespace std;


int main()

{

int E, V[MAX]; //E=number of Edges, V=Vertices

int i, j;

int temp1=0, temp2=0;

int adj_mat[MAX][MAX] = {0}; //Adjacency Matrix

cout<<"Enter Vertices"<<endl; //Enter all the vertices. for example 1,2,3,4 etc..

for(i=0; i<MAX; i++)

{

cin>>V[i];

}

cout<<"Enter number of Edges"<<endl;

cin>>E; //Total number of edges between vertices.



for(j=0; j<E; j++)

{

cout<<"Edge #"<<j+1<<" "; //j+1 because we will be starting from Edge #1 and not 0.

cin>>temp1; //Path from

cin>>temp2; //Path To

//Path from and to, are in case of directed graph.

adj_mat[temp1-1][temp2-1] = 1; //Placing 1 in appropriate place in adjacency matrix

}
for(i=0; i<MAX; i++)

{

for(j=0; j<MAX; j++)

{

cout<<adj_mat[i][j]<<" "; //Display the adjacency matrix.

}

cout<<endl;

}

return 0; //Get back in where you came from... :)

}

2013-10-07T20:59:00.000-07:00

I've been reading about the data structures a lot lately and came across this article on the website http://datastructures.itgo.com, So I though this is worth sharing on my blog. The person has neatly explained about the data structures and I am going to share some of the information available. So lets start with Graph.

Sorry! I can't give that mathematical definition, involving all those Vs and Es, for the Graphs. Rather, take it this way - a graph is a collection of some finite VERTICES and some finite EDGES which happen to connect these vertices. If I consider a given list of cities as my list of VERTICES then you can, probably, call the air routes between them as to be the EDGES for them.'

Based on this analogy, we can say that a Directed Graph is a one in which you have one way air routes and that you can not come back through that same route; means, you can fly from Delhi to Mumbai but can not come back through that same route. Similarly, if you have two way air routes between the cities then I call it, an Undirected Graph. Finally, if its not a sponsored journey then certainly you will have to bear the ticket fare, which means every route (EDGE) has some cost of journey attached and that makes it a Weighted Graph. No fare, no weight!

Directed Graph

Undirected Graph

Weighted Graph

Directed Graph:-
Vertices(cities): A, B, C and D
Edges(routes): AB, AC, CD

Undirected Graph:-
Vertices: A, B, C, D
Edges: AB, AC, BA, CD, DC

Weighted Graph:-
Vertices: A, B, C, D
Weighted Edges: AC-10, AB-17, CD-13

You might be thinking by now, what these Graphs have to do with computers! Well, to name a few I'll give you some applications of it - in the study of information routing on computer networks (helps in finding the shortest routes); electronic circuit designing (helps to find out the electrical loops and overlaps); ticketing software uses it to find out the shortest route... Got the idea!

Note:- When I said route here, I meant the direct path between the adjacent vertices and that no other vertex is there in that path except the two adjacent vertices forming the path.

1 if the edge is there
0 if no edge is there