* 1.

Program to search an element in the array using Linear Search

Technique *

Algorithm:

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the first element in the list.

Step 3 - If both are matched, then display "Given element is found!!!" and terminate the function

Step 4 - If both are not matched, then compare search element with the next element in the list.

Step 5 - Repeat steps 3 and 4 until search element is compared with last element in the list.

Step 6 - If last element in the list also doesn't match, then display "Element is not found!!!" and
terminate the function.

Program:
#include<stdio.h>
#include<conio.h>
int main()
{
int a[100],search,i,n;
clrscr();
printf("\n Enter number of elements in array");
scanf("%d",&n);
printf("\n Enter %d elements",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter a number to search");
scanf("%d",&search);
for(i=0;i<n;i++)
{
if(search==a[i])
 {
printf("\n Element found at location %d",i+1);
break;
}
}
if(i==n)
printf("Element not found");
return 0;
}
Output:
Enter number of elements in array 5
Enter 5 elements 56 64 32 87 69
Enter a number to search 64
Element found at location 2
 *2. Program to search an element in Binary Search Technique *

Algorithm:

Step 1 - Read the search element from the user.

Step 2 - Find the middle element in the sorted list.

Step 3 - Compare the search element with the middle element in the sorted list.

Step 4 - If both are matched, then display "Given element is found!!!" and terminate the function.

Step 5 - If both are not matched, then check whether the search element is smaller or larger than
the middle element.

Step 6 - If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left
sublist of the middle element.
 Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right
sublist of the middle element.

Step 8 - Repeat the same process until we find the search element in the list or until sublist
contains only one element.

Step 9 - If that element also doesn't match with the search element, then display "Element is not
found in the list!!!" and terminate the function.

Program:

#include<stdio.h>
#include<conio.h>
int main()
{
int c,first,last,middle,n,search,array[100];
clrscr();
printf("\n Enter number of elements");
scanf("%d",&n);
printf("\n Enter %d integers in sorted order \n",n);
for(c=0;c<n;c++)
scanf("%d",&array[c]);
printf("\n Enter value to find \n");
scanf("%d",& search);
first=0;
last=n-1;
middle=(first+last)/2;
while(first<=last)
{
if(array[middle]<search)
first=middle+1;
else if (array [middle]==search)
{
printf("\n %d found at location %d. \n",search,middle+1);
break;
}
else
 last=middle-1;
middle=(first+last)/2;
}
if(first>last)
printf("not found! %d isn't present in the list.\n",search);
return 0;
}
Output:
Enter number of elements 5
Enter 5 integers in sorted order 34 45 67 78 88
Enter value to find 67
67 found at location 3.
 * 3. Program to sort elements using Bubble Sort Technique *

Algorithm:

Step 1: Start with the first element.

Step 2:Compare the current element with the next element.

Step 3:If the current element is greater than the next element, then swap both the elements. If
not, move to the next element.

Step 4: Repeat steps 1 – 3 until we get the sorted list.

Program:

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],n,i,j,temp;
clrscr();
printf("\n enter number of elements");
scanf("%d",&n);
printf("\n enter %d elements",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
 {
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("\n elements in sorted order");
for(i=0;i<n;i++)
printf("\t %d",a[i]);
getch();
}

Output:
enter number of elements 5
enter 10 elements 76 56 34 89 80
elements in sorted order 34 56 76 80 89
 * 4. Program to sort elements using selection Sort Technique *
Algorithm:

Step 1 - Select the first element of the list (i.e., Element at first position in the list).

Step 2: Compare the selected element with all the other elements in the list.
 Step 3: In every comparison, if any element is found smaller than the selected element (for
Ascending order), then both are swapped.

Step 4: Repeat the same procedure with element in the next position in the list till the entire list is
sorted.

Program:

#include <stdio.h>
void selection(int arr[], int n)
{
int i, j, small;

for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
small = i; //minimum element in unsorted array

for (j = i+1; j < n; j++)

if (arr[j] < arr[small])
small = j;
// Swap the minimum element with the first element
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}
void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
 printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}

