Monday, June 28, 2010

Simple C Code to Create Magic matrix

First we have to understand what is magic matrix.
  •   In magic matrix every rows and column sums are equal.
  •   Diagonal sum is also equal.
  •   The following code has O(n^2) time complexity.
  •   The example for magic matrix is given below.
               8     1       6
                               
               3      5      7        //rows,column,diagonal sum are equal
                      
               4      9      2       //here n is 3


Here is the code
 
   void magic_matrix(int n)          // N should be odd number...
   {   int i,j,k,num=1;            
        i=1;
        j=(1+n)/2;
        for(k=0;k < n*n;k++)  
        { a[i-1][j-1]=num;num++;
           i--;
           j++;
           if(i==0) i=n;
           if(j==n+1) j=1;
           if(a[i-1][j-1]!=0)
          { i+=2;
            j--;
            if(i>n) i=i-n;
            if(j==0) j=n;
           }
         }
    for(i=0;i < n;i++)
    {for(j=0;j < n;j++)
      { printf("%d\t",a[i][j]);
       }
      printf("\n");              
       }
 }

Binary search Implementation without Recursion

The features are
  • The following code does the binary search without recursion
  • We know that the time complexity for the binary search is O(logN)
  • It is efficient method for searching an element in a sorted array.
Code :(In C)

In its simplest form, binary search is used to quickly find a value in a sorted sequence (consider a sequence an ordinary array for now). We'll call the sought value the target value for clarity. Binary search maintains a contiguous subsequence of the starting sequence where the target value is surely located. This is called the search space. The search space is initially the entire sequence. At each step, the algorithm compares the median value in the search space to the target value. Based on the comparison and because the sequence is sorted, it can then eliminate half of the search space. By doing this repeatedly, it will eventually be left with a search space consisting of a single element, the target value.

C code for finding square root of a number without using sqrt() function.

 The code has the following features
  •     This following code finds a square root for a given number.
  •     You can also find square root for a floating number.
  •     This code is using a Mathematical formula.
Here is the code

  float squareRoot(float n)
  {  float prev=0,cur=1;
     while(prev!=cur)
      {   prev=cur;
          cur=0.5*(prev+(n/prev));
       }
     return cur;
  }                         //Try this code..It works great..

c code for finding binary represenation of a number

Here we have to see a recursive procedure for finding the binary representation of a given number.
  •   The following code has O(logN) time complexity.
  •   The concept is to divide the number recursively and displays the result
  •   The following function void base(int num,int n) prints the output.
Here is the code

void base(int num,int n)              //num is the given number , n is 2
   {    if(num>1)                          
             base(num/n,n);
         printf("%d",num%n);
    }

Sunday, June 27, 2010

Code For Reversing the Linked list

We can reverse the linked list in different ways.But the efficient way is given below.
  •    The Idea behind here is making the first node as a last node.
  •    So The Time Complexity for this code is O(n). 
  •    The following one is efficient using three pointers. 

Here is the code

 struct node* reverse(struct node *head)
{    struct node *q,*r,*s;
      q=head;
      r=NULL;
      while(q!=NULL)
     {  s=r;
         r=q;
        q=q->link;
        r->link=s;
      }
    return r;
 }

Program to solve Tower Of Hanoi problem in C

 TOWER OF HANOI:

 Here is the function that solves the tower of hanoi problem.
  •  2^n-1 moves are required in solving the problem.
  •  The moves are   move n-1 disks  form source to middle,move n disks from source to destination,move n-1 disks from middle to destination.   

Here is the code

void hanoi(int n,int s,int i,int d)
{ if(n>0)
 {
    hanoi(n-1,s,d,i);
    printf("move %d from %d to %d\n",n,s,d);
    hanoi(n-1,i,s,d);
  }
}

Code for Creating Mirror Image of a binary tree

MIRROR IMAGE:

We Have to Change a tree so that the roles of the left and right pointers are swapped at every node.
So the tree...
    4
   /  \
  2    5
 / \
1  3

is changed to...
    4
   / \
 5   2 //mirror image
     / \
    3   1
The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.

Here is the code:

void mirror(struct node* node)
{
         if (node==NULL)
            return;
         else
            {
               struct node* temp;
               mirror(node->left);
               mirror(node->right);
               temp = node->left;
               node->left = node->right;
               node->right = temp;
              }
 }