Peasant's Multiplication Algorithm

Peasant's Multiplication Algorithm

Exploit the binary representation of the number. eg:
98 * 19
Take one of the two number and represent it in binary. Now, what happens
= 98 * (1 0 0 1 1)
= 98 * (16 + 2 + 1)
= 98 * 16 + 98 * 2 + 98 * 1
= 1568 + 196 + 98
= 1862

Calculate by hand or calculator
= 98 * 19
= 1862

What is the usefulness ?
Computation of multiplication is not as easy as addition, subtraction, shift operations or logical operations. Many primitive microprocessor and micro-controller doesn't
even support it directly. So, one way of doing it is by adding a term to itself for the number of second term. eg if x*y then if we add x to itself y times then we get x*y,
However, the computation has to be done y times. But same thing can be achieved by using this algorithm but still we are doing three multiplications in above example instead of
one. But the trick is all the multiplication above is multiplication by the power of 2 and which is very cheap to compute which can be achieved easily by shifting the bits.

C Code:
 #include<stdio.h>
int mult(int a,int b)
{
int count = 0,sum=0;
while(b != 0)
{
if((b & 1)!= 0)
sum += a << count;
b = b >> 1;
count++;
}
return sum;
}
int main()
{
int num1,num2;
scanf("%d%d",&num1,&num2);
printf("%d x %d = %d\n",num1,num2,mult(num1,num2));

return 0;
}

Doubly Linked List using Single Pointer

Doubly Linked List needs two pointers to maintain the previous and next pointer value so that we can traverse in both forward and reverse direction. However, maintaining two pointers may be costly for the system with low memory. For such circumstances we have an option to create a double linked list with a single pointer. This is attainable by the use of XOR.

Steps to create DLL:

1. For, after creating the first node, make its pointer point to NULL.
2. Now, create a next node and then make it point to the predecessor node.
3. The pointer of the predecessor node is XOR with the current node. i.e. pred->pointer= pred->pointer ^ current_node
4. Jump to Step 2 to add more elements

Displaying the DLL

1. Check the list to be displayed is empty. If so, return.
2. Use two additional pointers prev and temp. Initialize prev to NULL.
3. Now, save list to temp variable.
4. Find new value of list by: list=list->ptr ^ prev.
5. Set prev=temp.
6. Jump to Step 3 until list become NULL

Displaying in Reverse direction

It can be done in the same way as Displaying element but here you need to be in the last element and then you can traverse forward.

Code:

#include
#include
struct node;
typedef struct node NODE;
struct node
{
       int info;
       struct node *ptr;
};
void create_list(int a[],NODE **list,int size)
{
     NODE *temp,*new_node;
     temp=*list;
     int i;
     for(i=0;iptr=NULL;
                              temp->info=a[0];
                              *list=temp;
                }
                else 
                {
                     new_node=(NODE*)malloc(sizeof(struct node));
                     new_node->info=a[i];
                     new_node->ptr=temp;
                     temp->ptr=(NODE*)((long)temp->ptr ^ (long)new_node);
                     temp=new_node;
                 }
     }
}
void display_normal(NODE *list)
{
     NODE *temp,*prev;
     prev=NULL;
     if(list==NULL)
                   return;
     printf("\n\n\n");                   
     do
     {
          printf("  %d  ",list->info);
          temp=list;
          list=(NODE*)((long)list->ptr ^ (long)prev);
          prev=temp;
     }while(list!=NULL);     
     
}
void display_rev(NODE *list)
{
     NODE *temp,*prev;
     prev=NULL;
     if(list==NULL)
                   return;
     do
     {
                   temp=list;
                   list=(NODE*)((long)list->ptr ^ (long)prev);
                   prev=temp;
     }while(list!=NULL);
     
     printf("\n\n\n");
     list=prev;
     prev=NULL;
     do
     {
               printf("  %d ",list->info);
               temp=list;
               list=(NODE*)((long)list->ptr ^ (long)prev);
               prev=temp;
     }while(list!=NULL);
}
int main()
{
    int a[]={23,45,78,90,12,10};
    NODE *list;
    list=NULL;
    create_list(a,&list,sizeof(a)/sizeof(a[0]));
    display_normal(list);
    display_rev(list);
    getchar();
    return 0;
}

