<repo_name>vishpitama/Algorithms-1-Lab<file_sep>/Assignment 10/17CS30038_10.c
#include<stdio.h>
#include<stdlib.h>
typedef struct _rwd
{
	int start_time;
	int service_time;
}reqWD;	
typedef struct _rwd1
{
	int start_time;
	int service_time;
	int id;	
}reqWD1;
typedef struct _rsd 
{
	int service_time;
	int target_time;
} reqSD;
typedef struct _rsd1 
{
	int service_time;
	int target_time;
	int id;
} reqSD1;

void merge1(reqWD1 a[],int low ,int mid,int high)
{
    int i=low,j=mid+1;
    int k=0;
    reqWD1 *b=(reqWD1*)malloc((high-low+1)*sizeof(reqWD));
    while(i<=mid&&j<=high)
    {
        if(a[i].start_time>a[j].start_time)
        {
            b[k]=a[j];
            j++;
            k++;
        }
        else
        {
            b[k]=a[i];
            i++;
            k++;
        }
    }
    while(i<=mid)
    {
        b[k]=a[i];
        i++;
        k++;
    }
    while(j<=high)
    {
        b[k]=a[j];
        j++;
        k++;
    }
    for(i=low,k=0;i<=high;i++,k++)
    {
        a[i]=b[k];
    }
    return ;
}
void sort1(reqWD1 a[],int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        sort1(a,low,mid);
        sort1(a,mid+1,high);
        merge1(a,low,mid,high);
    }
}
void fun1(reqWD1* A,int n)
{
	reqWD1* B=(reqWD1*)malloc(sizeof(reqWD1)*n);
	int *keeper=(int* )malloc(n*sizeof(int));//stores counter no of ith index
	int i,j,index,max_count=1;
	B[0]=A[0];
	keeper[0]=0;
	for(i=1;i<n;i++)
	{
		for(j=0;j<max_count;j++)
		{
			if(B[j].start_time+B[j].service_time<=A[i].start_time)
			{
				B[j]=A[i];
				keeper[i]=j;
			//	count+++;
			//	maxcount++;
				break;
			}
			else
				continue;
			
		}
		if(j==max_count)
		{
			B[j]=A[i];
			keeper[i]=max_count;
	//		count++;
			max_count++;
		}	
	}
/*	for(int i=0;i<n;i++)
		printf("%d\n",keeper[i]);*/
	for(i=0;i<max_count;i++)
	{
		printf("counter %d::\n",i);
		for(j=0;j<n;j++)
		{
			if(keeper[j]==i)
			{
				printf("%d\t%d\t%d\n",A[j].id,A[j].start_time,A[j].start_time+A[j].service_time);
			}	
		}
	}
	return ;
}
void merge2(reqSD1 a[],int low ,int mid,int high)
{
    int i=low,j=mid+1;
    int k=0;
    reqSD1 *b=(reqSD1*)malloc((high-low+1)*sizeof(reqWD));
    while(i<=mid&&j<=high)
    {
        if(a[i].target_time>a[j].target_time)
        {
            b[k]=a[j];
            j++;
            k++;
        }
        else
        {
            b[k]=a[i];
            i++;
            k++;
        }
    }
    while(i<=mid)
    {
        b[k]=a[i];
        i++;
        k++;
    }
    while(j<=high)
    {
        b[k]=a[j];
        j++;
        k++;
    }
    for(i=low,k=0;i<=high;i++,k++)
    {
        a[i]=b[k];
    }
    return ;
}
void sort2(reqSD1 a[],int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        sort2(a,low,mid);
        sort2(a,mid+1,high);
        merge2(a,low,mid,high);
    }
}
void fun2(reqSD1* A,int n)
{
	int start_time=0;
	int end_time=0;

	for(int i=0;i<n;i++)
	{
		start_time=end_time;
		end_time=start_time+A[i].service_time;
		printf("request %d::  ",A[i].id);
		printf("%d  %d\n",start_time,end_time);	
		
	}
	return ;
}
int main()
{
	int n;
	printf("Enter the number of requests over weekday:\n");
	scanf("%d",&n);
	reqWD *rw=(reqWD*)malloc(n*sizeof(reqWD));
	reqWD1* RW=(reqWD1*)malloc(n*sizeof(reqWD1));
	printf("Enter the start time and length for each of the requests\n");
	for(int i=0;i<n;i++)
	{	
		printf("request no %d::",i);
		scanf("%d%d",&RW[i].start_time,&RW[i].service_time);
		RW[i].id=i;
		rw[i].start_time=RW[i].start_time;
		rw[i].service_time=RW[i].service_time;
		
	}			
	sort1(RW,0,n-1);
/*	for(int i=0;i<n;i++)
	{
		printf("%d: %d :: %d\n",RW[i].id,RW[i].start_time,RW[i].service_time);	
	}*/
	fun1(RW,n);



	int m;
	printf("Enter the number of requests over Saturday:\n");
	scanf("%d",&m);
	reqSD *sw=(reqSD*)malloc(m*sizeof(reqSD));
	reqSD1* SW=(reqSD1*)malloc(m*sizeof(reqSD1));
	printf("Enter the length and target time for each of the requests\n");
	for(int i=0;i<m;i++)
	{	
		printf("request no %d::",i);
		scanf("%d%d",&SW[i].service_time,&SW[i].target_time);
		SW[i].id=i;
		sw[i].service_time=SW[i].service_time;
		sw[i].target_time=SW[i].target_time;
		
	}
	sort2(SW,0,m-1);
	fun2(SW,m); 
	return 0;
}

<file_sep>/Assignment 12/17CS30038_12.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef struct node_
{
	int vno;
	struct node_* next;
}node;
typedef struct _vertex 
{
	node *adjlist; 
} vertex;
typedef vertex *graph;
void printlist(graph G,int v)
{
	node* tmp;
	for(int i=0;i<v;i++)
	{
		printf("vertex %d:",i);
		tmp=G[i].adjlist;
		while(tmp!=NULL)
		{
			printf("%d ",tmp->vno);
			tmp=tmp->next;	
		}
		printf("\n");
	}	
	return ;
}
void dfsvisit(graph G,int *visit,int i,int rem)
{
	visit[i]=1;
	node* tmp=G[i].adjlist;
	while(tmp!=NULL)
	{
		if(tmp->vno==rem)
		{
			tmp=tmp->next;
		}
		else
		{
			if(!visit[tmp->vno])
			dfsvisit(G,visit,tmp->vno,rem);
			tmp=tmp->next;
		}
	}	
}

int DFSComp (graph G,int v, int rem)
{
	int *visit=(int*)malloc(v*sizeof(int));
	for(int i=0;i<v;i++)
		visit[i]=0;
	int t=0;
	for(int i=0;i<v;i++)
	{
		if(i==rem)
			continue;
		else
		{
			if(visit[i]==0)
			{
				dfsvisit(G,visit,i,rem);
				t++;
			}
		}
	}
	return t;	
}
void findCritical (graph G,int v)
{
	printf("Critical junctions using the simple algorithm:\n");
	for(int i=0;i<v;i++)
	{
		int k=DFSComp (G,v, i);
		if(k>1)
		{
			printf("vertex %d : %d components\n",i,k);
			
		}
	}
	return ;
}
int dfsvisit2(graph G,int *visit,int* low,int* d,int* P,int i,int* time)
{
	int t=INT_MAX;;
	visit[i]=1;
	d[i]=*time;
	(*time)++;
	node* tmp=G[i].adjlist,*tmp2;
	tmp2=tmp;
	while(tmp2!=NULL)
	{
		if(low[tmp2->vno]>d[i])
			low[tmp2->vno]=d[i];
		tmp2=tmp2->next;
	}
	while(tmp!=NULL)
	{
		
		if(!visit[tmp->vno])
		{	
			P[tmp->vno]=i;
			t=dfsvisit2(G,visit,low,d,P,tmp->vno,time);
			if(t<low[i])
				low[i]=t;		
		}
		tmp=tmp->next;
		
	}
	return low[i];
}
void findCriticalFast (graph G,int v)
{
	int *visit=(int*)malloc(v*sizeof(int));
	int *low=(int*)malloc(v*sizeof(int));
	int* d=(int*)malloc(v*sizeof(int)); 
	int* P=(int*)malloc(v*sizeof(int)); 
	for(int i=0;i<v;i++)
	{	
		d[i]=INT_MAX;
		low[i]=INT_MAX;			
		visit[i]=0;
		P[i]=-1;
	}
	int time=1;
	for(int i=0;i<v;i++)
	{
	
		if(visit[i]==0)
		{
			dfsvisit2(G,visit,low,d,P,i,&time);
			
		}
	
	}
	int t=0;
	for(int i=1;i<v;i++)
	{
		if(low[i]<d[P[i]])
		printf("%d\t",i);
	}
	printf("\n");
	return ;
}
int main()
{
	int v,e,deg;
	node *tmp;
	printf("Enter the number of vertices and edges\n");
	scanf("%d%d",&v,&e);
	graph A=(graph)malloc(v*sizeof(vertex));
	for(int i=0;i<v;i++)	
	{
		A[i].adjlist=NULL;
	}
	printf("Enter the neighbors for each of the vertex\n");
	for(int i=0;i<v;i++)
	{
		printf("enter the degree of vertex %d :\n",i);
		scanf("%d",&deg);		
		printf("enter neighbours\n");
		for(int j=0;j<deg;j++)
		{
			tmp=(node*)malloc(sizeof(node));
			scanf("%d",&tmp->vno);
			tmp->next=A[i].adjlist;
			A[i].adjlist=tmp;
		}
		
	}
	printlist(A,v);
	findCritical (A, v);
	findCriticalFast (A, v);
	
}
<file_sep>/Assignment 7/17CS30038_7.c
#include<stdio.h>
#include<stdlib.h>

