# Monthly Archives: October 2015

## Write an Algorithm and a Program that accepts a Binary Tree as input and checks whether it is a Height Balanced Tree – IGNOU BCA Assignment 2015 – 16

BACHELOR OF COMPUTER APPLICATIONS

Course Code : BCSL-033
Course Title : Data and File Structures Lab
Assignment Number : BCA(III)/L-033/Assignment/2015
Maximum Marks : 50
Weightage : 25%

## Write an Algorithm and a Program that accepts a Binary Tree as input and checks whether it is a Height Balanced Tree.

#include <stdio.h>
#include <stdlib.h>
struct tnode
{
int data;
struct tnode *lchild, *rchild;
};

/* returns maximum of two integers */
int maxi(int a,int b)
{
int c;
c = (a >= b)? a :b;
return c;
}

int isBalanced(struct tnode *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */

/* If tree is empty then return true */
if(root == NULL)
return 1;

/* Get the height of left and right sub trees */
lh = height(root->lchild);
rh = height(root->rchild);

if( abs(lh-rh) <= 1 &&
isBalanced(root->lchild) &&
isBalanced(root->rchild))
return 1;

/* If we reach here then tree is not height-balanced */
return 0;
}

/* The function Compute the “height” of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct tnode* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + maxi(height(node->lchild), height(node->rchild));
}

struct tnode *insert(struct tnode *p,int val)
{
struct tnode *temp1,*temp2;
if(p == NULL)
{
p = (struct tnode *) malloc(sizeof(struct tnode));
/* insert the new node as root node*/
if(p == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
p->data = val;
p->lchild=p->rchild=NULL;
}
else
{
temp1 = p;
/* traverse the tree to get a pointer to that node
whose child will be the newly created node*/
while(temp1 != NULL)
{
temp2 = temp1;
if( temp1 ->data > val)
temp1 = temp1->lchild;
else
temp1 = temp1->rchild;
}
if( temp2->data > val)
{
temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->lchild;
if(temp2 == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
else
{
temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->rchild;
if(temp2 == NULL)
{
printf(“Cannot allocate\n”);
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
}
return(p);
}
/* a function to binary tree in preorder */
void preorder(struct tnode *p)
{
if(p != NULL)
{
printf(“%d\t”,p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p)
{
if(p != NULL)
{
inorder(p->lchild);
printf(“%d\t”,p->data);
inorder(p->rchild);
}
}
/* a function to binary tree in postorder */
void postorder(struct tnode *p)
{
if(p != NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf(“%d\t”,p->data);
}
}
void main()
{
struct tnode *root = NULL;
int n,x;
clrscr();
printf(“\nEnter the number of nodes\n”);
scanf(“%d”,&n);
while(n!=0)
{
printf(“Enter the data value\n”);
scanf(“%d”,&x);
root = insert(root,x);
n–;
}
if(isBalanced(root))
printf(“\n***THIS TREE IS A BALANCED TREE***\n”);
else
printf(“\n**THIS TREE IS NOT A BALANCED TREE**\n”);

printf(“\n\nPREORDER OF TREE : \n”);
preorder(root);
printf(“\n\nINORDER OF TREE : \n”);
inorder(root);
printf(“\n\nPOSTORDER OF TREE : \n”);
postorder(root);
getch();
}

CODE:

 Source code
```#include <stdio.h>
#include <stdlib.h>
struct tnode
{
int data;
struct tnode *lchild, *rchild;
};

/* returns maximum of two integers */
int maxi(int a,int b)
{
int c;
c = (a >= b)? a :b;
return c;
}

int isBalanced(struct tnode *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */

/* If tree is empty then return true */
if(root == NULL)
return 1;

/* Get the height of left and right sub trees */
lh = height(root->lchild);
rh = height(root->rchild);

if( abs(lh-rh) <= 1 &&
isBalanced(root->lchild) &&
isBalanced(root->rchild))
return 1;

/* If we reach here then tree is not height-balanced */
return 0;
}

/* The function Compute the "height" of a tree. Height is the
number of nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct tnode* node)
{
/* base case tree is empty */
if(node == NULL)
return 0;

/* If tree is not empty then height = 1 + max of left
height and right heights */
return 1 + maxi(height(node->lchild), height(node->rchild));
}

struct tnode *insert(struct tnode *p,int val)
{
struct tnode *temp1,*temp2;
if(p == NULL)
{
p = (struct tnode *) malloc(sizeof(struct tnode));
/* insert the new node as root node*/
if(p == NULL)
{
printf("Cannot allocate\n");
exit(0);
}
p->data = val;
p->lchild=p->rchild=NULL;
}
else
{
temp1 = p;
/* traverse the tree to get a pointer to that node
whose child will be the newly created node*/
while(temp1 != NULL)
{
temp2 = temp1;
if( temp1 ->data > val)
temp1 = temp1->lchild;
else
temp1 = temp1->rchild;
}
if( temp2->data > val)
{
temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->lchild;
if(temp2 == NULL)
{
printf("Cannot allocate\n");
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
else
{
temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->rchild;
if(temp2 == NULL)
{
printf("Cannot allocate\n");
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
}
return(p);
}
/* a function to binary tree in preorder */
void preorder(struct tnode *p)
{
if(p != NULL)
{
printf("%d\t",p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p)
{
if(p != NULL)
{
inorder(p->lchild);
printf("%d\t",p->data);
inorder(p->rchild);
}
}
/* a function to binary tree in postorder */
void postorder(struct tnode *p)
{
if(p != NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf("%d\t",p->data);
}
}
void main()
{
struct tnode *root = NULL;
int n,x;
clrscr();
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
while(n!=0)
{
printf("Enter the data value\n");
scanf("%d",&x);
root = insert(root,x);
n--;
}
if(isBalanced(root))
printf("\n***THIS TREE IS A BALANCED TREE***\n");
else
printf("\n**THIS TREE IS NOT A BALANCED TREE**\n");

printf("\n\nPREORDER OF TREE : \n");
preorder(root);
printf("\n\nINORDER OF TREE : \n");
inorder(root);
printf("\n\nPOSTORDER OF TREE : \n");
postorder(root);
getch();
}```

SCREENSHOTS:

## Write a program to do linear search for an integer in 20 distinct numbers. The program should return the location of an element – IGNOU BCA Assignment 2015 – 16

BACHELOR OF COMPUTER APPLICATIONS

Course Code : BCSL-045
Course Title : Introduction to Algorithm Design Lab
Assignment Number : BCA(IV)/L-045/Assignment/2015
Maximum Marks : 50
Weightage : 25%

## Write a program to do linear search for an integer number in an array of 20 distinct numbers. The program should return the location of an element if the number found in the array.

#include<stdio.h>
void main()
{
int I,Pos,KEY,TEMP,N=20,flag=0;
int List[]={14,6,10,3,12,19,4,20,8,11,2,18,15,5,13,9,17,1,16,7};
clrscr();
printf(“\n\nList to be searched :\n\n”);
for(I=0;I<N;I++)
{
printf(“%d “,List[I]);
}
printf(“\n\nEnter Element to SEARCH : “);
scanf(“%d”,&KEY);
for(I=0;I<N;I++)
{
if(List[I]==KEY)
{
flag=1;
Pos=I;
}
}
if(flag==1)
printf(“\n\nElement %d is found at Location Number %d.”,KEY,Pos+1);
else
getch();
}

Code:

 Source code
```#include<stdio.h>
void main()
{
int I,Pos,KEY,TEMP,N=20,flag=0;
int List[]={14,6,10,3,12,19,4,20,8,11,2,18,15,5,13,9,17,1,16,7};
clrscr();
printf("\n\nList to be searched :\n\n");
for(I=0;I<N;I++)
{
printf("%d ",List[I]);
}
printf("\n\nEnter Element to SEARCH : ");
scanf("%d",&KEY);
for(I=0;I<N;I++)
{
if(List[I]==KEY)
{
flag=1;
Pos=I;
}
}
if(flag==1)
printf("\n\nElement %d is found at Location Number %d.",KEY,Pos+1);
else
getch();
}```

ScreenShots:

## Write a program to sort data using a selection sort algorithm – IGNOU BCA Assignment 2015 – 16

BACHELOR OF COMPUTER APPLICATIONS

Course Code : BCSL-045
Course Title : Introduction to Algorithm Design Lab
Assignment Number : BCA(IV)/L-045/Assignment/2015
Maximum Marks : 50
Weightage : 25%

## Write a program to sort data using a selection sort algorithm.

#include<stdio.h>
void main()
{
int MIN,MIN_POS,I,J,TEMP,List[]={6,3,0,4,8,2,5,9,1,7};
int N=10;
clrscr();
printf(“\n****SELECTION SORT****\n”);
printf(“\n\nList Before Sorting :\n\n”);
for(J=0;J<N;J++)
{
printf(“%d “,List[J]);
}
for(I=0;I<N;I++)
{
MIN=List[I];
MIN_POS=I;
for(J=I;J<N;J++)
{
if(List[MIN_POS]>List[J])
{
MIN_POS=J;
MIN=List[J];
}
}
List[MIN_POS]=List[I];
List[I]=MIN;
}
printf(“\n\nList Before Sorting :\n\n”);
for(J=0;J<N;J++)
{
printf(“%d “,List[J]);
}
getch();
}

Code:

#include<stdio.h>
void main()
{
int MIN,MIN_POS,I,J,TEMP,List[]={6,3,0,4,8,2,5,9,1,7};
int N=10;
clrscr();
printf(“\n****SELECTION SORT****\n”);
printf(“\n\nList Before Sorting :\n\n”);
for(J=0;J<N;J++)
{
printf(“%d “,List[J]);
}
for(I=0;I<N;I++)
{
MIN=List[I];
MIN_POS=I;
for(J=I;J<N;J++)
{
if(List[MIN_POS]>List[J])
{
MIN_POS=J;
MIN=List[J];
}
}
List[MIN_POS]=List[I];
List[I]=MIN;
}
printf(“\n\nList Before Sorting :\n\n”);
for(J=0;J<N;J++)
{
printf(“%d “,List[J]);
}
getch();
}

ScreenShots:

## Implement merge sort algorithm – IGNOU BCA Assignment 2015 – 16

BACHELOR OF COMPUTER APPLICATIONS

Course Code : BCSL-045
Course Title : Introduction to Algorithm Design Lab
Assignment Number : BCA(IV)/L-045/Assignment/2015
Maximum Marks : 50
Weightage : 25%

## Implement merge sort algorithm.

#include<stdio.h>
int numbers[10]={2,8,4,1,0,7,9,3,5,6};
int temp[10],array_size=10;

void mergeSort(int numbers[],int temp[],int array_size);
void m_sort(int numbers[],int temp[],int left,int right);
void merge(int numbers[],int temp[],int left,int mid,int right);

void main()
{
int i;
clrscr();
printf(“\nUnsorted List : “);
for(i=0;i<10;i++)
printf(” %d”,numbers[i]);
printf(“\n\n Starting Sorting…\n”);
mergeSort(numbers,temp,array_size);
printf(“\n Sorted List : “);
for(i=0;i<10;i++)
printf(” %d”,numbers[i]);
getch();
}

void mergeSort(int numbers[],int temp[],int array_size)
{
m_sort(numbers,temp,0,array_size-1);
}

void m_sort(int numbers[],int temp[],int left,int right)
{
int mid;
if(right > left)
{
mid = (right+left)/2;
m_sort(numbers,temp,left,mid);
m_sort(numbers,temp,mid+1,right);

merge(numbers,temp,left,mid+1,right);
}
}

void merge(int numbers[],int temp[],int left,int mid,int right)
{
int i,left_end,num_elements,tmp_pos;
left_end = mid-1;
tmp_pos = left;
num_elements = right-left+1;
while((left <= left_end) && (mid <= right))
{
if(numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos+1;
left = left+1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos+1;
mid = mid+1;
}
}

while(left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left+1;
tmp_pos = tmp_pos+1;
}
while(mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid+1;
tmp_pos = tmp_pos+1;
}
for(i=0;i<=num_elements;i++)
{
numbers[right] = temp[right];
right = right – 1;
}
}

Code:

 Source code
```#include<stdio.h>
int numbers[10]={2,8,4,1,0,7,9,3,5,6};
int temp[10],array_size=10;

void mergeSort(int numbers[],int temp[],int array_size);
void m_sort(int numbers[],int temp[],int left,int right);
void merge(int numbers[],int temp[],int left,int mid,int right);

void main()
{
int i;
clrscr();
printf("\nUnsorted List : ");
for(i=0;i<10;i++)
printf(" %d",numbers[i]);
printf("\n\n Starting Sorting...\n");
mergeSort(numbers,temp,array_size);
printf("\n Sorted List : ");
for(i=0;i<10;i++)
printf(" %d",numbers[i]);
getch();
}

void mergeSort(int numbers[],int temp[],int array_size)
{
m_sort(numbers,temp,0,array_size-1);
}

void m_sort(int numbers[],int temp[],int left,int right)
{
int mid;
if(right > left)
{
mid = (right+left)/2;
m_sort(numbers,temp,left,mid);
m_sort(numbers,temp,mid+1,right);

merge(numbers,temp,left,mid+1,right);
}
}

void merge(int numbers[],int temp[],int left,int mid,int right)
{
int i,left_end,num_elements,tmp_pos;
left_end = mid-1;
tmp_pos = left;
num_elements = right-left+1;
while((left <= left_end) && (mid <= right))
{
if(numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos+1;
left = left+1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos+1;
mid = mid+1;
}
}

while(left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left+1;
tmp_pos = tmp_pos+1;
}
while(mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid+1;
tmp_pos = tmp_pos+1;
}
for(i=0;i<=num_elements;i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}```

ScreenShots:

## Write a program that finds the two smallest numbers in an array of n numbers – IGNOU BCA Assignment 2015 – 16

BACHELOR OF COMPUTER APPLICATIONS

Course Code : BCSL-045
Course Title : Introduction to Algorithm Design Lab
Assignment Number : BCA(IV)/L-045/Assignment/2015
Maximum Marks : 50
Weightage : 25%

Write a program that finds the two smallest numbers in an array of n numbers.

#include<stdio.h>
void main()
{
int I,J,Temp,List[]={6,3,0,4,8,2,5,9,1,7};
clrscr();
printf(“\nElement in Array :\n\n”);
for(J=0;J<10;J++)
{
printf(“%d “,List[J]);
}
for(I=0;I<10;I++)
{
for(J=0;J<=I;J++)
{
if(List[J]>List[I])
{ Temp=List[I];
List[I]=List[J];
List[J]=Temp;
}
}
}
printf(“\n\n\nTwo Smallest numbers :\n\n”);
for(J=0;J<2;J++)
{
printf(“%d “,List[J]);
}
getch();
}

Code:-

 Source code
```c#include<stdio.h>
void main()
{
int I,J,Temp,List[]={6,3,0,4,8,2,5,9,1,7};
clrscr();
printf("\nElement in Array :\n\n");
for(J=0;J<10;J++)
{
printf("%d ",List[J]);
}
for(I=0;I<10;I++)
{
for(J=0;J<=I;J++)
{
if(List[J]>List[I])
{ Temp=List[I];
List[I]=List[J];
List[J]=Temp;
}
}
}
printf("\n\n\nTwo Smallest numbers :\n\n");
for(J=0;J<2;J++)
{
printf("%d ",List[J]);
}
getch();
}```

ScreenShots:-

2. Write a program to generate Fibonacci series of 10 numbers.

Solved program Using Recursion can be found on this link http://cssimplified.com/c-programming/a-c-program-to-find-the-fibonacci-series-of-numbers-using-recursion

Solved program Using NonRecursion can be found on this link http://cssimplified.com/c-programming/design-an-algorithm-draw-a-corresponding-flow-chart-and-write-a-program-in-c-to-print-the-fibonacci-series-10m-jun2006

3. Write a program to reverse a string.

Solved program Using Recursion can be found on this link http://cssimplified.com/c-programming/a-c-program-to-reverse-the-given-string-using-recursion