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;
}