A Fast Majority Vote Algorithm (Moore's Majority Algorithm)

Algorithm:
Suppose, we have several candidates participating in voting. Now, if the number of candidate is static then it can be done easily in O(n) time complexity with an additional storage for the number of candidates participating in the voting. However, the time required can increased tremendously if
i. The number of voters are not static. In that case, for each vote we have to scan for the candidate and update the count which may cause as worse as O(n*n) time complexity.
ii. We don't have additional space to store the vote. We are allowed to only use O(1) space.

The problem can be solved using Majority Vote Algorithm.
Here, we use two variable to find out the majority. The total comparisons required for this algorithm is 2*n.
There are two variables count and c.
count= total number of vote for the candidate
c= particular candidate
Now, go through the votes one by one in the following fashion
Step 0: Initialize count to be zero
Step 1: Go through the vote
           i. Check if the count is zero
                    if so then assign the c to this vote's candidate and then set count=1
                    if not then check if this vote's candidate is equal to c
                                  if yes then set count+=1
                                  if no then set count-=1
Step 2: Continue until the end
Step 3: Now, return c
Step 4: Check once again by going through the votes if it is really the majority.
Code:
/*I have used the static number of candidate by defining the array however it works equally fine for dynamic candidate number too. */
#include<stdio.h>
int count_vote(int a[],int size)
{
    int count=0,c,i;
    for(i=0;i<size;i++)
    {
        if(count==0)
        {
            c=a[i];
            count=1;
        }
        else
        {
            if(c==a[i])
                count++;
            else
                count--;
        }
    }
    return c;
}
int main()
{
    int a[]={2,3,2,4,5,2,4,3,2,2,2,8,9,2,7,6,1,2,2,2,4,2,5,6,7,2,1,2,2,2,2};
    int size=sizeof(a)/sizeof(a[0]);
    int majority,count=0,i;
    majority=count_vote(a,size);
    for(i=0;i<size;i++)
        if(a[i]==majority)
            count++;
    if(count>size/2)
        printf("\nThe %d is a majority with %d vote where total vote is %d .\n",majority,count,size);
    else
        printf("\nThe %d is not a majority vote but has %d vote in total vote of %d.\n",majority,count,size);
    return 0;
}

Part II: Threaded Binary Search Tree Traversal

Inorder

Algorithm:
Follow the tree towards the left, print the smallest value and then move on to print the next smallest value so that finally we will be printing all the value in the ascending order. This one can be achieved simply by using recursive algorithm as follows:
For the general binary search tree,
void inorder(struct node *tree)
{
    if(tree==NULL)
        return;
    inorder(tree->left);
    printf(" %d ",tree->info);
    inorder(tree->right);
}

However, the inorder code for Threaded binary search tree isnot as simple, the code is given below

struct node *inorder_successor(struct node *tree)
{
    struct node *temp;
    temp=tree->right;
    if(tree->isright==0) //here we are checking if the tree is a leaf ( not the temp)
        return temp;
    while(temp->isleft==1)
        temp=temp->left;
    return temp;
}
/*Thus, what we are doing in the above steps are first checking if the tree is a leaf. If so we are returning temp (which is right of the tree), otherwise we are going to find the inorder successor of that tree. */
void inorder(struct node *head_tree)
{
    struct node *tree;
    printf("\n\n");
    tree=head_tree->left;
    if(tree==NULL)
    {
        printf("\nNo element in the tree.");
        return;
    }
    while(tree->left!=head_tree)
        tree=tree->left;
    do
    {
        printf(" %d ",tree->info);
        tree=inorder_successor(tree);
        if(tree==head_tree)
            break;
    }while(1);
    printf("\n\n");
}

We are using two functions here, one for the traversal and one to find the inorder succesor after traversing any node. By the way, the traversal has started from the first inorder element. (not the root of the tree)

Preorder

In preorder, for any node we first print the value of the node and then follow its left and after printing all its left value we follow the right and print all the value.
For general binary search tree, the recursive algorithm is as follows:
void preorder(struct node *tree)
{
    if(tree==NULL)
          return;
    printf(" %d ",tree->info);
    preorder(tree->left);
    preorder(tree->right);
}
However, we do it in the similar fashion as inorder for the threaded binary trees by using two functions respectively to traverse and find the preorder successor. The code for the preorder traversal is given below:

struct node *preorder_successor(struct node *tree,struct node *head_tree)
{
    struct node *temp;
    if(tree->isleft==1)
        return tree->left;
    if(tree->isright==1)
        return tree=tree->right;
    while(tree->isright==0)
    {
        tree=tree->right;
        if(tree==head_tree)
            return head_tree;
    }
    return tree->right;
}
void preorder(struct node *head_tree)
{
    struct node *tree;
    tree=head_tree->left;
    printf("\n\n");
    if(tree==NULL)
    {
        printf("\nNo element in the tree.\n");
        return;
    }
    do
    {
        printf("  %d  ",tree->info);
        tree=preorder_successor(tree,head_tree);
        if(tree==head_tree)
            return;
    }while(1);
    printf("\n\n");
}

Postorder 

In the postorder successor, for any node we follow the left link and print all the values and then follow the right one and print all the values and finally print the value of that node.
For the general binary search tree, the postorder code is below
void postorder(struct node *tree)
{
    if(tree==NULL)
          return;
    postorder(tree->left);
    postorder(tree->right);
    printf(" %d ",tree->info);
}
However, for the threaded binary search tree, it is the trickiest. Following algorithm I used to write a code from the following address http://stackoverflow.com/questions/10694037/postorder-traversal-of-tree-without-using-recursion-or-stack

The algorithm goes as follows 

• A variable can be used to check type of current action.
• If action is left traversal and current node has a left descendant, then descendant is traversed. Otherwise action changed to right traversal.
• If action is right traversal and current node has a left descendant, action changed to left traversal. Otherwise action changed to visiting a node.
• If action is visiting node: current node is visited, afterwards its postorder successor has to be found.
• If current node’s parent accessible through a thread (i.e. current node is parent’s left child) then traversal is set to continue with the right descendant of parent.
• If current node has no right descendant, this is the end of the right-extended chain of nodes.
• First: the beginning of the chain is reached through the thread of the current node.
• Second: right references of nodes in the chain is reversed.
• Finally: chain is scanned backward, each node is visited, then right references are restored to previous settings.

 The code goes as follow
enum my_enum {LEFT_TRAVERSAL=0,RIGHT_TRAVERSAL,CURRENT_VISITING};
void chain_formation(struct node *tree)
{
    struct node *start_chain,*parent,*temp;
    parent=tree;
    start_chain=tree->left;
    if(start_chain->right==tree)
        printf("  %d  ",start_chain->info);
    while(start_chain->right!=tree)
    {
        temp=start_chain->right;
        start_chain->right=parent;
        parent=start_chain;
        start_chain=temp;
    }
    while(start_chain!=tree)
    {
        printf(" %d ",start_chain->info);
        temp=parent->right;
        start_chain=parent;
        parent=temp;
    }
      
}
void postorder(struct node *head_tree)
{
    enum my_enum traversal;
    struct node *tree,*parent;  
    tree=head_tree->left;
    printf("\n\n");
    traversal=LEFT_TRAVERSAL;
    int i=20;
    do
    {
        switch(traversal)
        {
            case LEFT_TRAVERSAL:
                        parent=tree;
                        while(tree->isleft!=0)
                        {
                            parent=tree;
                            tree=tree->left;
                        }
                        traversal=RIGHT_TRAVERSAL;
                        break;
            case RIGHT_TRAVERSAL:
                        if(tree->isright==0)
                        {
                            traversal=CURRENT_VISITING;
                            break;
                        }
                        parent=tree;
                        tree=tree->right;
                        if(tree->isleft==1)
                            traversal=LEFT_TRAVERSAL;
                        else if(tree->isright==1)
                            traversal=RIGHT_TRAVERSAL;
                        else
                            traversal=CURRENT_VISITING;
                        break;
            case CURRENT_VISITING:                  
                        if(parent->info>tree->info)
                        {
                            printf("  %d  ",tree->info);
                            tree=tree->right;
                            if(parent->isright==0)
                            {
                                parent=parent->right;
                                traversal=CURRENT_VISITING;
                            }
                            else
                                traversal=RIGHT_TRAVERSAL;
                        }
                        else
                        {
                            chain_formation(tree->right);
                            tree=tree->right;
                            if(tree->isright==0)
                                parent=tree->right;
                            traversal=RIGHT_TRAVERSAL;
                        }
                        break;
            default:
                        printf("\nWrong Input\n");
                        break;
      
        }
    }while(tree!=head_tree);
    printf("\n\n");
}

Part I : Threaded Binary Search Tree ( Definition and Insertion)

Usually, in the binary tree, we notice more null links than acutal pointer.
In a binary tree with n nodes, we have
    2n = total links
    n+1 = null links
We can make use of these null links to point other nodes in the tree as a result of which we can traverse a tree without thre requirement of having stack. It can facilitate the traversal of all three viz Inorder, Preorder and Postorder traversal without the need of extra memory required.
In the memory representation, we must be able to distinguish between threads and normal pointer. This is done by adding two extra bit fields isright and isleft.

isleft=1 if parent->left is a normal pointer.
isleft=0 if parent ->left is a thread.

isright=1 if parent->right is a normal pointer.
isright=0 if parent->right is a thread.

If the node->right_child==NULL, now we will replace it by a pointer to the node which would be printed after P when traversing the tree in inorder.
If the node->left_child==NULL, we will replace it by a pointer to the node which immediately precedes node P in inorder.

However, we will still be having two pointers viz the one in the extreme left(directly down the left line from root) and the one in the extreme right(directly along the right line from root). To prevent it we will assume a head node for threaded binary trees.
The actual tree is the left subtree of the head node. And these two NULL pointers in the extreme points to this head node as well.

The following code is to declare a node structure for the threaded binary search tree and the insertion of the node in that tree.



struct node
{
    int info;
    struct node *left,*right;
    unsigned int isleft:1;
    unsigned int isright:1;
};
/* Be pretty clear here use UNSIGNED otherwise if you will use 1 bit signed number then it will be 0 and -1 so in the subsequent comparison you have to use -1 instead of 1. If you will use 1 bit unsigned number then it will behave like a binary 0 and 1 bit.*/

void insert(struct node *head_tree,int num)
{
    struct node *tree,*temp;
    tree=head_tree->left;
    if(head_tree->isleft==0)
    {
        head_tree->left=(struct node*)malloc(sizeof(struct node));
        head_tree->left->left=head_tree;
        head_tree->left->right=head_tree;
        head_tree->left->info=num;
        head_tree->isleft=1;
        head_tree->left->isleft=0;
        head_tree->left->isright=0;
        return;
    }
    while(1)
    {
        if((tree->isleft==0 && tree->info>=num) || (tree->isright==0 && tree->info<=num))
            break;
        else if(tree->info>num)
            tree=tree->left;
        else
            tree=tree->right;
    }
    temp=(struct node*)malloc(sizeof(struct node));
    temp->info=num;
    temp->left=NULL;
    temp->right=NULL;
    temp->isleft=0;
    temp->isright=0;
    if(tree->info>num)
    {
        temp->left=tree->left;
        temp->right=tree;
        tree->left=temp;
        tree->isleft=1;
    }
    else
    {
        temp->right=tree->right;
        temp->left=tree;
        tree->right=temp;
        tree->isright=1;
    }
}