UNIT 5 notes updated in the below link

UNIT 5 notes click below link

https://sites.google.com/site/cs6202pds1/home





Save water:

Espure water solutions Pvt Ltd

http://enpure.in/sewage-treatment-plant/

Linear Search

                                  Linear Search

#include<stdio.h>
#include<conio.h>
void main()
{
 int a[20],i,ele,n;
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  scanf("%d",&a[i]);
 }
 printf("enter search");
 scanf("%d",&ele);
 for(i=1;i<=n;i++)
 {
  if(ele==a[i])
  {
   printf("Found");
   break;
  }
  if(i==n)
  {
  printf("not found");
 }
}
getch();
}

Merge Sort

                                          Merge Sort

#include<stdio.h>
#include<conio.h>
void merge(int [],int ,int ,int );
void part(int [],int ,int );
int main()
{
 int arr[30];
 int i,size;
 printf("\n\t------- Merge sorting method -------\n\n");
 printf("Enter total no. of elements : ");
 scanf("%d",&size);
 for(i=0; i<size; i++)
 {
   printf("Enter %d element : ",i+1);
   scanf("%d",&arr[i]);
 }
 part(arr,0,size-1);
 printf("\n\t------- Merge sorted elements -------\n\n");
 for(i=0; i<size; i++)
 printf("%d ",arr[i]);
 getch();
 return 0;
}


void part(int arr[],int min,int max)
{
 int mid;
 if(min<max)
 {
   mid=(min+max)/2;
   part(arr,min,mid);
   part(arr,mid+1,max);
   merge(arr,min,mid,max);
 }
}


void merge(int arr[],int min,int mid,int max)
{
  int tmp[30];
  int i,j,k,m;
  j=min;
  m=mid+1;
  for(i=min; j<=mid && m<=max ; i++)
  {
     if(arr[j]<=arr[m])
     {
         tmp[i]=arr[j];
         j++;
     }
     else
     {
         tmp[i]=arr[m];
         m++;
     }
  }
  if(j>mid)
  {
     for(k=m; k<=max; k++)
     {
         tmp[i]=arr[k];
         i++;
     }
  }
  else
  {
     for(k=j; k<=mid; k++)
     {
        tmp[i]=arr[k];
        i++;
     }
  }
  for(k=min; k<=max; k++)
     arr[k]=tmp[k];
}

Quick Sort

                                        Quick Sort

#include<stdio.h>
#include<conio.h>
void qsort(int arr[20], int left, int right);
int main()
{
 int arr[30];
 int i,n;
 printf("Enter total no. of the elements : ");
 scanf("%d",&n);
 printf("Enter total %d elements : \n",size);
 for(i=0; i<n; i++)
    scanf("%d",&arr[i]);
 qsort(arr,0,n-1);
 printf("Quick sorted elements are as  : \n");
 for(i=0; i<n; i++)
    printf("%d\t",arr[i]);
 getch();
 return 0;
}
void qsort(int arr[20], int left, int right)
{
 int i,j,pivot,tmp;
 if(left<right)
 {
   pivot=left;
   i=left+1;
   j=right;
   while(i<j)
   {
     while(arr[i]<=arr[pivot] && i<right)
        i++;
     while(arr[j]>arr[pivot])
        j--;
     if(i<j)
     {
        tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
     }
   }
   tmp=arr[pivot];
   arr[pivot]=arr[j];
   arr[j]=tmp;
   qsort(arr,left,j-1);
   qsort(arr,j+1,right);
 }
}

Selection Sort

                                        Selection Sort

#include <stdio.h>
#include<conio.h>
void main()
{
   int array[100], n, c, d, position, swap;

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

   printf("Enter %d integers\n", n);

   for ( c = 0 ; c < n ; c++ )
      scanf("%d", &array[c]);

   for ( c = 0 ; c < ( n - 1 ) ; c++ )
   {
      position = c;

      for ( d = c + 1 ; d < n ; d++ )
      {
         if ( array[position] > array[d] )
            position = d;
      }
      if ( position != c )
      {
         swap = array[c];
         array[c] = array[position];
         array[position] = swap;
      }
   }

   printf("Sorted list using Selection sort:\n");

   for ( c = 0 ; c < n ; c++ )
      printf("%d\n", array[c]);

  getch();
}

Shell Sort

                                            Shell Sort