#define MAX_SIZE 100

int parent(int i)
{
	return i/2;
}
int left(int i)
{
	return 2*i;
}
int right(int i)
{
	return 2*i+1;
}
typedef struct _job
{
	int jobId;
	int startTime;
	int jobLength;
	int remLength;
} job;

typedef struct _heap
{
	job list[MAX_SIZE];
	int index_list[MAX_SIZE];
	int numJobs;
} heap;

typedef struct _jobPair
{
	int jobid_from;
	int jobid_to;
} jobPair;


void initHeap(heap *H)
{
	H->numJobs=0;
	for(int i=1;i<MAX_SIZE;i++)
		H->index_list[i]=-1;
}

void insertJob(heap *H,job j)
{
	int x,i;
	job temp;
	int temp_index;
	//printf("H->numJobs:%d",H->numJobs);
	H->list[++(H->numJobs)]=j;
	H->index_list[j.jobId]=H->numJobs;
	i=H->numJobs;
	//printf("i:%d",i);
	while(parent(i)>0)
	{
		if(H->list[parent(i)].remLength > H->list[i].remLength )
		{
			temp=H->list[parent(i)];
			H->list[parent(i)]=H->list[i];
			H->list[i]=temp;
			
			H->index_list[H->list[i].jobId]=i;
			H->index_list[H->list[parent(i)].jobId]=parent(i);
			

			i=parent(i);
		}
		else if( (H->list[parent(i)].remLength == H->list[i].remLength) && (H->list[parent(i)].jobId > H->list[i].jobId) )
		{
			temp=H->list[parent(i)];
			H->list[parent(i)]=H->list[i];
			H->list[i]=temp;
			
			
			H->index_list[H->list[i].jobId]=i;
			H->index_list[H->list[parent(i)].jobId]=parent(i);

			i=parent(i);
		}
		else
			break;
	}

	
}
void min_heapify(heap *H,int i)
{
	int smallest=i;
	if ( (left(i)<=H->numJobs) && ( (H->list[left(i)].remLength < H->list[i].remLength) || ( (H->list[left(i)].remLength==H->list[i].remLength) && (H->list[left(i)].jobId<H->list[i].jobId) ) )  ) 
		smallest=left(i);
	if( (right(i)<=H->numJobs) && ( (H->list[right(i)].remLength < H->list[smallest].remLength) || ( (H->list[right(i)].remLength==H->list[smallest].remLength) && (H->list[right(i)].jobId<H->list[smallest].jobId) ) ) )
		smallest=right(i);
	if(smallest!=i)
	{
		job temp;
		temp=H->list[smallest];
		H->list[smallest]=H->list[i];
		H->list[i]=temp;
		
		H->index_list[H->list[smallest].jobId]=smallest;
		H->index_list[H->list[i].jobId]=i;

		min_heapify(H,smallest);
	}
}
int extractMinJob(heap *H,job *j)
{
	if(H->numJobs==0)
		return -1;
	else
	{
		*j=H->list[1];
		H->list[1]=H->list[(H->numJobs)--];
		H->index_list[H->list[1].jobId]=1;
		min_heapify(H,1);
		return 0;
	}
}

void printHeap(heap *H,int n)
{
	int i;
	printf("\n JobId--startTime--jobLength--remLength--%d",H->numJobs);
	for(i=1;i<=H->numJobs;i++)
	{
		printf("\n %d -- %d -- %d -- %d",H->list[i].jobId,H->list[i].startTime,H->list[i].jobLength,H->list[i].remLength);
	}
	printf("\nindex_list:JobId--index_location");
	for(i=1;i<=n;i++)
	{
		printf("\n%d--%d\n",i,H->index_list[i]);
	}
}

void bubble_sort(job joblist[],int n)
{
	int i,j,flag;
	job temp;
	for(i=0;i<n-1;i++)
	{
		flag=0;
		for(j=0;j<n-i-1;j++)
			if(joblist[j].startTime>joblist[j+1].startTime)
			{
				flag=1;
				temp=joblist[j];
				joblist[j]=joblist[j+1];
				joblist[j+1]=temp;
			}
		if(flag==0)
			break;
	}
}

void bubble_sort2(jobPair pairList[],int n)
{
	int i,j,flag;
	jobPair temp;
	for(i=0;i<n-1;i++)
	{
		flag=0;
		for(j=0;j<n-i-1;j++)
			if(pairList[j].jobid_from>pairList[j+1].jobid_from)
			{
				flag=1;
				temp=pairList[j];
				pairList[j]=pairList[j+1];
				pairList[j+1]=temp;
			}
		if(flag==0)
			break;
	}
}

void decreaseKey(heap *H,int jid)
{
	//printf("K");
	//printf("%d",H->list[H->index_list[jid]].remLength);
	if(H->list[H->index_list[jid]].remLength==H->list[H->index_list[jid]].jobLength)
		H->list[H->index_list[jid]].jobLength=H->list[H->index_list[jid]].jobLength/2;
	H->list[H->index_list[jid]].remLength=(H->list[H->index_list[jid]].remLength)/2;
	//printf("---%d",H->list[H->index_list[jid]].remLength);
}




void newScheduler(job joblist[], int n,jobPair pairList[],int m)
{
	heap H;
	initHeap(&H);
	job current;
	current.remLength=-1;
	int time=0,i;
	int index=0;
	int job_flag=0;
	float turn=0;
	float number=0;
	int pairList_index[MAX_SIZE];
	int j=0;
	for(i=1;i<=n;i++)
	{
		if(i==pairList[j].jobid_from)
		{
			pairList_index[i]=pairList[j].jobid_to;
			j++;
		}
		else
			pairList_index[i]=0;
	}
	//for(i=1;i<=n;i++)
	//{
	//	printf("\n%d--%d",i,pairList_index[i]);
	//}
	
	printf("Jobs scheduled at each timestep are:");
	do
	{
		
		if(joblist[index].startTime==time)
		{
			do
			{
			if(time==0)
				insertJob(&H,joblist[index]);
			else
			{
				if(joblist[index].remLength<current.remLength || (joblist[index].remLength==current.remLength && joblist[index].jobId<current.jobId) )
				{
					insertJob(&H,current);
					current=joblist[index];
					
				}
				else
				{
					insertJob(&H,joblist[index]);
				}
			}
			index++;	
			}while( index<n && joblist[index].startTime==joblist[index-1].startTime);
		}
		if(current.remLength==0)
		{
			//printf(" ->%d",current.jobId-1);
			if(pairList_index[current.jobId]!=0)
			{
				//printf("-%d-",pairList_index[current.jobId]);
				decreaseKey(&H,pairList_index[current.jobId]);
				i=H.index_list[pairList_index[current.jobId]];
				job temp;
				while(parent(i)>0)
				{
					if(H.list[parent(i)].remLength > H.list[i].remLength )
					{
						temp=H.list[parent(i)];
						H.list[parent(i)]=H.list[i];
						H.list[i]=temp;
				
						H.index_list[H.list[i].jobId]=i;
						H.index_list[H.list[parent(i)].jobId]=parent(i);
				
	
						i=parent(i);
					}	
					else if( (H.list[parent(i)].remLength == H.list[i].remLength) && (H.list[parent(i)].jobId > H.list[i].jobId) )
					{
						temp=H.list[parent(i)];
						H.list[parent(i)]=H.list[i];
						H.list[i]=temp;
						
				
						H.index_list[H.list[i].jobId]=i;
						H.index_list[H.list[parent(i)].jobId]=parent(i);
		
						i=parent(i);
					}
					else
						break;
				}
				
			}
			extractMinJob(&H,&current);
			//printf("--%d %d--",current.jobLength,current.remLength);
			
		}
		if(time==0)
		{
			extractMinJob(&H,&current);
		}
		if(current.jobLength==current.remLength)
		{
				
				turn=turn+time-current.startTime;
		}
		current.remLength--;
		time++;	
		printf(" %d ",current.jobId);	
	}while( current.remLength!=0 || H.numJobs!=0);	
	printf("\n Average Turnaround time is: %f",turn/n); 
}

void main()
{
	
	int n,i,m;
	job temp;
	job temp2;
	printf("Enter number of jobs (n): ");
	scanf("%d",&n);

	job *joblist= (job*)malloc((n)*sizeof(job));
	for(i=0;i<n;i++)
	{
		scanf("%d",&(joblist[i].jobId));
		scanf(" %d",&(joblist[i].startTime));
		scanf(" %d",&(joblist[i].jobLength));
		joblist[i].remLength=joblist[i].jobLength;
	}
	bubble_sort(joblist,n);
	printf("Input number of job-dependancies:");
	scanf("%d",&m);
	jobPair *pairList= (jobPair*)malloc((m)*sizeof(jobPair));
	for(i=0;i<m;i++)
	{
		scanf("%d",&pairList[i].jobid_from);
		scanf("%d",&pairList[i].jobid_to);
		
	}
	bubble_sort2(pairList,m);
	newScheduler(joblist,n,pairList,m);

	if(joblist!=NULL)
	{
		free(joblist);
		joblist=NULL;
	}
	if(pairList!=NULL)
	{
		free(pairList);
		pairList=NULL;
	}


	/*
	printf("\nJobid_from,Jobid_to");
	for(i=0;i<m;i++)
		printf("\n%d--%d",pairList[i].jobid_from,pairList[i].jobid_to);
		
	heap H;
	initHeap(&H);
	for(i=0;i<n;i++)
	{
		scanf("%d",&(temp.jobId));
		scanf(" %d",&(temp.startTime));
		scanf(" %d",&(temp.jobLength));
		temp.remLength=temp.jobLength;
		insertJob(&H,temp);
		printf("\n \n");
		printHeap(&H,n);
	}
	printf("\n \n");
	extractMinJob(&H,&temp);
	printf("\n %d -- %d -- %d -- %d",temp.jobId,temp.startTime,temp.jobLength,temp.remLength);
	printf("\n \n");
	printHeap(&H,n);
	printf("\n \n");
	extractMinJob(&H,&temp);
	printf("\n %d -- %d -- %d -- %d",temp.jobId,temp.startTime,temp.jobLength,temp.remLength);
	printf("\n \n");
	printHeap(&H,n);*/
	
}





















