Posts

Showing posts from 2014

Sudoku using dancing link - Java implementation

Image
Here is a algorithm which uses dancing link to solve algorithm X(exact cover) that solves upto 100*100 sudoku. Algorithm has been implemented using  JAVA and can be able to solve Sudoku of any difficulty level(easy,hard,very hard).
Algorithm works as follows:-
1.) Algorithm first find out the number of possible elements in each cell , algorithm for this can be seen in the code.
2.) After this apply rule1 which says finds  that cell which has a single possible element , this works recursively until we find single possible element.
3.) After this apply rule2 which says if there is a number which can go into only one cell, then assign that number to that cell.
4.) Rule2 and rule1 run recursively.
5.) Still if we find possible number of elements in some cell then create a dancing link for sudoku puzzle , reduce the puzzle in to exact cover form and solve it using algorithm X in a efficient way.To make it efficient,first we implemented rule1 and rule2 ,firstly algorithm try to solve sudoku…

Broadcast data using UDP in Java Socket Programming

Image
If we want client to automatically discover server IP,we can do this by broadcasting a data packet with some identifier to the server , server extracts the client IP and then server send some identifier to the client ,client then extracts the IP from the packet received from the server.Here are simple work flows that is similar to DHCP protocol:-

On the server side:-
1.) Open a socket on the server that listens to the UDP request.
2.) Make a loop that handles the UDP request and responses.
3.) Inside the loop,check the received UDP packed to see if its valid by identifier.
4.) Still inside the loop , send a response to the IP and port of the received packet.

On the client side:-
1.) Open a socket on a random port.
2.) Loop over the computer network interfaces and get their broadcast address.
3.) send the UDP Packet inside the loop to the interface's broadcast address.
4.) wait for a reply
5.) when we have a reply , check to see if the package is valid.
6.) When its valid, get the p…

Perfect Hashing and its implementation in C

Perfect hashing simply means hashing with no collision.But there is nothing like perfect hashing(no collision).These are just a work around to achieve perfect hashing.Using this we can able to search the large set of records in a constant time i.e O(1) time complexity.To achieve searching in strict O(1) time ,one needs to implement hash table and then search the given record in to hash table using hash function.
        Here in perfect hashing ,one need to implement two level hash table , first level hash table consist a set of pointers that points to the second level hash table,we must select hash function that first maps the key in to first level hash table,so it simply means there must be collision in first level hash table ,thats  why i am saying its just a work around to achieve prefect  hashing.We must wisely choose hash function:
                 h(x)=((a*x+b)mod p)mod m
x is the key to be map,
Here m is size of the hash table,we should choose m >2N(N=no of elements)
p is a…

C Program to insert/delete/traverse/display XOR Linked List

Here is the C Program to insert/delete/traverse/display XOR Linked List.XOR linked list is said to be memory efficient version of doubly linked list.

_________________________________________________________________________________

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct Node{
int data;
struct Node *ptr;
};
struct Node* XOR(struct Node *a,struct Node *b){
return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
void insertIntoXORLL(struct Node **head,int pos,int data){
struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
newNode->data=data;
if(*head==NULL){//Insert first Node
newNode->data=data;
newNode->ptr=NULL;
*head=newNode;
}else{
struct Node *current=*head;
struct Node *previous=NULL,*next=NULL;
struct Node *nextNode=NULL;
if(pos<=1){
newNode->ptr=XOR(previous,*head);
nextNode=XOR((*head)->ptr,previous);
(*head)->ptr=XOR(newNode,nextNode);
*head=newNode;
}else if(pos>1){
int count=1;
while(current!=NULL &&…

C Program to sort an array using insertion sort

I have seen couple of students who use swap in insertion sort to sort an array.Insertion sort is an example of exchange sort ,we don't swap two elements to sort an array ,instead of this we shift elements if ith element is greater than i+1th element to sort an array.It works on simple concept:-
Store the ith element in temporary variable and shift element until you find the element smaller than this element towards 0 index position.Here is the C Program to find insertion sort:-

_________________________________________________________________________________
#include <stdio.h>
#include <string.h>

main()
{
    int arrSize,i;
   printf("Enter Size of array:");
   scanf("%d",&arrSize);
   int array[arrSize];
   for(i=0;i<arrSize;i++){
       scanf("%d",&array[i]);
   }
   int temp,j;
   for(i=1;i<arrSize;i++){
       temp=array[i];
       for(j=i;j>0;j--){
           if(temp<array[j-1]){
               array[j]=array[j-1]…

Algorithm to find Max. sub sequence of length atleast l in linear time

Below is the code attached to calculate the max. subsequence of length atleast l in O(n) time.This algorithm works as follows:- 1.) calculate sum of first array L elements. and set running sum & maxsum equal to sum. 2.) for each element after L elements   a) calculate sum=sum+array[i]-array[i-L];   b) calculate runningsum=runningsum+array[i];   c) update runningsum if sum is greater than running sum.   d) update maxsubsequence if runningsum is greater than max subsequence. Please find the below code,you can try and run the below code on http://www.compileonline.com/compile_c_online.php Happy Coding
_________________________________________________________________________________
#include <stdio.h> #include <string.h> int findMaxSubsequence(int array[],int arrLength,int lenOfSubSequence){     int i,maxSubsquence,sum=0,runningsum=0;     for(i=0;i<arrLength;i++){         if((i+1)<=lenOfSubSequence){             sum=sum+array[i];             maxSubsquence=sum;          …

Algorithm to find Max. sub sequence of length exactly l in linear time

Below is the attached code to calculate max sub sequence of length l which is entered by user.Algorithm calculate the max subsequence in O(n) time.The logic are as follows:-
1.)Take two variable sum and maxsum.
2.)Run the algorithm till (i+1)<=l and calculate the sum.
3.)After when i+1)>l ,then it follows the recursion like this. sum(n)=sum(n-1)+array[i]-array[i-l] ,it shows sum of next elements of length l is equal to sum of previous l elements + current element - (first element in sum of previous element)

for an example:-
2 -1 -2 3 4
then it has following sum of length 3
1.) 2+(-1)+(-2)    = -2
2.) (-1)+(-2)+3     = -1
3.) (-2)+3+4       =   5
max sub sequence is 5.

Please find the below code ,you can try and  run the below code on http://www.compileonline.com/compile_c_online.php
Happy coding

_________________________________________________________________________________

#include <stdio.h>
#include <string.h>
int findMaxSubsequence(int array[],int arrLength,int…

Quick Sort algorithm to select random/middle/first/last element as a pivot

Below i have attached quick sort algorithm that can select pivot element position from the user for the first time and sort the array with  nlogn complexity.
Approx. in all the books ,algorithm shows to select  either first or last element as a pivot.This algorithm is able to select pivot position from user and sort the array elements accordingly.
Lets take an example:
95 5 1 3 7
try a quick sort dry run of this array elements on pen and paper,here 1 is a pivot element:-
1st pass:-1 5 95 3 7   (pivot element 1 is in final position)
2nd pass:-1 3 5 95 7  (now pivot element 5 is in final position)
3rd pass:-1 3 5 7 95   (pivot element 95 is in final position)

Just with the slight modification in the main & quick sort function , you can able to select middle element as a pivot element.To make a middle element as a pivot element,you only need to do three changes :
1.)Remove below two lines in the main function
   printf("Enter pivot element position===>\n");
   scanf(&qu…