#include<stdio.h>
#include<conio.h>
int main()
{
 int arr[30];
 int i,j,k,tmp,num;
 printf("Enter total no. of elements : ");
 scanf("%d", &num);
 for(k=0; k<num; k++)
 {
   printf("\nEnter %d number : ",k+1);
   scanf("%d",&arr[k]);
 }
 for(i=num/2; i>0; i=i/2)
 {
   for(j=i; j<num; j++)
   {
     tmp=arr[j];
       for(k=j; k>=i; k=k-i)
     {
    if(tmp<arr[k-i])

         {
         arr[k]=arr[k-i];
        }
    else
    {
        break;
         }
         arr[k-i]=tmp;
       }
    }
     }
 printf("\t**** Shell Sorting ****\n");
 for(k=0; k<num; k++)
     printf("%d\t",arr[k]);
 getch();
 return 0;
}

Insertion Sort

                                            Insertion Sort

#include <stdio.h>
#include<conio.h>
void main()
{
  int n, array[1000], i, j, t;

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

  printf("Enter %d integers\n", n);

  for (i = 0; i< n; i++) {
    scanf("%d", &array[i]);
  }

  for (j = 1 ; j < n; j++)
  {
    k=j ;

    while ( k> 0 && array[k] < array[k-1])
    {
      t          = array[k];
      array[k]   = array[k-1];
      array[k-1] = t;

      k--;
    }
  }

  printf("Sorted list in ascending order:\n");

  for (i= 0; i< n; i++) {
    printf("%d\n", array[i]);
  }
 getch();
 }

Bubble sort

                                          Bubble sort

#include<stdio.h>
#include<conio.h>
void main()
{
    int A[20], N, Temp, i, j;
    clrscr();
    printf(“\n\n\t ENTER THE NUMBER OF TERMS…: “);
    scanf(“%d”,&N);
    printf(“\n\t ENTER THE ELEMENTS OF THE ARRAY…:”);
    for(i=0; i<N; i++)
    {
        gotoxy(25, 11+i);
        scanf(“\n\t\t%d”, &A[i]);
    }
    for(i=0; i<N-1; i++)
        for(j=0; j<N-i;j++)
            if(A[j]>A[j+1])
            {
                Temp = A[j];
                A[j] = A[j+1];
                A[j+1] = Temp;
            }
    printf(“\n\tTHE ASCENDING ORDER LIST IS…:\n”);
    for(i=0; i<N; i++)
        printf(“\n\t\t\t%d”,A[i]);
    getch();
}

Important part B question

Part B important question Unit III & Unit |IV

 

1. Explain the following for Singly Linked List with example

a)     Search routine. (5)

b)    Traverse routine. (6)

c)     Display routine. (5)

2. Explain the array implementation of Stack ADT.(16)

3. Explain the Insertion routine in singly Linked list.(16)                                                            

 4.Explain the Deletion routine in Doubly Linked list. 

     5.a) Explain the polynomial implementation & addition with eg. (8)

b) Implement the Enqueue and Dequeue operations of Queue using array (8)    

6. What are the various Linked list & its operations? Explain with eg(16)

7. Explain the following for Doubly Linked List with example

a)     Search routine.(5)

b)    Reverse routine.(6)

c)     Display routine.(5)

8. Explain the Linked implementation of Stack ADT.(16)                                                              

9.  a)Express the procedure for converting an Infix expression into Postfix expression with example. (8)

b) Write down the procedure for evaluating an postfix expression. (8)

10. Implement the queue ADT using Array with neat illustration. (8)

     11.Explain with example the insert at first and insert at end operations of circular linked list. (8)

 

 

Unit IV notes updated

https://sites.google.com/site/cs6202pds1/

UNIT 3 notes updated

NOTES LINK:

https://sites.google.com/site/cs6202pds1/

POSTFIX Evaluation

POSTFIX Evaluation

#include<stdio.h>

#include<conio.h>

#include <ctype.h>

int s[20];

int top=-1;       

push(int elem)

{ 

 top++;                    


 s[top]=elem;

}

int pop()

{                      

 return(s[top--]);

}

void main()

{                         

 char pofx[50],ch;

 int i=0,op1,op2;

 printf("\n\nRead the Postfix Expression ? ");

 scanf("%s",pofx);

 while( (ch=pofx[i++]) != '\0')

 {

  if(isdigit(ch)) 
   push(ch-'0'); 

  else

  {        

   op2=pop();

   op1=pop();

   switch(ch)

   {

   case '+':
   push(op1+op2);
    break;

   case '-':
   push(op1-op2); 
   break;

   case '*':
   push(op1*op2);
   break;

   case '/':
   push(op1/op2); 
   break;

   }

  }

 }

 printf("\n Given Postfix Expn: %s\n",pofx);

 printf("\n Result after Evaluation: %d\n",s[top]);
getch();

}