<file_sep>/Assignment 4/17CS30038_4.c
//<NAME>
//17CS10061

#include<stdio.h>
#include<stdlib.h>


typedef struct node
{
	int value;
	struct node *left;
	struct node *right;
	struct node *parent;
}NODE, *NODEPTR;

void preOrder(NODEPTR root)
{
	if(root!=NULL)
	{
		printf(" %d ",root->value);
		preOrder(root->left);
		preOrder(root->right);
	}
}

void inOrder(NODEPTR root)
{
	if(root!=NULL)
	{
		inOrder(root->left);
		printf(" %d ",root->value);
		inOrder(root->right);
	}
}
NODEPTR search(NODEPTR x,int k)
{
	if(x==NULL)
		return NULL;
	else if ( x->value == k)
		return x;
	else if ( x->value > k)
		return search(x->left,k);
	else
		return search(x->right,k);
}
NODEPTR right_rotate(NODEPTR root, NODEPTR x)
{
	NODEPTR y=NULL;
	y=x->left;
	x->left=y->right;
	if(y->right!=NULL)
		y->right->parent=x;
	y->parent=x->parent;
	if(x->parent==NULL)
		root=y;
	else if(x->parent->left==x)
		x->parent->left=y;
	else
		x->parent->right=y;
	y->right=x;
	x->parent=y;
	return root;
	
}

NODEPTR left_rotate(NODEPTR root, NODEPTR x)
{
	NODEPTR y=NULL;
	y=x->right;
	x->right=y->left;
	if(y->left!=NULL)
		y->left->parent=x;
	y->parent=x->parent;
	if(x->parent==NULL)
		root=y;
	else if(x->parent->right==x)
		x->parent->right=y;
	else
		x->parent->left=y;
	y->left=x;
	x->parent=y;
	return root;
	
}

NODEPTR makeRoot(NODEPTR root, NODEPTR N)
{
	if(root->left==N)
		root=right_rotate(root,root);
	else if(root->right==N)
		root=left_rotate(root,root);
	return root;
}

NODEPTR sameOrientation(NODEPTR root, NODEPTR N)
{
	if( ( N->parent->parent->left == N->parent) && (N->parent->left==N ) )
	{
		root=right_rotate(root,N->parent->parent);
		root=right_rotate(root,N->parent);
	} 
	else if ( ( N->parent->parent->right == N->parent) && (N->parent->right==N) )
	{
		root=left_rotate(root,N->parent->parent);
		root=left_rotate(root,N->parent);
	}
	return root;
}

NODEPTR oppositeOrientation(NODEPTR root, NODEPTR N)
{
	if( (N->parent->parent->left == N->parent) && (N->parent->right==N) )
	{
		root=left_rotate(root,N->parent);
		root=right_rotate(root,N->parent);
	}
	else if( (N->parent->parent->right == N->parent) && (N->parent->left==N) )
	{
		root=right_rotate(root,N->parent);
		root=left_rotate(root,N->parent);
	}
	return root;
}
NODEPTR lift_insert(NODEPTR root,NODEPTR N)
{
	while(N!=root)
	{
		if(N->parent==root)
			root=makeRoot(root,N);
		else if ( ( ( N->parent->parent->left == N->parent) && (N->parent->left==N ) ) || ( ( N->parent->parent->right == N->parent) && (N->parent->right==N) ) )
			root=sameOrientation(root,N);
		else if ( ( ( N->parent->parent->left == N->parent) && (N->parent->right==N) ) || ( (N->parent->parent->right == N->parent) && (N->parent->left==N) ) )
			root=oppositeOrientation(root,N);
	}
	return root;
}






NODEPTR insert(NODEPTR x,int key)
{
	int input=key;
	if (x==NULL)
	{
		x=(NODE*)malloc(sizeof(NODE));
		x->value = input;
		x->parent = NULL; 
		x->left=NULL;
		x->right=NULL;
		return x;
	}
	else 
	{
		NODEPTR temp=x;
		while(temp!=NULL)
		{
			if( temp->value > input ) //input < temp->value
			{
				if(temp->left == NULL)
				{
					temp->left=(NODE*)malloc(sizeof(NODE));
					(temp->left)->value=input;
					(temp->left)->parent = temp; 
					(temp->left)->left=NULL;
					(temp->left)->right=NULL;
					temp=temp->left;
					break;
				}
				else
					temp=temp->left;
			}
			else if( temp->value < input ) //input > x->value
			{
				if(temp->right == NULL)
				{
					temp->right=(NODE*)malloc(sizeof(NODE));
					(temp->right)->value=input;
					(temp->right)->parent = temp; 
					(temp->right)->left=NULL;
					(temp->right)->right=NULL;
					temp=temp->right;
					break;
				}
				else
					temp=temp->right;
			}
		}
		x=lift_insert(x,temp);
		return x;
	}
}

NODEPTR leftmost(NODEPTR root)
{
	while (root != NULL && root->left != NULL)
       		 root = root->left;
    	return root;
}
NODEPTR rightmost(NODEPTR root)
{
	while (root != NULL && root->right != NULL)
       		 root = root->right;
    	return root;
}

NODEPTR successor(NODEPTR x)
{
	if (x->right != NULL)
	{
     		return leftmost(x->right);
	}
	if(x->right==NULL)
	{
		while(x==x->parent->right)
			x=x->parent;
		return x->parent;
	}
}

NODEPTR delete(NODEPTR root, int key)
{
	NODEPTR N;
	N=search(root,key);
	NODEPTR M=N->parent;
	while(root!=NULL)
	{
		if(N->left==NULL && N->right==NULL)
		{
			if(N->parent==NULL) 
				return NULL;
			NODEPTR temp=N->parent;
			if(temp->left==N)
				temp->left=NULL;
			else
				temp->right=NULL;
			N->parent=NULL;
			break;
		}
		else if(N->left==NULL)
		{
			NODEPTR temp=N->right;
			N->right==NULL;
			temp->parent=N->parent;
			if(N->parent!=NULL)
			{
				if(temp->parent->left==N)
					temp->parent->left=temp;
				else
					temp->parent->right=temp;
			}
			else
				root=temp;
			N->parent=NULL;
			break;
		}
		else if(N->right==NULL)
		{
			NODEPTR temp=N->left;
			N->left=NULL;
			temp->parent=N->parent;
			if(N->parent!=NULL)
			{
				if(temp->parent->left==N)
					temp->parent->left=temp;
				else
					temp->parent->right=temp;
			}
			else
				root=temp;
			N->parent=NULL;
			break;
		}
		else
		{
			NODEPTR temp=successor(N);
			N->value=temp->value;
			N=temp;	
		}	
	}
	if(M!=NULL)
	{
		root=lift_insert(root,M);
	}
	return root;
	
}

void main()
{
	int n,i,s,l;
	NODEPTR root=NULL,current=NULL;
	printf("Enter the number of insertions:");
	scanf("%d",&n);
	printf("Input Numbers to be inserted:");
	for(i=0;i<n;i++)
	{
		scanf("%d",&s);
		if(search(root,s)==NULL)
		{
			root=insert(root,s);
		}
	}
	printf("\nPreorder traversal:");
	preOrder(root);
	printf("\nInorder traversal:");
	inOrder(root);
	printf("\nEnter the number of deletions:");
	scanf("%d",&l);
	for(i=0;i<l;i++)
	{
		printf("\nInput value to be deleted:");
		scanf("%d",&s);
		if(search(root,s)!=NULL)
		{
			root=delete(root,s);
			printf("\nPreorder traversal:");
			preOrder(root);
			printf("\nInorder traversal:");
			inOrder(root);
			printf("\n");
		}
		else
			printf("Number not found\n");
	}
}



















<file_sep>/Assignment 1/17CS30038_1.c
#include<stdio.h>
#include<stdlib.h>
 #include<stdint.h>
struct node
{
	int data;
	struct node *xor;
};

