Friday, August 5, 2016

Optimized quick sort

In the previous article we discussed about quick sort algorithm. In this article we are going to discuss about further optimizing quick sort.

The optimized version of quick sort algorithm we are going to use is known as QuickIn Sort. QuickIn Sort is significantly faster in practice than other O (n log n) algorithms.


Previous article explains how quick sort works. As described in it, quick sort do the real sorting in it's partitioning step. Every time when the recursive function is called, the size of the partition gets smaller. 


Even for a very large data set, the recursive function call occur till the partition size is the smallest possible. When this partitioning occur, there is a threshold size of partition after which, the partitioning costs more than other O (N^2) algorithms. This is an inefficiency of quick sort algorithm.




where A, B, k and c are constants , N is the number of elements in the data set.


The L.H.S of the inequality gives the time complexity of quick sort while R.H.S gives the time complexity of other sorting algorithms.


Insertion sort is an algorithm which has an average time complexity of O (N^2). But the time efficiency of insertion sort depends on how sorted the data set is.


For small N values above inequality becomes true.


eg:






The quickIn sort algorithm use insertion sort for partitions of size less than the threshold value. The threshold value needs to be determined by testing.

Following is an implementation of quickInSort function


The partition function will be the same as in normal quick sort algorithm. Please refer previous article for the partition function. 

Following is an implementation of insertion sort function 

You can find the complete implementation of QuickIn Sort algorithm with tests on github here.

Tuesday, August 2, 2016

Learn Quick Sort

Quick Sort


Quick Sort is a divide and conquer recursive algorithm used in sorting a data set. It is one of the fastest sorting algorithms with an average time complexity of O(Nlog(N)) and a worst case time complexity of O(N²).


Algorithm

  • Pick a pivot ( element of the data set in the range)
  • Iterate through the data set once and re-arrange data so that all the elements larger than the pivot are on the right side of the pivot and elements smaller than the pivot are on the left. 
  • Apply the same re-arranging method recursively to the left and the right parts of the data set separated by the pivot.


Picking the pivot


The pivot can be any element of the data set within the range of the partition. But the pivot will decide the running time of the sorting process. Because if you choose the smallest/largest element of the data set every time, the partitioning will be useless and hence running time will be O(N²). Therefore spending some time to pick a good pivot won't be a waste. 

As mentioned above, choosing left-most element, right-most element or the element at middle as the pivot may lead to time inefficiency as the arrangement of the data set is not known. Choosing a random element also has the same risk. The best pivot will be the median of the data set. But finding it would not be wise considering the time efficiency. 

The easiest way to choose a pivot which is not a corner element is, picking the median element of the first, middle and the last element of the data set. This will ensure that you are not at the worst case every time. 

Advantages

  • No additional memory required. ( Sort in place )
  • Very fast sorting for average case

Disadvantage

  • Worst-case complexity is O(N²)
  • Sorting time not guaranteed.


Following is an implementation of quick sort algorithm in C



Partition function which does the sorting



Here is the complete implementation of quick sort algorithm with example tests on github. 

Saturday, July 16, 2016

Vert.x example - Http Server

Vert.x is a toolkit for building reactive applications on the JVM. 
For more information about vert.x please read the previous article from here. 

Following is a simple http Server implemented using vert.x to understand the nature of vert.x applications.


The code is self explanatory. 

To run the above http server, you need vert.x installed and setup properly. 

To start the server, open a terminal or a command promt and run the following command. 

vertx run Server.java

After you run the above command you will get a message saying 'Succeeded in deploying verticle'. 

If you get any errors, please check your vert.x installation. 

Now your server is running and waiting for requests to come.  

Note that the above server is implemented to handle GET requests only. It listens to the port 8500.

As line 28 needs a parameter called "name", our GET request should include a name parameter. 

Now open your browser, paste the below url and hit enter. For 'yourname', you can give anything.

http://localhost:8500/?name=yourname



Now you've used successfully used vert.x to build a server. 

This server can handle multiple clients at the same time although in the code we never do anything about it. And we don't have to worry about synchronization or deadlocks. 
This is the speciality of vert.x. 

This same server can be built using javaScript, ruby Groovy or Python to run on JVM. 
More examples can be found in the official github repository of vert.x.

Getting Started with Vert.x

What is Vert.x ?


Vert.x is a toolkit for writing scalable, polyglot, reactive applications which run on the JVM. Vert.x is similar to Node.js as both provide an asynchronous API and as it is event-driven. 

Polyglot


Vert.x is written in Java, but we can use it with many languages like Java, Groovy, Ruby, Python, and even JavaScript. You can even mix and match languages. 

Reactive