Output:
enter number of elements 5
enter 10 elements 76 56 34 89 80
elements in sorted order 34 56 76 80 89
 * 5. Program to sort elements using Insertion Sort *

Algorithm:

Step 1 - Assume that first element in the list is in sorted portion and all the remaining elements
are in unsorted portion.

Step 2: Take first element from the unsorted portion and insert that element into the sorted
portion in the order specified.

Step 3: Repeat the above process until all the elements from the unsorted portion are moved into
the sorted portion.

Program:
#include <stdio.h>
void insert(int a[], int n)
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;

while(j>=0 && temp <= a[j])

{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
\
oid printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);

return 0;
}
Output:
 * 6. Program to sort elements using quick Sort *

Algorithm:

Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in the list).

Step 2 - Define two variables i and j. Set i and j to first and last elements of the list respectively.

Step 3 - Increment i until list[i] > pivot then stop.

Step 4 - Decrement j until list[j] < pivot then stop.

Step 5 - If i < j then exchange list[i] and list[j].

Step 6 - Repeat steps 3,4 & 5 until i > j.

Step 7 - Exchange the pivot element with list[j] element.

Program:

void quickSort(int list[10],int first,int last){

int pivot,i,j,temp;

if(first < last){

pivot = first;
i = first;
j = last;

while(i < j){

while(list[i] <= list[pivot] && i < last)
i++;
while(list[j] && list[pivot])
j--;
if(i < j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}

temp = list[pivot];
list[pivot] = list[j];
list[j] = temp;
quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}
Output:
How many elements are u going to enter? 10
Enter 10 elements: 2 3 5 7 1 9 3 8 0 4
Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9
 * 7. Program to sort elements using merge Sort *

Algorithm:

Step 1 − if it is only one element in the list it is already sorted, return.

Step 2 − divide the list recursively into two halves until it can no more be divided.

Step 3 − merge the smaller lists into new list in sorted order.

Program:

#include <stdio.h>
void merge(int a[], int beg, int mid, int end)

int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;

int LeftArray[n1], RightArray[n2];

for (int i = 0; i < n1; i++)

LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];

i = 0; j = 0;
k = beg;
 while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}

while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}

void mergeSort(int a[], int beg, int end)

{
if (beg < end)
{
 int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}

/* Function to print the array */

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

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}
Output:
 *8. Program to implement stack using array *

Algorithm:

Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.

Step 2 - Declare all the functions used in stack implementation.

Step 3 - Create a one dimensional array with fixed size (int stack[SIZE])

Step 4 - Define a integer variable 'top' and initialize with '-1'. (int top = -1)

Step 5 - In main method, display menu with list of operations and make suitable function calls to
perform operation selected by the user on the stack.
Program:
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
clrscr();
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t [Link]\n\t [Link]\n\t [Link]\n\t [Link]");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
 break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
 printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}
Output:
Enter the size of STACK[MAX=100]:10

STACK OPERATIONS USING ARRAY

--------------------------------
[Link]
[Link]
[Link]
[Link]
Enter the Choice:1
Enter a value to be pushed:12
Enter the Choice:1
Enter a value to be pushed:24
Enter the Choice:1
Enter a value to be pushed:98
Enter the Choice:3
The elements in STACK
98
24
12
Press Next Choice
Enter the Choice: 2
The popped elements is 98
Enter the Choice: 3
The elements in STACK
24
12
Press Next Choice
Enter the Choice: 4
EXIT POINT

* 9. Program to implement Queue using Array *

Algorithm:

Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.

Step 2 - Declare all the user defined functions which are used in queue implementation.

Step 3 - Create a one dimensional array with above defined SIZE (int queue[SIZE])

Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -
1, rear = -1)