struct node *xor(struct node *a,struct node *b)
{
    return (struct node*) ((uintptr_t) a ^ (uintptr_t) b);
}
void trafte(struct node *head)
{
	int i;
	struct node* temp=NULL,*prev=NULL,*temp2;
	temp=head;
	printf("front to end traversal\n");
	printf("%d\t",temp->data);
	temp=temp->xor;
	prev=head;
	while(xor(temp->xor,prev))
	{
		printf("%d\t",temp->data);
		temp2=prev;
		prev=temp;
		temp=xor(temp->xor,temp2);
	}

	printf("%d\n",temp->data);	
}
int main()
{
	int n;
	scanf("%d",&n);
	struct node * front=NULL,*end,*move,*temp,*prev,*temp2;	;
	int i=0;
	for(i=0;i<n;i++)
	{
		move=(struct node*)malloc(sizeof(struct node*));
		move->data=rand()%100;
		move->xor=NULL;
		if(front==NULL)
		{
			front=move;
		}
		else
		{
			prev->xor=move;
			
		}
		prev=move;
	}
	end=move;
	move=front;
	prev=NULL;
	for(int i=0;i<n-1;i++)
	{
		temp=move->xor;
		temp2=move;
		move->xor=xor(prev,temp);
		move=temp;
		prev=temp2;
			
	}
	move->xor=prev;
	trafte(front);
	return 0;
	
}
<file_sep>/Assignment 6/17CS30038_6.c
#include<stdio.h>
#include<stdlib.h>
void combine(int A[], int left, int middle, int right)
{
	int i=left,j=middle+1,k=0;
	int *b;
	b=(int*)malloc(sizeof(int)*(right-left+1));
	while(i<=middle&&j<=right)
	{
		if(A[i]<=A[j])
		{
			b[k]=A[i];
			i++;
			k++;
			
		}
		else
		{
			b[k]=A[j];
			k++;
			j++;
		}
	}
	while(i<=middle)
	{
		b[k]=A[i];
		i++;
		k++;
			
	}
	while(j<=right)
	{
		b[k]=A[j];
		k++;
		j++;
	}	
	for(i=left,k=0;i<=right;k++,i++)
	{
		A[i]=b[k];
	}	
	free(b);
	return;
}
void superbSorting(int A[], int sizeOfA)
{
	int block=1;
	int i,left,middle,right;
	for(block=1;block<=sizeOfA;block*=2)
	{
		for(i=0;i<sizeOfA;i+=block*2)
		{
			left=i;
			right=i+2*block-1;
			if(right>=sizeOfA)
				right=sizeOfA-1;
			middle=left+block-1;
			combine(A, left,  middle, right);
		}
	}
}
int compare1(int X[],int sizeOfX,int x,int y)
{
	int i,x_pos,y_pos;
	for(i=0;i<sizeOfX;i++)
	{
		if(X[i]==x)
			x_pos=i;
		if(X[i]==y)
			y_pos=i;
	}
	if(x_pos<y_pos)
		return 1;	
	
	else
		return -1;

}
void combine1(int A[], int left, int middle, int right, int B[], int sizeOfB)
{
	int i=left,j=middle+1,k=0;
	int *b;
	b=(int*)malloc(sizeof(int)*(right-left+1));
	while(i<=middle&&j<=right)
	{
		if(compare1(B,sizeOfB,A[i],A[j])==1)
		{
			b[k]=A[i];
			i++;
			k++;
			
		}
		else
		{
			b[k]=A[j];
			k++;
			j++;
		}
	}
	while(i<=middle)
	{
		b[k]=A[i];
		i++;
		k++;
			
	}
	while(j<=right)
	{
		b[k]=A[j];
		k++;
		j++;
	}	
	for(i=left,k=0;i<=right;k++,i++)
	{
		A[i]=b[k];
	}	
	free(b);
	return;
}
void superbSorting1(int A [], int sizeOfA, int B[], int sizeOfB)
{
	int block=1;
	int i,left,middle,right;
	for(block=1;block<=sizeOfA;block*=2)
	{
		for(i=0;i<sizeOfA;i+=block*2)
		{
			left=i;
			right=i+2*block-1;
			if(right>=sizeOfA)
				right=sizeOfA-1;
			middle=left+block-1;
			combine1(A, left,  middle, right,B,sizeOfB);
		}
	}
}
void F_combine(int A[], int left, int middle, int right,int B[])
{
	int i=left,j=middle+1,k=0;
	int *b;
	b=(int*)malloc(sizeof(int)*(right-left+1));
	while(i<=middle&&j<=right)
	{
		if(B[A[i]]<B[A[j]])
		{
			b[k]=A[i];
			i++;
			k++;
			
		}
		else
		{
			b[k]=A[j];
			k++;
			j++;
		}
	}
	while(i<=middle)
	{
		b[k]=A[i];
		i++;
		k++;
			
	}
	while(j<=right)
	{
		b[k]=A[j];
		k++;
		j++;
	}	
	for(i=left,k=0;i<=right;k++,i++)
	{
		A[i]=b[k];
	}	
	free(b);
	return;
}
void F_sort(int A [], int sizeOfA, int B[])
{
	int block=1;
	int i,left,middle,right;
	for(block=1;block<=sizeOfA;block*=2)
	{
		for(i=0;i<sizeOfA;i+=block*2)
		{
			left=i;
			right=i+2*block-1;
			if(right>=sizeOfA)
				right=sizeOfA-1;
			middle=left+block-1;
			F_combine(A, left,  middle, right,B);
		}
	}
}
int main()
{
	int i,n,*A;
	printf("Enter number of numbers in the array A :\n");
	scanf("%d",&n);
	printf("\n");
	A=(int*)malloc(n*sizeof(int));
	printf("Enter numbers in the arrayA:\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
	}  
	printf("\nnon decreasing order\n");
	superbSorting(A,n);
	for(i=0;i<n;i++)
	{
		printf("%d\t",A[i]);
	}
	printf("\n");



 	printf("\nArray conversion+++++++\n");
	int n1,*A1,*B;
	A1=(int*)malloc(n*sizeof(int));
	printf("Enter numbers in the arrayA1:\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&A1[i]);
	}
	printf("Enter number of numbers in the array B:\n");
	scanf("%d",&n1);
	printf("\nenter elements of B:\n");
	B=(int*)malloc(n1*sizeof(int));  
	for(i=0;i<n1;i++)
	{
		scanf("%d",&B[i]);
	} 
	printf("\nrearranged order\n");
	superbSorting1(A1,n,B, n1);
	for(i=0;i<n;i++)
	{
		printf("%d\t",A1[i]);
	}
	printf("\n");
	free(A1);
	free(B);



	printf("\nFaster Algo++++++++++++++\n");
	int *B1,tmp,m;
	B1=(int*)malloc(sizeof(int)*10*n);
	printf("re-enter A for faster algo:\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
	}
	printf("Re-enter number of numbers in the array B for fast algo:\n");
	scanf("%d",&m);
	printf("\nenter elements of B:\n");
	for(i=0;i<m;i++)
	{
		scanf("%d",&tmp);
		B1[tmp]=i;
		
	}
	F_sort(A, n, B1);
	printf("reaaranged A using faster algorithm:\n"); 
	for(i=0;i<n;i++)
	{
		printf("%d\t",A[i]);
	}
	printf("\n");
	free(A);
	free(B1); 
	return 0;
}
<file_sep>/Assignment 8/17CS30038_8.c
#include<stdlib.h>
#include<stdio.h>
#include<math.h>

typedef struct score
{
	int mscore;
	int escore;
} score, *scorelist;

int distance(score a, score b)
{
	//printf("\n%d--%d--%d--%d %d\n",a.mscore,a.escore,b.mscore,b.escore,(abs(a.mscore-b.mscore)+abs(a.escore-b.escore) ));
	return (abs(a.mscore-b.mscore)+abs(a.escore-b.escore) );
}

void mergeM(score a[],int lower,int middle,int upper)
{
	score b[10000],c[10000];
	int i,j,k,h1,h2;
	h1=0;
	for(i=lower;i<=middle;i++)
		b[h1++]=a[i];
	h2=0;
	for(i=middle+1;i<=upper;i++)
		c[h2++]=a[i];
	i=0;
	j=0;
	k=lower;
	while(i<h1 && j<h2)
	{
		if(b[i].mscore>c[j].mscore)
			a[k++]=c[j++];
		else
			a[k++]=b[i++];
	}
	while(i<h1) 
		a[k++]=b[i++];
	while(j<h2) 
		a[k++]=c[j++];

}

void merge_sortM(score a[],int lower,int upper)
{
	if(lower!=upper)
	{
		int middle=(lower+upper)/2;
		merge_sortM(a,lower,middle);
		merge_sortM(a,middle+1,upper);
		mergeM(a,lower,middle,upper);
	}
}

void mergeE(score a[],int lower,int middle,int upper)
{
	score b[1000],c[1000];
	int i,j,k,h1,h2;
	h1=0;
	for(i=lower;i<=middle;i++)
		b[h1++]=a[i];
	h2=0;
	for(i=middle+1;i<=upper;i++)
		c[h2++]=a[i];
	i=0;
	j=0;
	k=lower;
	while(i<h1 && j<h2)
	{
		if(b[i].escore>c[j].escore)
			a[k++]=c[j++];
		else
			a[k++]=b[i++];
	}
	while(i<h1) 
		a[k++]=b[i++];
	while(j<h2) 
		a[k++]=c[j++];

}

void merge_sortE(score a[],int lower,int upper)
{
	if(lower!=upper)
	{
		int middle=(lower+upper)/2;
		merge_sortE(a,lower,middle);
		merge_sortE(a,middle+1,upper);
		mergeE(a,lower,middle,upper);
	}
}

int explore_strip(score strip[],int size,int current_minimum, score *score1, score *score2)
{
	//printf("IN STRIP");
	//printf("Size%d:",size);		
	int new_minimum=current_minimum;
	int i,j;
	//for(i=0;i<size;i++)
	//{
	//	printf("\nstrip--%d--%d",strip[i].mscore,strip[i].escore);
	//}
	for(i=0;i<size;i++)
	{
		for(j=i+1; (j<size) && abs(strip[i].escore-strip[j].escore)<current_minimum;j++ )
		{
			if(distance(strip[j],strip[i])<new_minimum )
			{
				new_minimum=distance(strip[j],strip[i]);
				(*score1)=strip[j];
				(*score2)=strip[i];
			}
		}
	}
	//printf("Out of strip");
	return new_minimum;
}