Vert.x is asynchronous. It can be used to create highly concurrent applications. Vert.x allows to create multiple threads based on the number of CPU cores while only one process is executed. It handles the multi-threading so users can focus on implementing business logic. Developer won't have to worry about synchronization, deadlocks or data races.

Verticles


Verticles are building blocks of vert.x application. They are units which operate independently. It can simply said that running a vert.x application means running one or more verticles. Verticles communicate with each other using event bus. Vert.x has some command line tool which enable the developer to simply run the program without compiling it. 

How to install vert.x ?


Vert.x can be installed linux, Windows or OSX. Before installing, you need to have JDK 1.7.0 or later installed and JAVA_HOME added to the PATH variable. 

Linux

  • Download the latest version of vert.x from here.
  • Extract it to a place where it will stay permanent. (Extracted directory shouldn't be moved since path will be set accordingly).
  • Add vert.x/bin to PATH variable. Open a terminal and run the following command 
                          export PATH=$PATH:/path

      where
          path = absolute path to the bin directory of your vert.x extract

     eg:
                          export PATH=$PATH:/home/user/Vertx/bin


      If you are having trouble changing the PATH variable, see this.

  • Verify your installation by running the command 
                         vertx version

Windows

  • Download the latest version of vert.x from here.
  • Extract it to a place where it will stay permanent. (Extracted directory shouldn't be moved since path will be set accordingly).
  • Search for 'View Advanced System Settings' and select 'Environment Variables'
  • From 'System Variables' section, highlight 'Path' and click on 'Edit'
  • For windows 7 and 8 
          append ;path to the existing 'Variable Value'
          where
          path = absolute path to the bin directory of your vert.x extract

           eg:
                          ;C:\Users\User\Vertx\bin

  • For Windows 10 click 'New' and add the path with no semicolon. 
             eg:
                          C:\Users\User\Vertx\bin


Running Vert.x programs


Vert.x programs can be simply run using vert.x command line tools. 

eg: 
        vertx run myprogram.java
        vertx run myprogram.js
    


Java - Standard input and output in competitive programming

Java provides several classes for taking standard input and printing to standard output.


For input
  • Scanner class
  • BufferedReader and InputStreamReader classes
  • DataInputStream class
  • Console class
For output
  • PrintStream class (System.out.print)
  • BufferedWriter and OutputStreamWriter classes
  • PrintWriter class
We can use any of the above classes to interact with std in/out. But the performance of the above classes differ with the way they are implemented.

Sometimes the time taken to get user input or the time taken to print back to the user becomes important. One such occasion is competitive programming.

Competitive programming websites like hackerrank.com or codeforces.com sets timouts to run the solutions. These timeouts are generally set to check whether the competitor has solved the problem using an efficient algorithm.

But sometimes although the competitor has used an efficient algorithm, timeouts may occur. This is due to inefficiency in taking input or printing the output. Below is an implementation of a java class which can be easily used take input and print output efficiently. 

   

Saturday, May 28, 2016

Binary Search Tree Data Structure

Graph

A graph ‘G’ is defined as G = (V, E) Where V is a set of all vertices and E is a set of all edges in the graph.

Example
graph
In the above example, ab, ac, cd, and bd are the edges of the graph. Similarly, a, b, c, and d are the vertices of the graph.

Tree

A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree.
Tree 












Binary Tree

Binary tree is a tree in which every node has a maximum of two nodes connected.

 


Binary Search Tree

Binary Search tree is a binary tree with the following properties.


• The left subtree of a node contains only nodes with keys less than the node’s key.

• The right subtree of a node contains only nodes with keys greater than the node’s key.


• Both the left and right subtrees must also be binary search trees. 



BST




Binary search tree should be implemented considering the above properties.

BST.h file implements the data structure and functions of Binary Search Tree.
Please find a link on github to this same implementation at the bottom.

[code]
#ifndef _BST_
#define _BST_

#include <stdlib.h>
#include <limits.h>

/*data structure binary search tree*/
typedef struct bst_node
{
    int data;
    struct bst_node* left;
    struct bst_node* right;   
}bst;

/*
  allocate memory for a single
  node
  return the node
*/
bst* createBST();

/*
  add the given data to the
  given tree
*/
void addBST(bst* tree, int data);

/*
  print the tree in sorted
  order
*/
void printOrderedList(bst* tree);

/*
  free the memory allocated
  for the bst
*/
void destroyBST(bst* tree);

/*
  Delete the node with
  the given value from
  given bst
*/
bst* deleteBST(bst* tree, int data);

/*
  return 1 if given data is
  present in the given bst
  0 otherwise
*/
int findBST(bst* tree, int data);

/*
  copy the bst given in tree
  to bst given as copy
*/
void copyBST(bst* tree, bst* copy);

/*
  find the node with min value
  and return it
*/
bst* minValueNode(bst* tree);


/*Implementations*/

/**********************/
bst* createBST()
{
    bst* tree = malloc(sizeof(bst)); // allocate memory
    tree -> data = INT_MIN;
    tree -> left = NULL;
    tree -> right = NULL;
    return tree;
}

/**************************/
void destroyBST(bst* tree)
{
    if(tree == NULL)
        return;

    if(tree -> left != NULL)    
        destroyBST(tree -> left);
   
    if(tree -> right != NULL)
        destroyBST(tree -> right);
   
    free(tree);
}

/*********************************/
void copyBST(bst* tree, bst* copy)
{
    if(tree == NULL)
        return;
   
    addBST(copy, tree -> data);

    if(tree -> left != NULL)
        copyBST(tree -> left, copy);

    if(tree -> right != NULL)
        copyBST(tree -> right, copy);

   
}

/*******************************/
void addBST(bst* tree, int data)
{
    bst* node = malloc(sizeof(bst));
    node -> data = data;
    node -> right = NULL;
    node -> left = NULL;   

    if(tree -> data == INT_MIN) // if root is not entered yet
    {
        tree -> data = data;
        return;
    }

    if( (tree -> data) <= data) // if data should go to left
    {
        if( tree -> right == NULL)
        {
            tree -> right = node;
        }   
        else
            addBST(tree -> right, data);
    }
    else
    {
        if( tree -> left == NULL)
        {
            tree -> left = node;
        }   
        else
            addBST(tree -> left, data);
    }
   
   
}

/*********************************/
bst* deleteBST(bst* tree, int data)
{
    bst* tmp;
    if(tree == NULL)
        return tree;

    if(tree -> data > data)
        deleteBST(tree -> left, data);
    else if(tree -> data < data)
        deleteBST(tree -> right, data);
    else
    {
        if(tree -> left == NULL)
        {
            tmp = tree -> right;
            free(tree);
            return tmp;
        }
        else if(tree -> right == NULL)
        {
            tmp = tree -> left;
            free(tree);
            return tmp;
        }
        tmp = minValueNode(tree -> right); // find min node from right children
        tree -> data = tmp -> data;

        tree -> right = deleteBST(tree -> right, tmp -> data);//remove min node from right children
    }
    return tree;
}

/*********************************/
int findBST(bst* tree, int data)
{
    if(tree == NULL)
        return;

    if(tree -> left != NULL)
    {   
        if(findBST(tree -> left, data))
            return 1;
    }
   
    if(tree -> right != NULL)
    {
        if(findBST(tree -> right, data))
            return 1;
    }

    if(tree -> data == data)
    {
        return 1;
    }
    else
        return 0;
}

/************************/
int findMax(bst* tree)
{
    bst* tmp = tree;
    int val;

    while(tmp != NULL)
    {
        val = tmp -> data;
        tmp = tmp -> right;
    }
    return val;
}

/************************/
int findMin(bst* tree)
{
    bst* tmp = tree;
    int val;

    while(tmp != NULL)
    {
        val = tmp -> data;
        tmp = tmp -> left;
    }
    return val;
}

/*******************************/
void printOrderedList(bst* tree)
{
    if(tree == NULL)
        return;
    if(tree -> left == NULL && tree -> right == NULL)
    {
        printf("%d ",tree -> data);
        return;
    }
   
    if(tree -> left != NULL)
        printOrderedList(tree -> left);

    printf("%d ",tree -> data);
    if(tree -> right != NULL)
        printOrderedList(tree -> right);
   
}

/***************************/
bst* minValueNode(bst* tree)
{
    bst* tmp = tree;

    while (tmp -> left != NULL)
        tmp = tmp -> left;

    return tmp;
}


#endif
[/code]

test.c file demonstrate the functionalities of the BST implemented in BST.h file.

[code]
#include <stdio.h>
#include "BST.h"

void printArray(int arr[30]);
void populate(bst* tree, int arr[30]);

/*********/
int main()
{
    int randomNos[30];
    int num;
    bst* tree = createBST();
    bst* copy = createBST();
   
    printf("Adding random numbers to BST\n");
    populate(tree, randomNos);   

    printf("Populated order..\n");
    printArray(randomNos);

    printf("Printing ordered list from tree\n");
    printOrderedList(tree);
    printf("\n");
    printf("\n");
   
    printf("Copying BST to another BST..\n Printing it..\n");
    copyBST(tree, copy);
    printOrderedList(copy);
    printf("\n");
    printf("\n");

    printf("Max in the tree : %d \n",findMax(tree));
    printf("Min in the tree : %d \n",findMin(tree));
    printf("\n");

    printf("Enter a number find in the tree : \n");
    scanf("%d",&num);
   
    if(findBST(tree, num))
        printf("%d is in the tree\n",num);
    else
        printf("%d is not in the tree\n",num);

    printf("\n");

    printf("Removing %d from the tree..\n",randomNos[5]);
    tree = deleteBST(tree, randomNos[5]);
    printf("After removal\n");
    printOrderedList(tree);
    printf("\n");
   
    printf("Destroying BST...\n");
    destroyBST(tree);

    printf("\nPrinting tree after destroy..\n\n");
    printOrderedList(tree);
   

    return 0;
}

/************************************/
void populate(bst* tree, int arr[30])
{
    int i;
    srand(time(NULL));

    for(i = 0; i<30; i++)
    {
        arr[i] = rand()%50;
        addBST(tree, arr[i]);
    }
}

/****************************/
void printArray(int arr[30])
{
    int i;
   
    for(i = 0; i<30; i++)
        printf("%d ",arr[i]);
    printf("\n");
}

[/code]

Please visit here to view the code in github.

Sunday, February 14, 2016

Binary search of an ordered list of integers

Binary search is a fundamental algorithm in computer science. It is used to find the position of a given integer in a sorted list of integers. We don't have to iterate through the whole list, if we use this algorithm. Therefore it is an efficient algorithm for searching. The complexity of binary search algorithm is O(logN). 

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html

If N elements are there in the list, 
you will have to halve the list x times to find an element. (Halve the list until 1 element is left)

 1 = N / 2x
 2x = N
 x = log2 N

Therefore time complexity - O(logN)

[code]
#include <stdio.h>

int main()
{
    int arr[100];
    int n, i, el;

    printf("Enter the number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements\n");
    for(i = 0; i<n; i++)
    {
        scanf("%d",&arr[i]);
        if(i != 0 && arr[i-1]>arr[i])
        {
            printf("Please enter a sorted list!\n");
            return 0;
        }
    }

    printf("Enter the element to search\n");
    scanf("%d",&el);

    int position = binarySearch(arr,n,el);
   
    if(position != -1)
        printf("The element is at %d.\n",position);
    else
        printf("Element not found!\n");

    return 0;
}

/*Binary search function
  Arguments - integer array
          size of the array
          element to search for
  Return the position if successful
 
*/
int binarySearch(int arr[], int size, int el)
{
    int low = 0, high = size-1;
    int mid = (high + low)/2;

    while(arr[mid] != el)
    {
        if(arr[mid] > el)
            high = mid;
        else
            low = mid;

        if(high == low+1)
        {
            if(arr[high] == el)
                return high;
            else if(arr[low] == el)
                return low;
            else
                return -1;
        }
        mid = (low + high)/2;
    }
    return mid+1;
}[/code]

Saturday, February 6, 2016

Stack data structure implemented in C


Stack

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. Only two operations are allowed in a stack:

  • Push the item into the stack
  • Pop the item out of the stack
A stack is a limited access data structure - elements can be added and removed from the stack only at the top.


Following is an implementation of a stack in C

stack.h file contains all the implementations related to the stack. Please find a link on github.com for the same implementation below at the bottom.


[code]#include <stdlib.h>
#include <limits.h>

//functions and data structure are implemented in the header file

typedef struct node
{
    int pos;
    int data[SIZE];
   
}stack_node;

typedef stack_node* stack_ref;

//create a new stack
stack_ref stackCreate()
{
    stack_ref ref = malloc(sizeof(stack_node));
    (*ref).pos = 0;
    return ref;
}

//destroy an existing stack
int stackDestroy(stack_ref st)
{
    if(st != NULL)
    {
        free(st);
        return 1;
    }
    return 0;
}

//add a new element
int stackPush(stack_ref st,int el)
{
    if(!StackIsFull(st))
    {       
        (*st).data[(*st).pos] = el;
        (*st).pos++;
        return 1;
    }

    return 0;
}

//remove the last element
int stackPop(stack_ref st)
{
    if(StackIsEmpty(st))
    {
        return INT_MIN;
    }   
    (*st).pos--;
    return (*st).data[(*st).pos];
}

//peek at the top element
int stackPeak(stack_ref st)
{
    if(StackIsEmpty(st))
    {
        return INT_MIN;
    }   
    return (*st).data[(*st).pos-1];
}

//if stack is empty
int StackIsEmpty(stack_ref st)
{
    if((*st).pos == 0)
        return 1;
    return 0;
}

//if stack is full
int StackIsFull(stack_ref st)
{
    if((*st).pos == SIZE)
        return 1;
    return 0;
}
[/code]

reverse_string.c file is an example of how a stack can be used.



[code]

//define the stack size here
#define SIZE 50

#include <stdio.h>
#include "stack.h"
#include <string.h>


int main()
{
    char string[SIZE];
    char reverse[SIZE];
    int i,j;
   
    printf("Enter the string to reverse: \n");
    fgets(string, SIZE, stdin);
   
    //create stack for the string
    stack_ref st = stackCreate();
   
    for(i = 0; i<strlen(string); i++)
        stackPush(st, (int)string[i]); 
   
    for(i = 0; i<strlen(string); i++)
        reverse[i] = (char)stackPop(st);
   
    reverse[i] = 0;
   
    printf("Reversed string: %s\n",reverse);
    return 0;
}[/code]

Please visit here to view the code in github.com

Monday, February 1, 2016

Socket Programming - Simple UDP client and server programs. ( In C)

UDP

UDP is a simple transport-layer protocol. The application writes a message to a UDP socket, which is then encapsulated in a UDP datagram, which is further encapsulated in an IP datagram, which is sent to the destination.  
There is no guarantee that a UDP will reach the destination, that the order of the datagrams will be preserved across the network or that datagrams arrive only once. 

Server
  1. Listen for a client's requests.
  2. Process the requests.
  3. Return the results back to the client. 

Client
  1. Send the request to the server.
  2. Wait for the server's response.
Server Program

[code]

#include <sys/socket.h>
#include <netinet/in.h>
#include <strings.h>
#include <stdio.h>

int main(int argc, char**argv)
{
    int sockfd,n;
    struct sockaddr_in servaddr, cliaddr;
    socklen_t len;
    char mes[1000];
    char send[] = "Hello client!";
   
    sockfd=socket(AF_INET,SOCK_DGRAM,0);
   
    servaddr.sin_family = AF_INET;   
    servaddr.sin_addr.s_addr=htonl(INADDR_ANY);
    servaddr.sin_port=htons(32000);
   
    bind(sockfd,(struct sockaddr *)&servaddr,sizeof(servaddr));
    len = sizeof(cliaddr);
   
    while(1)
    {
        n=recvfrom(sockfd,mes,1000,0,(struct sockaddr*)&cliaddr,&len);
   
        sendto(sockfd,send,n,0,(struct sockaddr*)&cliaddr,sizeof(cliaddr));
        mes[n] = 0;
   
        printf("Client says: %s\n",mes);
    }   
    return 0;
}[/code]

Client Program

[code]

#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>


int main(int argc, char**argv)
{
    int sockfd,n;
    struct sockaddr_in servaddr;
    char send[] = "Hello server!";
    char recv[1000];

    if (argc != 2)
    {
        printf("usage:%s <IP address>\n",argv[0]);
        return -1;
    }
   
    sockfd=socket(AF_INET,SOCK_DGRAM,0);
    bzero(&servaddr,sizeof(servaddr));

    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr=inet_addr(argv[1]);
    servaddr.sin_port=htons(32000);

    sendto(sockfd,send,strlen(send),0,(struct sockaddr*)&servaddr,sizeof(servaddr));

    n=recvfrom(sockfd,recv,10000,0,NULL,NULL);

    recv[n]=0;
   
    printf("Server says: %s\n",recv);
    return 0;
}[/code]



Monday, November 23, 2015

Recursion in programming

Recursion is a very useful programming technique. It can be simply described as calling the function by the same function. It can be understood better by examples rather than by definitions. 

A recursive algorithm must have the following,
  1. Base Case (to stop recursive call at some point)
  2. Recursive Call
Example:

Finding factorial of a positive integer.

The factorial of a positive integer is multiplication of a series of descending natural numbers.
eg:
4! = 4 x 3 x 2 x 1

In the above example note the following property.

4! = 4 x (3 x 2 x 1)
4! = 4 x 3!

Therefore for any positive integer n,
n! = n x (n-1)!

The above property enables us to use recursion.
If we write a function to find the factorial of a positive integer, let's call it 'factorial(int number)',
then 
factorial(n) = n x factorial(n-1);
This is the recursive call. 

The base case is the factorial of 1. 
factorial(1) = 1;

Following is a program written in C to find factorial using a recursive algorithm.

[code]


#include <stdio.h>

int main()
{

      int number;
      printf("Enter an ineger: ");
      scanf("%d",&number);
      printf("The factorial is %d",factorial(number));

      return 0;

}

int factorial(int number)
{

      if(number == 1)
            return 1;

      return number*factorial(number-1);

}[/code]

Sunday, November 22, 2015

C program to find all combinations of user entered characters.

This program uses user entered characters(up to 8 characters) to generate all possible combinations of  these characters using every character entered. If duplicate characters are entered they will be treated as different characters. This can be useful in generating wordlists used in password cracking.
compiling : gcc -o program program.c -lm
[code]#include <stdio.h>
#include <math.h>  // compile the code with -lm to the end since ceil is used
#include <stdlib.h>

int size;

/*functions used*/
int min_num();
int max_num();
int to_int(int array[size]);
int* to_array(int num);
int is_bounded(int num);
int factorial(int num);

int main()
{
    printf("Enter the number of characters: ");
    scanf("%d",&size);
   
    if(size>8)
    {
        printf("Please enter a number less than 10\n");
        return 0;
    }

    char array[size];
    int i;       
    char c;

    printf("Enter characters seperated by space or newline\n");
    for(i=0; i<size; i++)
    {
        scanf("%c",&c);
        while(c==' ' || c=='\n')
        {
            scanf("%c",&c);
        }
        array[i] = c;       
    }   

    printf("There are %d number of possible combinations(combinations will include duplicate characters if you entered any!)\n",factorial(size));
    printf("Press enter to proceed.....\n");
    getchar();
    getchar();
   
    int iter = min_num();
    int max = max_num();

    int* arr;
   
    while(iter<=max)
    {
        if(is_bounded(iter))
        {   
            arr = to_array(iter);
            for(i=0; i<size; i++)
            {
                printf("%c",array[arr[i]-1]);       
            }
            printf("\n");
        }
        iter++;
    }
   
    return 0;
}

/***********************************************************/
/*returns the integer contructed by the given integer array*/
int to_int(int array[size])
{
    int i, ans = 0;
    for(i=0; i<size; i++)
    {
        ans = ans + array[i];
        ans = ans*10;
    }
    return ans/10;
}

/****************************************************************/
/*convert an integer number to an integer array
return a reference to the array*/
int* to_array(int num)
{
    int* array = malloc(sizeof(int)*size);
    double tmp1;
    int tmp2;
    double tmp3;
    int i;
    for(i = size-1; i>=0; i--)   
    {
        tmp1 = num/10.0;
        tmp2 = num/10;
        tmp3 = ceil((10*tmp1 - 10*tmp2));   
        array[i] = tmp3;
        num = num/10;
    }
    return array;
}

/*********************************************************/
/*check whether an integer has distict digits
and each digit is less than the number of digits
return 1 if conditions are met*/
int is_bounded(int num)
{
    int* array = to_array(num);
   
    int i,j;
    for(i = 0; i<size; i++)
    {
        for(j = 0; j<size && i!=j; j++)
        {
            if(array[i] == array[j])
                return 0;
        }
        if(array[i]>size || array[i]==0)
            return 0;
    }
    return 1;

}

/***********************************************************/
/*returns the maximum number that a number with 'size' number of digits
  and with concecutive digits from 1
  eg: if size = 4
      then max_num() returns 4321*/
int max_num()
{
    int i;
    int arr[size];
    int tmp = size;
    for(i = 0; i<size; i++)
    {
        arr[i] = tmp;
        tmp = tmp-1;
    }
    return to_int(arr);
}

/**************************************************************/
/*does the opposite of max_num()*/
int min_num()
{
    int i;
    int arr[size];
    for(i = 0; i<size; i++)
    {
        arr[i] = i+1;
    }
    return to_int(arr);

}

/*****************************************************************/
/*recursively return the factorial of a given number*/
int factorial(int num)
{
    if(num == 1)
        return 1;
    return num*factorial(num-1);

}[/code]

Example:
./program
Enter the number of characters: 3
Enter characters seperated by space or newline
a b c
There are 6 number of possible combinations(combinations will include duplicate characters if you entered any!)
Press enter to proceed.....

abc
acb
bac
bca
cab
cba


Saturday, October 11, 2014

Earn cash back for your purchases from Ebates!!

You can easily earn a part of the money you spend for a purchase on ebay ebates. It's free!!! It's like getting a discount. You can receive the pay back to your paypal account.
This site is not only for ebay, it is also available for amazon, walmart, livingsocial and etc.
Sign up and enjoy the cash backs!!. Simply click the following link to sign up.
http://www.ebates.com/rf.do?referrerid=prJehZWAYqOmg1SuONkOaw%3D%3D&eeid=26471http://www.ebates.com/rf.do?referrerid=prJehZWAYqOmg1SuONkOaw%3D%3D&eeid=26471



Sunday, October 5, 2014

How to buy items from ebay without a credit card(for Sri Lankans)?

In this post I'm  going to explain you the easiest way to purchase in ebay and get items posted to your home for Sri lankans. For this you will only need a savings bank account and a debit card.

The first step is to open a bank account. Commercial bank, Sampath bank and Hatton National banks allow international transactions. But the best bank to choose is Commercial bank. Because they issue an international Visa shopping debit card which is already activated for international transactions.

Go to your nearest Commercial bank and open a savings account.
Ask for a debit card application and fill it applying for a Visa shopping debit card. Not a master card. They charge Rs.400 for the card. Any bank does.
You can obtain the card within 15 minutes if you don't want your name printed on it.
If you want your name on the card, your card will sent via post within two weeks.

After you obtain your card check it's balance with an ATM. Then your card will be activated.

Then go to ww.ebay.com  website and register as a new user.







Enter your address and other details correctly. 
Then you will receive a confirmation email to your email address. Confirm it and sign in to your ebay account. 


Then visit www.paypal.com and make a new personal account. 
Enter your details correctly. 



Confirm the confirmation email that you will receive and sign in to your paypal account. 
Go to profile tab and select add/edit card. Enter your card details here. (Card number and other details). Then they will ask for a 3 digit number mentioned after the card number in your card. 
You will find it on the card. 

After that, you need to get your card verified. For this you need to transfer 1$  to paypal. Don't worry this will be credited back once the account is verified. 

The way to verify the account is,  when you transfer the money to paypal, the transaction will be recorded in your bank account. A four digit number will appear in your bank statement for this transaction. You simply can call your bank and ask for this number. They will ask your detail just to confirm that the owner is speaking. 

Enter this number in your paypal account and then you are verified. 
Now you are ready to purchase. 

Now go to ebay and find your items. 

Sometimes ebay sends coupons for new users.
Make sure you get a free shipping and buy it now item. Because sometimes shipping charges are more than the price of your item. Bidding items are not sure to have. Therefore when you search, go for advanced search and specify your search. 

In advanced search you can specify the price range, keyword and category.





You can also specify buying format and shipping option. 





You can find cheap items if you search the right way. 

Wednesday, April 10, 2013

Herbs to fight cancer



Garlic

Garlic is a very widely used herb in lowering both cholesterol and triglycerides. It also has anti-clotting and anti-bacterial properties and in addition, not many people know that it also has anti-tumor properties. Garlic contains phytochemicals which are helpful in getting rid of toxins and free radicals that are found inside the body.

Milk thistle

Milk thistle is a medicinal plant which is usually used to treat varicose veins, menstrual problems and depression. True to its name, it is also used to increase breast milk production in women. Milk thistle has also been used as to detoxify liver.

Turmeric

Turmeric is a yellow- orange spice that belongs to the same family as the ginger. Aside from being used as a spice for cooking, it is also used for its medicinal properties. Many researches have been made in order to prove that turmeric really is the wonder herb against cancer.

Sunday, March 31, 2013

Steps To Avoid Kidney Diseases.


  • Be Active 
  • Controlling of Blood Sugar Levels 
  • Blood Pressure Control 
  • Proper food and Control of Weight 
  • No Smoking 
  • Avoid Unnecessary Medicines 
  • Kidney Check-Up

Monday, March 18, 2013

Lie detection, is it true?


A lie detector or polygraph machine is used to aid in finding out if someone is truthfully answering a specific set of questions. It is a combination of various devices used to measure a person's physical responses to what are known as irrelevant, control and relevant questions. How this data is interpreted by the examiner will determine if the subject is telling the truth.

In a typical lie detection test the subject is asked a number of question before the actual test is performed. These are used to create what is known as a "baseline". How the subjects reaction to these question will help create the baseline. The subjects pulse, blood pressure, rate of breathing and how much they sweat could be all measured as physical responses to help create the baseline. When the actual test questions are asked the response to these questions is compared to the questions asked to create the baseline.

There are three types of questions asked. Some questions are irrelevant such as asking the subject what their name is. Others are called probable-lie control questions and often get an answer which is not truthful. This type of question could be asking the subject if they ever committed a crime. The type of question most important to the examiner is what is known as a relevant question. A relevant question would be like asking the subject if they committed the crime. If the subjects response to the probable-lie control question is greater than to the relevant questions, then the answer to the relevant question is considered truthful.

It should be noted many scientists do not consider a lie detector test to be very accurate. It is not considered scientific by many and therefore not accurate enough to be used in a court of law.

Thursday, March 14, 2013

Touch Screen and health


We are all fully aware of the anti-biotic resistant bacteria, which exists in our hospitals. There are all sorts of fungus, viruses, diseases, and other things that humans will have to deal with in the future along these lines. Yes, we will no doubt come up with nano-particles which will be able to defeat these types of bacteria, and other strategies such as using nano-copper material or titanium dioxide to help us. But, don't forget that there are real challenges we face in the future.

Also, let's not forget the reality that there are bio weapons being created, and mankind is busy experimenting with the modification of various species on the planet, including many crop species and foods that we eat through bio engineering. Sometimes these experiments can create unintended consequences, just as mankind's travel throughout the world brings with it the possibility of more diseases and viruses being introduced into our society and civilization, which is relatively stable and sterile to such human biosystem challenges.

One of the biggest problems they found in hospitals where people contracted MRSA was due to the remote control which would be passed to various individuals within the room of a hospital. Yes, something as simple as the TV clicker was spreading MRSA from patient to patient. Still even having all the hospital nurses and doctors continually wash their hands and change their gloves, MRSA could still spread relatively easily. This is a real problem.

Now then, what about all the touch screen systems that people will be using in the future. There are many touchscreen kiosks out there and there will be more in the future. They will have all types of germs on them, and the glass needs to be coded with nano copper material, titanium dioxide, or other such substances, this way they will be self-cleaning, and kill the bacteria, viruses, or diseases caused from the interaction with human tissue.

Wednesday, March 13, 2013

How to overcome side effects of mobile phones?


1. Use the external antenna in the car.
Most mobile phones have an attachment to the external antenna, all energy can be kept outside the vehicle.

2. Use hands-free device
Each place to keep your mobile is better than sticking it to the ear.

3. Use voice recognition
Instead of touching the mobile you can say what number you want to dial.

4. Use digital phones
Analog phones use about 1.3 Watts which twice as much as in digital phones (0.6W)

5. Make your conversations shorter
Cut it as short as possible

side effects
http://scienceloverr.blogspot.com/2013/03/side-effects-of-excessive-usage-of.html

Side effects of excessive usage of mobile phones


- nerves in the scalp are damaged

- blood cells leak hemoglobin

- headaches, fatigue

- loss of memory,

- the strange ringing in the ear, sense of smell is impaired

- retina may be damaged, eyes can get cancer

- the amount of white blood cells is reduced

- digestive problems may appear, bad levels of cholesterol are risen

- the barrier to viruses and toxins is open

- asthma is triggered

- the endocrine system stops working properly

- skin rash and burning sensation of skin is evoked

see also

http://scienceloverr.blogspot.com/2013/03/effects-of-usage-of-mobile-phones.html

Effects of usage of mobile phones.


Cell phones' electromagnetic radiation is said to cause brain cancer. Is it true? People are concerned about the fact that high levels of microwave radiation pose harmful hidden dangers and realize they demand protection that will ensure their safety and help them keep in a healthy and good condition. Although there are many shields available on the market the don't protect them against radiation from towers, antenna or masts. So what can we do to prevent ourselves from emission that kills our brain cells?
Mobile phones radiation
Mobile phones are used worldwide these days, the invention of pocket sized mobile phones startled the implementation of mobile phones into our daily lives. As far as I'm concerned, there are people who have a kind of emotional attitude to their mobiles, they would rather die than not use mobile at all. To make things worse, there are scant numbers of people who can imagine life without mobile phones and being in touch with their family or friends 24/7. Since mobile phones depend greatly on radiation there is a concern if they have any harmful effect on people's health. The industry tries to con the public and make them believe in lack of any negative effect of mobile phone industry as it brings billions of dollars every year.
So far, numerous studies and tests have been conducted to check whether mobiles are harmful or not. The controversy and debates over the effects of usage mobile phones and their possibility to cause brain tumors are of special interest of scientists, communication workers and ordinary people. The reason for such an interest is that cell phones belong to the group of products that emit electromagnetic radiation e.g microwave oven, electric clocks, computers or other appliances. This is non ionizing radiation which is claimed not to cause any damages to the cells. Ionizing radiation e.g. x-rays damages DNA of the cells, results in mutations and birth defects.
According to some researchers using a mobile phone has no direct effect on getting malignant brain tumors. The harmful effect of mobile phone is achieved through their thermal effect. This type of radiation causes dielectric heating which heats up living tissue - your one part of the head will be warm. This could be called microwave radiation - according to The Journal of Cellular Biochemistry this radiation interferes with DNA and destroys its repair mechanisms. Apart from that microwave radiation make cells age rapidly or cancerous cells grow quicker, as Italian scientists demonstrated.
Brain damages
Even tiny, minimal doses of radio frequency accumulate and lead to harmful effects and damage the brain cells. Although it is the antenna which is said to emit the biggest amount of radiation the mouthpiece and keypad also leak radiation, penetrates the brain, ear and eye tissues.

Side effects
http://scienceloverr.blogspot.com/2013/03/side-effects-of-excessive-usage-of.html

Optimized quick sort

In the previous article  we discussed about quick sort algorithm. In this article we are going to discuss about further optimizing quick sor...