INFIX to POSTFIX convertion

INFIX to POST FIX

#include<stdio.h> 

#include<conio.h>          

#include <ctype.h>

char s[20];

int top = -1;

void push(char elem)

{

 top++;

 s[top] = elem;

}

char pop()

{ 

return (s[top--]);

}

int pr(char elem)

{

 switch (elem)

 {

 case '(':

  return 1;

 case '+':

 case '-':

  return 2;

 case '*':

 case '/':

  return 3;

 }

 return 0;

}

void main()

 {

char infx[50], pofx[50], ch, elem;

 int i = 0, k = 0;

 printf("\n\nRead the Infix Expression ? ");

 scanf("%s", infx);

 while ((ch = infx[i++]) != '\0')

{

  if (ch == '(')

   push(ch);

  else if (isalnum(ch))

   pofx[k++] = ch;

  else if (ch == ')')

{

   while (s[top] != '(')

    pofx[k++] = pop();

   elem = pop();

  }

else

{

   while (pr(s[top]) >= pr(ch))

    pofx[k++] = pop();

   push(ch);

  }

 }

 while (top !=-1 )

  pofx[k++] = pop();

 pofx[k] = '\0';

printf("\n\nGiven Infix Expn: %s  Postfix Expn: %s\n", infx, pofx);

}

Assignment II - UNIT III & UNIT IV

UNIT III & UNIT IV

Part A

1.   Define Data Structures

2.      Define ADT.

3.      What is Data Structure and list its types

4.      Define a node.

5.      List the advantages of Linked List over array

6.      List the types of linked list.

7.      List out the applications of a linked list

8.      Write a procedure to insert at beginning  in a Singly Linked List

9.      What is header?

10.  Write a routine to find an element in Singly Linked list.

11.  What are the advantages and disadvantages of doubly linked list over Singly Linked list?

12.   Write the structure declaration for defining a node in Polynomial representation.

13.  Write a procedure for Polynomial differentiation.

Void polyDiff ()

{

Poly *ptr1,*newnode;

ptr1=list1;

while (ptr1 !=0 )

{

newnode=malloc(sizeof(struct poly));

newnode->coeff=(ptr1->coeff)*(ptr1->power);

newnode->power=ptr1->power -1;

list3=create(list3,newnode);

ptr1=ptr1->next;

}

}

14.  List the application of List ADT

15.  List the advantage and disadvantage of circular Linked list

16.   How to traverse a Linked List

17.  Give the structure declaration of a node in doubly linked list

18.  Write the routine for reverse in doubly Linked List.

19.  Write a routine to traverse in doubly Linked list.

20. What does the following function do for a givem Linked List

void fun2(struct node* head) {   if(head== NULL)     return;   printf("%d  ", head->data);   if(head->next != NULL )     fun2(head->next->next);   printf("%d  ", head->data);   }

21.  Define Stack.

22.  What are the operations performed on stack and write its exception condition

23.  List the applications of stack.

24.  Write the steps for converting infix to postfix.

25.  Convert the infix expression (A+B) * (C/D) – E to its equivalent postfix expression.

26.  How do push and pop elements in linked list.

27.  Write a routine to return the top element of the stack.

28.  What is stack overflow condition?

29.  Define Queue data structure and give some application for it.

30.  When we can declare a queue as FULL?

Part –B

 1.      What are the various Linked list  & its operations? Explain with example.

2.      Explain the Insertion & Deletion routine in singly Linked list.

3.      Explain the Insertion & Deletion routine in Doubly Linked list.

4.      Explain the following for Singly Linked List with example

      a)      Search routine.

      b)      Traverse routine.

      c)      Display routine.

5.      Explain the following for Doubly Linked List with example

      a)      Search routine.

      b)      Reverse routine.

      c)      Display routine.

6.      Explain with example the operations of circular linked list.

7.      Write the routine to implement create, display, Merge & subtraction of two polynomial.

8.      Explain the array implementation of Stack ADT.

9.      Explain the Linked implementation of Stack ADT.

10.  Write the program for converting an Infix expression into Postfix expression.

11.  Explain how stack is applied for evaluating an Postfix expression.

12.  Implement the queue ADT using Array with neat illustration.

13.  Implement the queue ADT using Linked list.