int closest_pair(scorelist T_M,scorelist T_E, int l, int r, score *score1, score *score2)
{
	if((r-l)==1)
	{
		*score1=T_M[l];
		*score2=T_M[r];
		return distance(T_M[l],T_M[r]);
	}
	else if((r-l)==2)
	{
		int d1=distance(T_M[l],T_M[l+1]);
		int d2=distance(T_M[l+1],T_M[l+2]);
		int d3=distance(T_M[l],T_M[l+2]);
		if(d1<d2 && d1<d3) //d1 is min
		{
			*score1=T_M[l];
			*score2=T_M[l+1];
			return d1;
		}
		else if(d2<d1 && d2<d3) //d2 is min
		{
			*score1=T_M[l+1];
			*score2=T_M[l+2];
			return d2;
		}
		else //d3 is min
		{
			*score1=T_M[l];
			*score2=T_M[l+2];
			return d3;
		}
	}
	else
	{
		int mid=(l+r)/2;
		score T_E_l[10000],T_E_r[10000];
		int i,j=0,k=0;
		
		for(i=0;i<=(r-l);i++)
		{
			if(T_E[i].mscore<=T_M[mid].mscore)
				T_E_l[j++]=T_E[i];
			else
				T_E_r[k++]=T_E[i];
		}
		//printf("\nstart--->%d--%d--%d--%d<----",score1->mscore,score1->escore,score2->mscore,score2->escore);
		score score3=(*score1);
		score score4=(*score2);
		int a=closest_pair(T_M,T_E_l,l,mid,score1,score2);
		//printf("\nmid--->%d--%d--%d--%d<----",score1->mscore,score1->escore,score2->mscore,score2->escore);
		int b=closest_pair(T_M,T_E_r,mid+1,r,&score3,&score4);
		int minimum=a;
		if(minimum>=b)
		{
			minimum=b;
			(*score1)=score3;
			(*score2)=score4;
		}
		//printf("\nend--->%d--%d--%d--%d<----",score1->mscore,score1->escore,score2->mscore,score2->escore);
		score strip[10000];
		j=0;
		for(i=0;i<=(r-l);i++)
		{
			if(abs(T_E[i].mscore-T_M[mid].mscore)<minimum)
			{
				strip[j++]=T_E[i];
				//printf("\nT_E--%d--%d",T_E[i].mscore,T_E[i].escore);
			}
		}
		return explore_strip(strip,j,minimum,score1,score2);
			

	}
	
}

int NearestProfiles(scorelist T,int n,score *score1,score *score2)
{
	int i;
	scorelist T_M,T_E;
	T_M = (scorelist)malloc((n)*sizeof(score));
	T_E = (scorelist)malloc((n)*sizeof(score));
	for(i=0;i<n;i++)
	{
		T_M[i]=T[i];
		T_E[i]=T[i];
	}
	merge_sortM(T_M,0,n-1);
	merge_sortE(T_E,0,n-1);
	
	return closest_pair(T_M,T_E,0,n-1,score1,score2);
}






int closest_cluster_pair(scorelist section1_M,scorelist section1_E,int l1,int r1, scorelist section2_M, scorelist section2_E,int l2,int r2,score *score1,score *score2)
{
	if((r1-l1)==0)
	{
		int i;
		int minimum=distance(section1_M[l1],section2_M[l2]);
		*score1=section1_M[l1];
		*score2=section2_M[l2];
		for(i=l2+1;i<=r2;i++)
		{
			if(distance(section1_M[l1],section2_M[i])<minimum)
			{
				minimum=distance(section1_M[l1],section2_M[i]);
				*score2=section1_M[l1];
				*score1=section2_M[i];
			}
		}
		return minimum;
	}
	else if((r2-l2)==0)
	{
		int i;
		int minimum=distance(section2_M[l2],section1_M[l1]);
		*score1=section2_M[l2];
		*score2=section1_M[l1];
		for(i=l1+1;i<=r1;i++)
		{
			if(distance(section2_M[l2],section1_M[i])<minimum)
			{
				minimum=distance(section2_M[l2],section1_M[i]);
				*score1=section2_M[l2];
				*score2=section1_M[i];
			}
		}
		return minimum;
	}
	else
	{
		int mid1=(l1+r1)/2;
		score section1_E_l[10000],section1_E_r[10000];
		int i,j=0,k=0;
		
		for(i=0;i<=(r1-l1);i++)
		{
			if(section1_E[i].mscore<=section1_M[mid1].mscore)
				section1_E_l[j++]=section1_E[i];
			else
				section1_E_r[k++]=section1_E[i];
		}


		int mid2=(l2+r2)/2;
		score section2_E_l[10000],section2_E_r[10000];
		j=0;
		k=0;
		
		for(i=0;i<=(r2-l2);i++)
		{
			if(section2_E[i].mscore<=section2_M[mid2].mscore)
				section2_E_l[j++]=section2_E[i];
			else
				section2_E_r[k++]=section2_E[i];
		}

		score score3=(*score1);
		score score4=(*score2);
		int a=closest_cluster_pair(section1_M,section1_E_l,l1,mid1,section2_M,section2_E_l,l2,mid2,score1,score2);

		int b=closest_cluster_pair(section1_M,section1_E_r,mid1+1,r1,section2_M,section2_E_l,mid2+1,r2,&score3,&score4);
		int minimum=a;
		if(minimum>=b)
		{
			minimum=b;
			(*score1)=score3;
			(*score2)=score4;
		}
/*
		//printf("\nend--->%d--%d--%d--%d<----",score1->mscore,score1->escore,score2->mscore,score2->escore);
		score strip[10000];
		j=0;
		for(i=0;i<=(r-l);i++)
		{
			if(abs(T_E[i].mscore-T_M[mid].mscore)<minimum)
			{
				strip[j++]=T_E[i];
				//printf("\nT_E--%d--%d",T_E[i].mscore,T_E[i].escore);
			}
		}
		return explore_strip(strip,j,minimum,score1,score2);*/
		
		return minimum;
			

	}
	
}


int ClusterDist(scorelist section1,int n, scorelist section2,int m,score *score1,score *score2)
{
	int i;
	scorelist section1_M,section1_E;
	section1_M = (scorelist)malloc((n)*sizeof(score));
	section1_E = (scorelist)malloc((n)*sizeof(score));
	for(i=0;i<n;i++)
	{
		section1_M[i]=section1[i];
		section1_E[i]=section1[i];
	}
	merge_sortM(section1_M,0,n-1);
	merge_sortE(section1_E,0,n-1);


	scorelist section2_M,section2_E;
	section2_M = (scorelist)malloc((m)*sizeof(score));
	section2_E = (scorelist)malloc((m)*sizeof(score));
	for(i=0;i<n;i++)
	{
		section2_M[i]=section2[i];
		section2_E[i]=section2[i];
	}
	merge_sortM(section2_M,0,n-1);
	merge_sortE(section2_E,0,n-1);

	return closest_cluster_pair(section1_M,section1_E,0,n-1,section2_M,section2_E,0,m-1,score1,score2);

	
}


int main()
{
	score profile1,profile2;
	score T1[10000],T2[10000];
	int n,m,i;
	printf("Enter number of students:");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Enter math and english scores:");
		scanf("%d",&T1[i].mscore);
		scanf("%d",&T1[i].escore);
	}
	int minimum=NearestProfiles(T1,n,&profile1,&profile2);
	printf("\nClosest pair: (%d,%d) and (%d,%d)",profile1.mscore,profile1.escore,profile2.mscore,profile2.escore);
	printf("\nDistance: %d",minimum);
	printf("\n\n");
	printf("Enter the size of the second cluster:");
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{
		printf("Enter math and english scores:");
		scanf("%d",&T2[i].mscore);
		scanf("%d",&T2[i].escore);
	}
	minimum=ClusterDist(T1, n, T2,m,&profile1,&profile2);
	printf("\nClosest pair: (%d,%d) and (%d,%d)",profile1.mscore,profile1.escore,profile2.mscore,profile2.escore);
	printf("\nDistance: %d",minimum);
	
	return 0;
}
























<file_sep>/Assignment 3/17CS30038_3.c
#include <stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct treenode
{
	char word[100];
	struct treenode *leftchild;
	struct treenode *rightchild;
	struct treenode *parent;
} NODE, *NODEPTR;

NODEPTR insert(NODEPTR x)
{
	char input[100];
	printf("Input String:");
	scanf("%s",input);
	if (x==NULL)
	{
		x=(NODE*)malloc(sizeof(NODE));
		strcpy(x->word,input);
		x->parent = NULL; 
		x->leftchild=NULL;
		x->rightchild==NULL;
		return x;
	}
	else 
	{
		NODEPTR temp=x;
		while(temp!=NULL)
		{
			if( strcmp(temp->word,input) > 0 ) //input < temp->word
			{
				if(temp->leftchild == NULL)
				{
					temp->leftchild=(NODE*)malloc(sizeof(NODE));
					strcpy((temp->leftchild)->word,input);
					(temp->leftchild)->parent = temp; 
					(temp->leftchild)->leftchild=NULL;
					(temp->leftchild)->rightchild==NULL;
					return x;
				}
				else
					temp=temp->leftchild;
			}
			else if( strcmp(temp->word,input) < 0 ) //input > x->word
			{
				if(temp->rightchild == NULL)
				{
					temp->rightchild=(NODE*)malloc(sizeof(NODE));
					strcpy((temp->rightchild)->word,input);
					(temp->rightchild)->parent = x; 
					(temp->rightchild)->leftchild=NULL;
					(temp->rightchild)->rightchild==NULL;
					return x;
				}
				else
					temp=temp->rightchild;
			}
		}
		
	}
	
}

