Monday, October 21, 2013

Need for 'Pi'

'Pi' the miracle number
-----------------------------


I was asked( long back may be 4 years) to write which known formula provides maximum number of digits to the value of 'pi'. Since my tutor is soft enough, I bravely (rare thing from me :) ) wrote in the paper that "I do not know the formula, but using Ramanujan's formula( which is what he expected, he is a fan/ devotee of great Ramanujan) we can calculate up to some thousands and lakhs of digits, at the same time, in my opinion, the universe radius is in the order of 10 to the power 15 or 20, even if we want to calculate the volume of the universe, it is enough to find around 60 to 70 digits accuracy, I do not know the motivation of finding so many digits for pi, may be this is due to mathematicians' dream/ ego to find out this miracle (maximum number of digits)" !!
Then he explained one of the applications is to test the computation complexity using 'pi' related findings !! 

Now when I saw this article, I remember those days !!


I should have read this article before writing in the paper, but what to do I thought about this after when I read the question !! 


Thursday, October 17, 2013

Sum of cube of first n natural numbers is the square of the sum of first n natural numbers !!

Proof for (Simple Try) !!
Sum of cube of first n natural numbers is the square of the sum of first n natural numbers !!

13+23 + 33+ … +n= (1 + 2 + 3+...+n) 2 

As we know the simple formula
----------------------------------
(a + b) 2 = a2 + 2*ab + b 2

(a + b + c) 2 = a2+ b2+ c 22 (ab + ac 
                                                    + bc)

(a + b + c + d) 2= a2+ b2+c2+ d2
                                                     2(ab + ac + ad 
                                                             + bc + bd 
                                                                     + cd )

The above algebric formula has some pattern ( marked as bold) .. 2 ( a (b+c+d) + b (c+d) + cd))

Now let us look into (1 + 2 … + n) 2

(1 + 2 … + n) 2   = 
             
           12+ 22 + 32 .. + n2 + 2*{1(2+3+4..n) + 2 (3+4+...+n) + ... (n-1)(n)}

             
 (1 + 2 … + n) 2
                             12+ 22 + 32 .. + n2 2*{1*2 + 1*3 + 1*4 + …+ 1*n
                                           + 2*3 + 2*4+ … + 2*n
                                                    + 3*4+…. + 3*n
                                                             +…..+ (n-1) (n)}

Consider the violet terms, this can be written as

2 * 1 + 3 (1+2) + 4 (1+2+3) + …+ (n)(1+2+…(n-1))

using some of first n terms formula ... ( n * (n+1) / 2)) 

The above terms can be rewritten as

2 + 3(2 * 3/2) + 4(3*4/2) + 5(4*5/2) + …. +n((n-1)n/2))

After simplifying, This can be written as