Step 5 - Then implement main method by displaying menu of operations list and make suitable
function calls to perform operation selected by the user on queue.
Program:
#include<stdio.h>
#define n 5
int main()
{
int queue[n],ch=1,front=0,rear=0,i,j=1,x=n;
printf("Queue using Array");
printf("\[Link] \[Link] \[Link] \[Link]");
while(ch)
{
printf("\nEnter the Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(rear==x)
printf("\n Queue is Full");
else
{
printf("\n Enter no %d:",j++);
scanf("%d",&queue[rear++]);
}
break;
case 2:
if(front==rear)
{
printf("\n Queue is empty");
}
else
{
printf("\n Deleted Element is %d",queue[front++]);
x++;
}
break;
case 3:
printf("\nQueue Elements are:\n ");
 if(front==rear)
printf("\n Queue is Empty");
else
{
for(i=front; i<rear; i++)
{
printf("%d",queue[i]);
printf("\n");
}
break;
case 4:
exit(0);
default:
printf("Wrong Choice: please see the options");
}
}
}
return 0;
}
Output:
Queue using Array
[Link]
[Link]
[Link]
[Link]
Enter the Choice: 1
Enter no 1:10

Enter the Choice: 1

Enter no 2:54
Enter the Choice: 1
Enter no 3:98
Enter the Choice: 1
Enter no 4:234
Enter the Choice: 3
Queue Elements are:
10
54
9
234
Enter the Choice: 2
Deleted Element is 10
Enter the Choice: 3
Queue Elements are:
54
98
234
Enter the Choice: 4
 * 10. Program to implement Single Linked List *
Algorithm:

1. Create a class Node which has two attributes: data and next. Next is a pointer to
the next node.
2. Create another class which has two attributes: head and tail.
3. addNode() will add a new node to the list:
a. Create a new node.
b. It first checks, whether the head is equal to null which means the list is
empty.
c. If the list is empty, both head and tail will point to the newly added node.
d. If the list is not empty, the new node will be added to end of the list such
that tail's next will point to the newly added node. This new node will
become the new tail of the list.
4. display() will display the nodes present in the list:
. Define a node current which initially points to the head of the list.
a. Traverse through the list till current points to null.
b. Display each node by making current to point to node next to it in each
iteration.

Program:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void beginsert ();
void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\[Link] in begining\[Link] at last\[Link] at any random location\[Link] from Beginning
\n
[Link] from last\[Link] node after specified location\[Link] for an element\[Link]\[Link]\n");

printf("\nEnter your choice?\n");

scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
 case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
 if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}

}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
 }
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");

}
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
 temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}

}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
 }
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}

else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
 printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
 }
if(flag==1)
{
printf("Item not found\n");
}
}

}
void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}
Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
1
Enter value
1
Node inserted
*********Main Menu*********
Choose one option from the following list ...

===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
2
Enter value?
2
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
3
Enter element value1
Enter the location after which you want to insert 1

Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
8
printing values . . . . .
1
2
1
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]

Enter your choice?

2
Enter value?
123
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
1
Enter value
1234
Node inserted
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
4
Node deleted from the begining ...
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
5
Deleted Node from the last ...
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
6
Enter the location of the node after which you want to perform deletion
1
Deleted node 2
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
8
printing values . . . . .
1
1
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
7
Enter item which you want to search?
1
item found at location 1
item found at location 2
*********Main Menu*********
Choose one option from the following list ...
===============================================
[Link] in begining
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] node after specified location
[Link] for an element
[Link]
[Link]
Enter your choice?
9

Theory Questions
1. write about the following
a) linked list and types
b) stack and queue
1. write about the following
a) Tree terminology
b) Tree traversal techniques
c) Operations on BST(binary seacrh tree)

2. write about the following

a)DFS and BFS
b) kruskals and prims algorithms
c)find shortest path using Dijkstras algorithm