void inorder(NODEPTR x)
{
	if(x!=NULL)
	{
		inorder(x->leftchild);
		printf("%s ",x->word);
		inorder(x->rightchild);
	}
}
int prefix( char A[100],char B[100]) //returns 1 if B is a prefix
{
	int a,b,i;
	a=strlen(A);
	b=strlen(B);
	if(b>a)
		return 0;
	else
	{
		for(i=0;i<b;i++)
		{
			if(A[i]!=B[i])
				return 0;
		}
		return 1;
	} 
}
NODEPTR leftmost(NODEPTR root)
{
	while (root != NULL && root->leftchild != NULL)
       		 root = root->leftchild;
    	return root;
}
NODEPTR rightmost(NODEPTR root)
{
	while (root != NULL && root->rightchild != NULL)
       		 root = root->rightchild;
    	return root;
}
NODEPTR successor(NODEPTR x)
{
	if (x->rightchild != NULL)
	{
     		return leftmost(x->rightchild);
	}
	if(x->rightchild==NULL)
	{
		while(x==x->parent->rightchild)
			x=x->parent;
		return x->parent;
	}
}
void find_extensions(NODEPTR root, char pattern[100])
{
	while(root!=NULL)
	{
		if(prefix(root->word,pattern)==1)
		{
			if(root->leftchild==NULL)
			{
				printf(" %s",root->word);
				root=root->rightchild;
				
			}
			else if(root->rightchild==NULL)
				root=root->leftchild;
			else
			{
				NODEPTR temp1,temp2;
				temp1=root->leftchild;
				temp2=root->leftchild;
				while(temp1!=NULL && temp1->leftchild!=NULL)
					temp1=temp1->leftchild;
				while(temp2!=NULL && temp2->rightchild!=NULL)
					temp2=temp2->rightchild;
				while(temp1!=temp2)
				{
					if(prefix(temp1->word,pattern)==1)
						printf(" %s",temp1->word);
					temp1=successor(temp1);	
				}
				printf(" %s",temp2->word);
				printf(" %s",root->word);
				root=root->rightchild;
			}
		}
		else if ( strcmp(root->word,pattern)>0)
			root=root->leftchild;
		else
			root=root->rightchild;
	}
}

void main()
{
	int n,i;
	char input[100];
	NODEPTR root=NULL;
	printf("Enter the number of words:");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		root=insert(root);
	}
	inorder(root);
	printf("\n\n");
	find_extensions(root,"pag");
}



























	
<file_sep>/Lab Test/even/9_17CS30038.c
//<NAME>	
//17CS30038
//PC No-9
/*
subproblem: max probabilty with P persons in completing the project will be max of prob by p persons(n<=p<P) and multiplying by probability ratios of changing number of persons in any one of the component
let dp(n,p) be person on each component with total persons=p;
let maxp(p) store max prob by p persons
dp(n,p)=0 	...for all nXp where (p<N)
maxp(p)=0	...for all nXp where (p<N)
dp(n,p)=1	...when p=N as only one possible way of distributing min 1 perswon to a component
maxp(p)=prod(p[i][1])	...when p=N 
maxp(p)=max(max(maxp(p_i)*(p[i][dp(p_i)+p-p_i])/(p[i][p_i])    for(i=1 to n))for(N<=p_i<p))
let p_i_max and i_max be corresponding obtained values
dp(n,p)=dp(n,p_i_max) for(n !=i )
dp(n,p)=dp(n,p_i_max)+p_i-p_i_max for(n==i)		  

*/
#include<stdio.h>
#include<stdlib.h>
int main()
{
	int N,P;
	scanf("%d%d",&N,&P);
	double **p;	
	p=(double**)malloc((N+1)*sizeof(double*));
	for(int i=0;i<=N;i++)
	{
		p[i]=(double*)malloc((P+1)*sizeof(double));
	}
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<=P;j++)
		{
			if(i==0||j==0)
				p[i][j]=0;
			else
				scanf("%lf",&p[i][j]);
		}
	}
	int **dp;
	dp=(int**)malloc((N+1)*sizeof(int*));
	for(int i=0;i<=N;i++)
	{
		dp[i]=(int*)malloc((P+1)*sizeof(int));
	}

	double *maxp;
	maxp=(double*)malloc((P+1)*sizeof(double));
	for(int i=0;i<P;i++)
		maxp[i]=1.0;

	for(int i=1;i<=N;i++)
	{
		dp[i][N]=1;
		maxp[N]=p[i][1]*maxp[N];
	}
	double max,tmp;
	int indi,indk;	
	for(int j=N+1;j<=P;j++)
	{
		max=0;
		for(int k=N;k<j;k++)
		{
			for(int i=1;i<=N;i++)
			{
				tmp=maxp[k]*(p[i][dp[i][k]+j-k])/(p[i][dp[i][k]]);
				if(tmp>max)
				{
					max=tmp;
					indi=i;
					indk=k;
				}
			}
		}
		maxp[j]=max;
		for(int i=1;i<=N;i++)
		{
			dp[i][j]=dp[i][indk];
		}	
		dp[indi][j]+=j-indk;
		
		
	}
	printf("max success probability is:%lf\n",maxp[P]);
	printf("assignment of people for max success probability:\n");
	for(int i=1;i<=N;i++)
	{
		printf("counter %d::%d\n",i,dp[i][P]);
	}
	return 0;	
		
	
}
<file_sep>/Lab Test/odd/odd.c
//NAME: <NAME>
//ROLL NO: 17CS10061
//PC NO: 71

/*
	Definition of subproblem used:
I have defined DP[i][j] as the max success probability that a project has with i essential components and j number of people.
For storing the components I have used a 2D array 'comp'. comp[i][j] stores the number of people assigned to the ith essential component such that we can get the max success probability with i essential components and j number of people.

base cases:

	DP[k][0]=0 for 1<=k<=N because its given p[k][0]=0
	DP[1][j]=p[1][j] for 1<=j<=P as if there is only one essential component, all the j people available must be assigned to it (as p(k,j) values are non decreasing for increasing values of j)

	comp[1][j]=j for 1<=j<=P as for only 1 task all people available must be set to that task

Recursive formulation:
	
	for 2<=x<N, x<=y<=P : 
		if(x==y) : DP[x][y]=D[x-1][y-1]*a[x][1] (as all essential components must have one person each)
			   comp[x][y]=1 as xth essential task will be assigned 1 person
		else     : DP[x][z]=max(DP[x-1][y-z]*a[x][z]) where 1<=z<=(y-1) ( 1 as each essential component must have atleast 1 person)
			   comp[x][y]=tempz where tempz=value of z for which maximum is found above (as this means xth essential component must have tempz people)
	
Answer: maximum success probability: DP[N][P]
	components: components printed using 2D array comp.
*/

#include<stdio.h>
#include<stdlib.h>

int main()
{
	int N,P,j,k,x,y,z,i,tempz,res;
	float q,max;
	float a[100][100];
	float DP[100][100];
	int output[100];
	int comp[100][100];
	printf("\nEnter N:");
	scanf(" %d",&N);
	printf("\nEnter P:");
	scanf(" %d",&P);
	printf("\nEnter the probabilities:\n");
	for(k=1;k<=N;k++)
		for(j=1;j<=P;j++)
			scanf(" %f",&a[k][j]);
	//DP array initialized to 0
	for(x=0;x<=N;x++)
		for(y=0;y<=P;y++)
			DP[x][y]=0;
	for(k=1;k<=N;k++)
		DP[k][0]=0;
	for(j=1;j<=P;j++)
		DP[1][j]=a[1][j];
	
	for(x=2;x<=N;x++)
		for(y=1;y<=P;y++)	
		{
			comp[i][j]=0;
		}
	for(j=1;j<=P;j++)
	{
		comp[1][j]=j;
	}
	for(x=2;x<=N;x++)
		for(y=x;y<=P;y++)
		{
			if(x==y)
			{	
				DP[x][y]=DP[x-1][y-1]*a[x][1];
				comp[x][y]=1;
			}
			else
			{
				
				max=0;
				for(z=1;z<=(y-1);z++)
				{
					q=DP[x-1][y-z]*a[x][z];
					if(q>max)
					{
						tempz=z;
						max=q;
					}
				}
				DP[x][y]=max;
				comp[x][y]=tempz;
			}
		}
	printf("\nThe maximum success probability is: %f\n",DP[N][P]);
	printf("Assignment of people for max success probability:\n");
	res=P;
	for(x=N;x>0;x--)
	{
		output[x]=comp[x][res];
		res=res-output[x];
	}
	for(i=1;i<=N;i++)
		printf("Component %d: %d\n",i,output[i]);
	
	return 0;
}
<file_sep>/Assignment 2/17CS30038_2.c
#include<stdio.h>
#include<stdlib.h>
typedef struct rm {
	int hInd;
	int vInd;
} room;
struct node 
{
	room data;
	struct node *next;
};
typedef struct node node, *list;
typedef struct {
	struct node *head ;
} STACK ;
void init(STACK *s)
{
	s->head=NULL;
}
int isempty(STACK s)
{
	if(s.head==NULL)
		return 1;
	else
		return 0;
}
void push(STACK *s, room data)
{
	struct node *temp;
	temp=(struct node*)malloc(sizeof(struct node));
	temp->data.hInd=data.hInd;
	temp->data.vInd=data.vInd;
	temp->next=s->head;
	s->head=temp;
}
void pop(STACK *s);