(1 + 2 … + n) 2= 12+ 22 + 32 … + n2 + 2 {2 + 3(2*3/2) + 4 (3*4/3) + ….. n ((n-1) (n/2)}

                          = 12+ 22 + 32 … + n2 + {1*22+2*32 + 3*42….+ (n-1)n2}

                          = 12+ 22 + 32 … + n2 + 22 + 2*32 + 3*4+ ... + (n-1)n

upon rearranging the terms

                           = 12+ (22  22) + (32*32) + … + ((n-1)n2 + n2) 

                            = 12+ (2 * 2) + ( 3 * 32) + … + (n* n2) 

                            =13+ 2 3+ …+ n 3  
                
(1 + 2 + 3 … +n) 2 = 13+ 2 3+ … +n 3          
                                              
Change LHS to RHS and vice –versa

13+ 2 3+ … +n3    =    (1 + 2 + 3 … +n) 2

FROM the induction ( 1 + 2 + 3 … n ) = ( n (n+1) / 2 ) the above equation can be written as

13+ 2 3+ … n3     =    (n (n+1)/ 2) 2  

Tuesday, September 3, 2013

Optimized Bubble Sort - for my reference

#include "stdio.h"
#include "conio.h"


//swapping function

void swap(int* a, int *b){
      int temp;
      temp = *a;
      *a = *b;
      *b = temp;
}

//sorting function

void sort(int* a){
          
     int i = 0;
     int j = 0;
     int temp = 0;
     int flag = 1;
     int m =0;
    //optimized bubble sort using flag Variable which stops the loop after the array is sorted
    
    for (i = 0; ((i < 5) && (flag == 1)); i++ ){
       
         flag = 0;
         m = i;
         for (j = 0; j < 5-i; j++){
             
              if(a[j] > a[j+1]){
                      
                      swap(&a[j],&a[j+1]);                     
                      flag = 1;
              }
         }         
     }     
}

//main function

int main(){ 
    
    int* array;
    int i = 0;
    
    //Array creation dynamically
    array = (int*) malloc (5*sizeof(int));
    
    //Sample array
    array[0] = 78;
    array[1] = 56;
    array[2] = 93;
    array[3] = 19;
    array[4] = 104;
    
    for( i = 0; i < 5; i++){
         
         printf("%d \t", array[i]);
    }
    printf("\n\nAfter Sorting \n\n");
    sort(array);
    
    for( i = 0; i < 5; i++){
         
         printf("%d \t", array[i]);
    }
    getch();
    return 0;
}
   

Tuesday, August 13, 2013

Java Linear and Binary Searching - For my reference


public class Searching {

/**
* @param args
*/
public static void main(String[] args) {

int arrayNumbers[] = new int[] {55, 65, 76, 89, 123, 43, 56, 23, 11, 107, 98 };
int searchNumber = 89;
int pos = 0;
int posB = 0;
int unsortedArray[] = new int[arrayNumbers.length];
System.arraycopy( arrayNumbers, 0, unsortedArray, 0, arrayNumbers.length);
arrayNumbers = sort(arrayNumbers);

for (int i = 0; i < unsortedArray.length;i++){


pos = linearSearch(arrayNumbers, unsortedArray[i]);
posB = binarysearch(arrayNumbers, unsortedArray[i]);
System.out.println(unsortedArray[i] + "\t" + pos + "\t" + posB + "\t" + arrayNumbers[i]);
}
}

private static int binarysearch(int[] arrayNumbers, int i) {

int lower = 0;
int upper = arrayNumbers.length - 1;
int cur = 0;

while (true){

cur = (lower + upper) / 2;

if(i == arrayNumbers[cur])

return cur;
else if (lower > upper) 

return arrayNumbers.length;

else {

if(i > arrayNumbers[cur])

lower = cur + 1;

else 

upper = cur - 1;
}
}


}

private static int linearSearch(int[] arrayNumbers, int searchNumber) {

for(int i = 0; i < arrayNumbers.length; i++){

if(searchNumber == arrayNumbers[i]){

return i;
}

}
return 0;
}

public static int[] sort (int[] arrayNumbers){

int temp = 0;
for (int i = 0; i < arrayNumbers.length ; i ++ ){

for (int j = 0; j < arrayNumbers.length; j++) {

if(arrayNumbers[i] < arrayNumbers[j]){

temp = arrayNumbers[i];
arrayNumbers[i] = arrayNumbers[j];
arrayNumbers[j] = temp;
}
}
}
return arrayNumbers;
}
}


Friday, August 9, 2013

linked list - simple adding and deleting in between - for my reference

#include "stdio.h"
#include "stdlib.h"

struct node {
   
   int   data;
   struct node* next;
};

int length(struct node *head){
    
    struct node* current = head;
    int count = 0;
    while ( current != NULL ){
          
          count++;
          current = current -> next;
    }
return count;
}

void display(struct node *head) {
     
      
    struct node* current = head;
    int count = 0;
    while ( current != NULL ){
          
          printf("%d \t", current -> data);
          current = current -> next;
    } 
    printf("\n \n");
}

void delete ( struct node* head, int pos) {
     
     int k = 0;
     struct node* current = head;
     for( k = 0; k < pos; k++){
          
          current = current -> next;
     }
     current -> next = current -> next -> next;
}

void add ( struct node* head, int pos, int data) {
     
     int k = 0;
     struct node* current = head;
     struct node* newNode = malloc(sizeof(struct node));
     for( k = 0; k < pos; k++){
          
         current = current -> next;
     }
     
     newNode -> next = current -> next;
     newNode -> data = data;
     current -> next = newNode;
}         
     
int main(){

    int k = 0;
    int m = 0;
    int i =0;
    int pos = 3;
    struct node* head = NULL;
    struct node* current = NULL;
    struct node* nextCur = NULL;
    
    head = malloc (sizeof (struct node));
    current = malloc (sizeof (struct node));
    head -> data = 1;
    head -> next = current;
    current -> next = NULL;
    
    for(i = 0; i < 5; i++){  
          
         current -> data = i;
         nextCur = malloc (sizeof (struct node));
         current -> next = nextCur;
         current = nextCur;
     }
   current -> data = i; 
   current -> next = NULL; 
      
   display(head);    
   
   delete (head, pos);
   
   display(head);   
   
   add (head, pos, 10); 
   
   display(head); 
    
getch();
return 0;
}
    

Simple Linked List -for my reference !!


#include "stdio.h"
#include "stdlib.h"


struct node {
   
   int   data;
   struct node* next;
};

int length(struct node *head){
    
    struct node* current = head;
    int count = 0;
    while ( current != NULL ){
          
          count++;
          current = current -> next;
    }
return count;
}

void display(struct node *head) {
     
      
    struct node* current = head;
    int count = 0;
    while ( current != NULL ){
          
          printf("%d \t", current -> data);
          current = current -> next;
    } 
    printf("\n \n");
}
     
int main(){

    int k = 0;
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;
    struct node* twothree = NULL;
    
    head = malloc (sizeof (struct node));
    second = malloc (sizeof (struct node));
    third = malloc (sizeof (struct node));
    twothree = malloc (sizeof(struct node));
  
    head -> data = 1;
    head -> next = second ;
    
    second -> data = 2;
    second -> next = third;
    
    third -> data = 3;
    third -> next = NULL;
    
    printf("List with three elements \n");
   
    display(head);
    k = length(head);
    printf("\n adding a node in between second and third \n");
    
    twothree -> data = 10;
    second -> next = twothree;
    twothree -> next = third;
    
    display(head);
    k = length(head);
    display(head);
    
    printf ("\nThe length of the list %d\n \n", k);
    
    printf ("\nDeleting a node twothree \n \n");
    
    second -> next = third;
    
    k = length(head);
    display(head);
    printf ("The length of the list %d \n \n", k);
    
    
getch();
return 0;
}