void printmaze(int H[][20], int V[][21], int n)
{
	int i,j;
	for(i=0;i<4*n+1;i++)
		for(j=0;j<4*n+1;j++)
		{
			if(i%4==0&&j%4==0)
			{
				printf("+");
			}
			if(i%4==0&&j%4!=0)
			{
				if(H[i/4][j/4]==0)
					printf("-");
				else
					printf(" ");
			}
			if(i%4!=0&&j%4==0)
			{
				if(i%4==1||i%4==3)
					printf(" ");
				else
				{	
					if(V[i/4][j/4]==0)
						printf("|");
					else
						printf(" ");
				}
	
			}
			if(i%4!=0&&j%4!=0)
			{ 
				printf(" ");
			}
			if(j==4*n)
				printf("\n");

			
		}
	
}
void createmaze(list maze[][20], int n, int H[][20], int V[][21])
{
	int i,j;
	struct node* temp;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			maze[i][j]=NULL;
			if(H[i][j]==1)
			{
				struct node* t;
				t=(struct node*)malloc(sizeof(struct node));
				t->data.hInd=i-1;
				t->data.vInd=j;
				if(maze[i][j]==NULL)
				{	maze[i][j]=t;temp=t;}
						
				else
				{	
					temp->next=t;
					temp=t;
				}	
			}
			if(H[i+1][j]==1)
			{
				struct node* t;
				t=(struct node*)malloc(sizeof(struct node));
				t->data.hInd=i+1;
				t->data.vInd=j;
				if(maze[i][j]==NULL)
				{	maze[i][j]=t;temp=t;}
				else
				{	
					temp->next=t;
					temp=t;
				}
			}
			if(V[i][j]==1)
			{
				struct node* t;
				t=(struct node*)malloc(sizeof(struct node));
				t->data.hInd=i;
				t->data.vInd=j-1;
				if(maze[i][j]==NULL)
				{	maze[i][j]=t;temp=t;}
				else
				{	
					temp->next=t;
					temp=t;
				}
			}

			if(V[i][j+1]==1)
			{
				struct node* t;
				t=(struct node*)malloc(sizeof(struct node));
				t->data.hInd=i;
				t->data.vInd=j+1;
				if(maze[i][j]==NULL)
				{	maze[i][j]=t;temp=t;}
				else
				{	
					temp->next=t;
					temp=t;
				}
			}
			temp->next=NULL;			
		}
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			printf("(%d,%d)",i,j);
			temp=maze[i][j];
			if(temp!=NULL)
			{printf("::-->");printf("(%d,%d)",temp->data.hInd,temp->data.vInd);}
			while(temp->next!=NULL)
			{
				temp=temp->next;
				printf("-->");	
				printf("(%d,%d)",temp->data.hInd,temp->data.vInd);	
				
			}	printf("\n");
		}
	return;	
}
int main()
{
<file_sep>/Assignment 13/17CS10061_13.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef int** graph;
typedef struct queue
{
	int n;
	struct queue* next;
}que;
typedef struct Edge 
{ 
    int src, dest,weight; 
}edge;
void merge(edge a[],int low ,int mid,int high)
{
    int i=low,j=mid+1;
    int k=0;
    edge b[high-low+1];
    while(i<=mid&&j<=high)
    {
        if(a[i].weight<a[j].weight)
        {
            b[k]=a[j];
            j++;
            k++;
        }
        else
        {
            b[k]=a[i];
            i++;
            k++;
        }
    }
    while(i<=mid)
    {
        b[k]=a[i];
        i++;
        k++;
    }
    while(j<=high)
    {
        b[k]=a[j];
        j++;
        k++;
    }
    for(i=low,k=0;i<=high;i++,k++)
    {
        a[i]=b[k];
    }
    return ;
}
void mergesort(edge a[],int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        mergesort(a,low,mid);
        mergesort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}
que* enqueue(que *front,int n)
{
	que* move=(que*)malloc(sizeof(que)),*temp;
	move->n=n;
	move->next=NULL;
	if(front==NULL)
	{
		front =move;
		return front ;
	}
	else
	{
		temp=front;
		while(temp->next!=NULL)
			temp=temp->next;
		temp->next=move;
		return front;	
	}		
}
int first(que* front)
{
	if(front!=NULL)
		return front->n;
}	
que* dequeue(que* front)
{
	if(front!=NULL)	
		return front->next;	
}
int isempty(que* front)
{
	if(front==NULL)
		return 0;
	return 1;
}
int isConnectedUsingBFS(graph G,int n)
{
	int *v=(int*)malloc(n*sizeof(int));
	for(int i=0;i<n;i++)
		v[i]=0;
	v[0]=1;
	que* Q=NULL;
	Q=enqueue(Q,0);
	while(isempty(Q))
	{
		int u=first(Q);
		Q=dequeue(Q);
		for(int j=0;j<n;j++)
		{
			if(G[u][j]>0 && v[j]==0)
			{
				Q=enqueue(Q,j);	
				v[j]=1;
			}	
		}
	}
	for(int i=0;i<n;i++)
		if(v[i]==0)		
		{	free(v);
			return 0;
		}
	free(v);
	return 1;


}
	
void findMST(graph G, int numberOfNodes)
{
	int v=numberOfNodes,e=0;
	edge ed[10000];
	for(int i=0;i<v;i++)
	{
		for(int j=i;j<v;j++)
		{
			if(G[i][j]>0)
			{
				
				ed[e].src=i;
				ed[e].dest=j;
				ed[e].weight=G[i][j];
				e++;
				
			}	
		}
	}
	mergesort(ed,0,e-1);
	for(int i=0;i<e;i++)
	{
		int t=G[ed[i].src][ed[i].dest];
		G[ed[i].src][ed[i].dest]=0;
		G[ed[i].dest][ed[i].src]=0;
		if( isConnectedUsingBFS( G,v))
			continue;
		else
		{
			G[ed[i].src][ed[i].dest]=t;
			G[ed[i].dest][ed[i].src]=t;
		}
			
	}
	for(int i=0;i<v;i++)
	{	
		printf("vertex %d : ",i);
		for(int j=0;j<v ;j++)
			if(G[i][j]>0)
				printf("%d %d ",j,G[i][j]);
		printf("\n");
			
	}
			
}
int main()
{
	int n,m,a,b,deg;
	printf("Enter the number of nodes and edges\n");
	scanf("%d%d",&n,&m);
	graph A=(int**)malloc(n*sizeof(int*));
	for(int i=0;i<n;i++)
	{
		A[i]=(int*)malloc(n*sizeof(int));
	}
	printf("Enter the neighbors for each of the vertex\n");
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			A[i][j]=0;
		printf("enter the degree of vertex %d :\n",i);
		scanf("%d",&deg);		
		printf("enter neighbours\n");
		for(int j=0;j<deg;j++)
		{
			
			scanf("%d%d",&a,&b);
			A[i][a]=b;
		}
	}
	for(int i=0;i<n;i++)
	{	
		printf("vertex %d : ",i);
		for(int j=0;j<n ;j++)
			if(A[i][j]>0)
				printf("%d %d ",j,A[i][j]);
		printf("\n");
			
	}	
	printf("neughbours of required mst\n");	
	findMST( A, n)	;
	for(int i=0;i<n;i++)
		free(A[i]);
	return 0;
}	
<file_sep>/Assignment 11/17CS30038_11.c
#include<stdio.h>
#include<stdlib.h>

typedef struct
{
	int subpartID;
	int cost_per_day;
	int duration;
} subpart_data;

typedef struct{
	int predecessorID;
	int successorID;
} dependency_info;

void merge(subpart_data a[],int lower,int middle,int upper)
{
	subpart_data b[100],c[100];
	int i,j,k,h1,h2;
	h1=0;
	for(i=lower;i<=middle;i++)
		b[h1++]=a[i];
	h2=0;
	for(i=middle+1;i<=upper;i++)
		c[h2++]=a[i];
	i=0;
	j=0;
	k=lower;
	while(i<h1 && j<h2)
	{
		if(b[i].cost_per_day*c[j].duration>c[j].cost_per_day*b[i].duration)
			a[k++]=b[i++];
		else
			a[k++]=c[j++];
	}
	while(i<h1) 
		a[k++]=b[i++];
	while(j<h2) 
		a[k++]=c[j++];

}

void merge_sort(subpart_data a[],int lower,int upper)
{
	if(lower!=upper)
	{
		int middle=(lower+upper)/2;
		merge_sort(a,lower,middle);
		merge_sort(a,middle+1,upper);
		merge(a,lower,middle,upper);
	}
}	

void print_schedule(subpart_data *A, int K)
{
	merge_sort(A,0,K-1);//sort in descending based on cost/duration
	int no_of_days=0;	
	int i,cost=0;
	for(i=0;i<K;i++)
	{
		printf("%d ",A[i].subpartID);
		no_of_days=no_of_days+A[i].duration;
		cost=cost+no_of_days*A[i].cost_per_day;
	}
	printf("\nCost:%d",cost);	
}

void print_schedule1(subpart_data *A,int K,dependency_info *B,int l)
{
	int i,j,m,col,flag;
	int number_of_chains;
	int chain[100][100];
	int dependent[100];
	int high[100];
	for(i=0;i<K;i++)
		dependent[i]=0;
	for(i=0;i<l;i++)
		dependent[B[i].successorID-1]=1;
	printf("\n");
	for(i=0;i<K;i++)
		printf("%d ",dependent[i]);
	for(i=0;i<K;i++)
	{
		high[i]=0;
		for(j=0;j<K;j++)
			chain[i][j]=0;
	}
	j=0;
	for(i=0;i<K;i++)
	{
		if(dependent[i]==0)
		{
			chain[j][0]=i+1;
			col=0;
			while(1)
			{
				flag=0;
				for(m=0;m<l;m++)
					if(B[m].predecessorID==chain[j][col])
					{
						chain[j][++col]=B[m].successorID;
						flag=1;
						break;
					}
				if(flag==0)
					break;
			}
			high[j]=col+1;
			j++;
		}
	}
	number_of_chains=j;
	for(i=0;i<K;i++)
	{
		printf("\n %d -  ",high[i]);
		for(j=0;j<K;j++)
			printf("%d ",chain[i][j]);
	}
	printf("\n");
	
	//merge number_of_chains chains

	float max_value=0;
	int max_index;
	int r,c;
	
	int output[100];
	int output_index=0;
	
	int low[100];
	int duration_sum,cost_sum;

	int active_chain[100];
	for(i=0;i<number_of_chains;i++)
		active_chain[i]=1;
	for(i=0;i<number_of_chains;i++)
		low[i]=0;
	for(i=0;i<number_of_chains;i++)
		high[i]--;
	while(1)
	{
		max_value=0;
		for(i=0;i<number_of_chains;i++)
		{
			if(active_chain[i]==1)
			{
				duration_sum=0;
				cost_sum=0;
				for(j=low[i];j<=high[i];j++)
				{
					duration_sum=duration_sum+A[chain[i][j]-1].duration;
					cost_sum=cost_sum+A[chain[i][j]-1].cost_per_day;
					if(max_value< ((float)cost_sum)/((float)duration_sum) )
					{
						max_value=((float)cost_sum)/((float)duration_sum);
						r=i;
						c=j;
					}
				}
			}
		}
		for(m=low[r];m<=c;m++)
			output[output_index++]=chain[r][m];
		low[r]=c+1;
		printf(" %d",output_index);
		if(output_index==K)
			break;
	}
	printf("\n Scheduled Index: ");
	for(i=0;i<K;i++)
		printf("%d ",output[i]);

	int cost=0;
	int no_of_days=0;
	for(i=0;i<K;i++)
	{
		no_of_days=no_of_days+A[output[i]-1].duration;
		cost=cost+no_of_days*A[output[i]-1].cost_per_day;
	}
	
	printf("\nCost:%d",cost);
}

int main()
{
	subpart_data* A;
	dependency_info* B;
	int K,i,l;
	printf("Input number of subparts (K) :");
	scanf("%d",&K);
	A = (subpart_data*)malloc((K)*sizeof(subpart_data));
	for(i=0;i<K;i++)	
	{
		A[i].subpartID=i+1;
		scanf("%d",&A[i].duration);
	}
	for(i=0;i<K;i++)
		scanf("%d",&A[i].cost_per_day);
	print_schedule(A,K);
	
	printf("\nInput number of dependencies (l) :");
	scanf("%d",&l);
	
	B = (dependency_info*)malloc((l)*sizeof(dependency_info));
	for(i=0;i<l;i++)
	{
		scanf("%d",&B[i].predecessorID);
		scanf("%d",&B[i].successorID);
	}
	print_schedule1(A,K,B,l);
	
	
	return 0;	
}





























<file_sep>/README.md
# Algorithms-1-Lab
IIT KGP CS29003
2018 Autumn Semester
<file_sep>/Lab Test/even/9_17CS30038(1).c
//<NAME>
//17CS30038
//PC no=9
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max(a,b)(a>b?a:b)
int main()
{
	char input1[100],input2[100],output[100];
	int DP[100][100];
	int i,j;
	int m,n;
	printf("enter m:");
	scanf("%d",&m);
	printf("enter n:");
	scanf("%d",&n);
	printf("enter A:");
	scanf(" %s",input1);
	printf("enter B:");
	scanf(" %s",input2);
	for(i=0;i<=strlen(input1);i++)
		for(j=0;j<=strlen(input2);j++)
		{
			if(i==0 || j==0)
				DP[i][j]=0;
			else if(input1[i-1]==input2[j-1])
				DP[i][j]=DP[i-1][j-1]+1;
			else
				DP[i][j]=max(DP[i][j-1],DP[i-1][j]);
		}
	int temp=DP[strlen(input1)][strlen(input2)];
	printf("\nLength of LCS is %d",DP[strlen(input1)][strlen(input2)]);
	
	return 0;
}


<file_sep>/Assignment 5/17CS30038_5.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

typedef struct _wordR 
{ 
	char word[100]; 
	double x, y; 
} wordR; 

typedef struct _node
{ 
	wordR w; 
	struct _node *next; 
}node, *nodePointer; 

typedef nodePointer **hashTable; 

void insertH(hashTable H, int m, wordR a)
{
	int X=floor(m*(a.x));
	int Y=floor(m*(a.y));
	nodePointer temp=NULL;
	if(H[X][Y]==NULL)
	{
		H[X][Y]=(nodePointer)malloc(sizeof(node));
		H[X][Y]->w=a;
		H[X][Y]->next=NULL;
	}
	else
	{
		temp=H[X][Y];
		while(temp->next!=NULL)
		{
			temp=temp->next;
		}
		temp->next=(nodePointer)malloc(sizeof(node));
		temp->next->w=a;
		temp->next->next=NULL;
	}
}

void printH(hashTable H, int m,FILE* fp)
{
	int i,j;
	nodePointer temp=NULL;
	printf("%d",m);
	for(i=0;i<m;i++)
	{
		for(j=0;j<m;j++)
		{
			fprintf(fp,"\n[%d,%d]::(",i,j);
			temp=H[i][j];
			while(temp!=NULL)
			{
				fprintf(fp," %s ",temp->w.word);
				temp=temp->next;
			}
			
		}
	}
}

void findNN (hashTable H, int m, wordR a)
{
	int X=floor(m*(a.x));
	int Y=floor(m*(a.y));
	wordR output;
	nodePointer temp=NULL;
	int flag=0;
	double min=1000;
	double dis=0;
	int s,t,i,j;
	i=X;
	j=Y;
	printf("--%d--%d--",i,j);
	if(H[X][Y]!=NULL)
	{
		temp=H[X][Y];
		while(temp!=NULL)
		{
			if(strcmp( (temp->w.word),a.word ) !=0)
			{
				dis=sqrt( ((temp->w.x)-a.x)*((temp->w.x)-a.x) + ((temp->w.x)-a.x)*((temp->w.x)-a.x) );
				if(dis<min)
				{
					min=dis;
					output=temp->w;
				}
				flag=1; 
			}
			temp=temp->next;
		}
		if(flag==1)
		{
			printf("%s%lf%lf",output.word,output.x,output.y);
		}
	}
	if(flag==0)
	{
		int k=1;
		while(1)
		{
			for(s=i-k,t=j-k;t<=j+k;t++)
			{
				temp=H[s][t];
				while(temp!=NULL)
				{
					dis=sqrt( ((temp->w.x)-a.x)*((temp->w.x)-a.x) + ((temp->w.x)-a.x)*((temp->w.x)-a.x) );
					if(dis<min)
					{
						min=dis;
						output=temp->w;
					}
					flag=1; 
					temp=temp->next;
				}
			}
			for(s=i+k,t=j-k;t<=j+k;t++)
			{
				temp=H[s][t];
				while(temp!=NULL)
				{
					dis=sqrt( ((temp->w.x)-a.x)*((temp->w.x)-a.x) + ((temp->w.x)-a.x)*((temp->w.x)-a.x) );
					if(dis<min)
					{
						min=dis;
						output=temp->w;
					}
					flag=1; 
					temp=temp->next;
				}
			}
			for(t=j-k,s=i-k+1;s<i+k;s++)
			{
				temp=H[s][t];
				while(temp!=NULL)
				{
					dis=sqrt( ((temp->w.x)-a.x)*((temp->w.x)-a.x) + ((temp->w.x)-a.x)*((temp->w.x)-a.x) );
					if(dis<min)
					{
						min=dis;
						output=temp->w;
					}
					flag=1; 
					temp=temp->next;
				}
			}
			for(t=j+k,s=i-k+1;s<i+k;s++)
			{
				temp=H[s][t];
				while(temp!=NULL)
				{
					dis=sqrt( ((temp->w.x)-a.x)*((temp->w.x)-a.x) + ((temp->w.x)-a.x)*((temp->w.x)-a.x) );
					if(dis<min)
					{
						min=dis;
						output=temp->w;
					}
					flag=1; 
					temp=temp->next;
				}
			}
			if(flag==1)
			{
				printf("%s%lf%lf",output.word,output.x,output.y);
				break;	
			}	
		}
	}
	



}


int main()
{
	FILE *inpf, *outf; 
	int n, i,j, m,k;    
	wordR w,a;
	hashTable H;

	inpf = fopen("input.txt","r");
	if (inpf==NULL)
	{
		printf("Error opening input file input.txt\n");
		return (-1);
	}	
	
	outf = fopen("output.txt","w");
	if (outf==NULL)
	{
		printf("Error creating output file output.txt\n");
		return (-1);
	}

	fscanf(inpf,"%d",&n);
	m=ceil(sqrt(n));

	printf("%d--%d",n,m);
	//creating dynamic array
	H= (nodePointer **)malloc(m*sizeof(nodePointer*));
	for(i=0;i<m;i++)
	{
		H[i]=(nodePointer*)malloc(m*sizeof(nodePointer));
		for(j=0;j<m;j++)
			H[i][j]=NULL;
	}

	
	
	for(i=0;i<n;i++)
	{
		fscanf(inpf,"%s%lf%lf",w.word,&w.x,&w.y);
		insertH(H,m,w);
			
	}
	printH(H,m,outf);
	
	printf("Input number of words to search for:");	
	scanf("%d",&k);
	
	for(i=0;i<k;i++)
	{
		printf("Input Word");
		scanf("%s%lf%lf",a.word,&a.x,&a.y);
		findNN(H,m,a);
	}
	fclose(inpf); 
	fclose(outf); 



}

