Recursive Binary Search

Binary Search Using Recursion

#include<stdio.h>

void binary_search(int a[100], int low, int high, int key)

{

                int mid;

                if(low>high)

                {

                                printf("\nKey not found");

                                return;

                }

                mid = (low+high)/2;

                if(key == a[mid])

                {

                                printf("\nKey element is found at position = %d", mid);

                }

                else  if(key<a[mid])

                                binary_search(a, low, mid-1, key);

                else

                                binary_search(a, mid+1, high, key);

}

void main()

{

                int a[100], i, n, pos, key;

                printf("\nEnter value of n: ");

                scanf("%d", &n);

                printf("\nEnter the array elements: ");

                for(i=0; i<n; i++)

                                scanf("%d", &a[i]);

                printf("\nEnter key: ");

                scanf("%d", &key);

                binary_search(a, 0, n-1, key);

}

Output:

Enter value of n: 6

Enter the array elements: 11 22 33 44 55 66

Enter key: 55

Key element is found at position = 5

Enter value of n: 6

Enter the array elements: 11 22 33 44 55 66

Enter key: 88

Key is not found

Multiple stacks in 1 Dimensional Array

Multiple stacks in 1 Dimensional Array

#include<stdio.h>
#include<stdlib.h>
#define MAX 12

int stack[MAX];
int m=MAX, n;
int top[10], boundary[10];

void push(int i, int item )
{
          if(top[i] == boundary[i+1])
          {
                    printf("\nStack%d overflow", i);
          }
          else
         {
                   top[i] = top[i] +1;
                   stack[top[i]] = item;
         }
}
void pop(int i)
{
         int item;
         if(top[i] == boundary[i])
         {
                  printf("\nStack%d underflow", i);
         }
         else
        {
                 item = stack[top[i]];
                 printf("\nItem that got deleted from stack%d is %d", i, item);
                 top[i] = top[i] - 1;
         }
}

void display(int i)
{
          int j;
          if(top[i] == boundary[i])
          {
                     printf("\nStack%d is empty", i);
                     return;
          }
          else
         {
                    printf("\n");
                    for(j=top[i]; j>=boundary[i]+1; j--)
                               printf("| %d |\n",stack[j]);
          }
}

void main()
{
          int ch, stackno, item,i;
          printf("\nEnter the number of stacks: ");
          scanf("%d",&n);
          for(i=0;i<n;i++)
          {
                  top[i] = boundary[i] = (i*(m/n)) - 1;
                  printf("\ntop[%d] = %d and boundary[%d] = %d",i,top[i], i, boundary[i]);
          }
          boundary[i] = MAX-1;
   
          while(1)
          {
                  printf("\n\n~~~MENU~~~");
                  printf("\n1.Push operation");
                  printf("\n2.Pop operation");
                  printf("\n3.Display");
                  printf("\n4.Exit");
                  printf("\nPlease enter your choice: ");
                  scanf("%d", &ch);
                  switch(ch)
                 {
                            case 1: printf("\nEnter a item to be pushed: ");
                                        scanf("%d",&item);
                                        printf("\nEnter the stack number: ");
                                        scanf("%d",&stackno);
                                        push(stackno, item);
                                        break;

                           case 2: printf("\nEnter the stack number: ");
                                       scanf("%d",&stackno);
                                       pop(stackno);
                                       break;

                          case 3: for(stackno=0;stackno<n;stackno++)
                                     {
                                              printf("\nStack%d contents are: ", stackno);
                                              display(stackno);
                                     }
                                     break;

                          case 4:exit(0);
                          default: printf("\nPlease enter a valid choice");
                                       break;
                }
       }
}

Output:

Enter the number of stacks: 3

top[0] = -1 and boundary[0] = -1
top[1] = 3  and boundary[1] = 3
top[2] = 7  and boundary[2] = 7

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 11
Enter the stack number: 0

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 12
Enter the stack number: 0

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 13
Enter the stack number: 0

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 14
Enter the stack number: 0

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 15
Enter the stack number: 0
Stack0 overflow

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 21
Enter the stack number: 1

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 22
Enter the stack number: 1


~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 23
Enter the stack number: 1

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 31
Enter the stack number: 2

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 32
Enter the stack number: 2

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 33
Enter the stack number: 2

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 3
Stack0 contents are:
| 14 |
| 13 |
| 12 |
| 11 |

Stack1 contents are:
| 23 |
| 22 |
| 21 |

Stack2 contents are:
| 33 |
| 32 |
| 31 |


~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 2
Enter the stack number: 1
Item that got deleted from stack1 is 23

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 3

Stack0 contents are:
| 14 |
| 13 |
| 12 |
| 11 |

Stack1 contents are:
| 22 |
| 21 |

Stack2 contents are:
| 33 |
| 32 |
| 31 |

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 2
Enter the stack number: 1
Item that got deleted from stack1 is 22

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 2
Enter the stack number: 1
Item that got deleted from stack1 is 21

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 2
Enter the stack number: 1
Stack1 underflow

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 3

Stack0 contents are:
| 14 |
| 13 |
| 12 |
| 11 |

Stack1 contents are:
Stack1 is empty

Stack2 contents are:
| 33 |
| 32 |
| 31 |

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 4

A Mazing Problem

A Mazing Problem

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

typedef struct
{
      short int vert;
      short int horiz;
}Offsets;

Offsets move[8];

typedef struct
{
       short int row;
       short int col;
       short int dir;
}Element;

Element Stack[50];
int maze[10][10];
int mark[10][10];
int top=-1;
int exit_row,exit_col;

void readMaze()
{
         int r, c;
         int i, j;

         printf("\nEnter the no of rows in the matrix: ");
         scanf("%d", &r);

         printf("\nEnter the no of cols in the matrix:   ");
         scanf("%d",&c);

         printf("\nEnter the elements of the matrix:   ");
         for(i=0;i<r;i++)
        {
                 for(j=0;j<c;j++)
                 {
                          scanf("%d",&maze[i][j]);
                  }
        }
        exit_row = r-2;
        exit_col = c-2;
}

void setMoveTable()
{
          move[0].vert = -1, move[0].horiz = 0;
          move[1].vert = -1, move[1].horiz = 1;
          move[2].vert = 0,   move[2].horiz = 1;
          move[3].vert = 1,   move[3].horiz = 1;
          move[4].vert = 1,   move[4].horiz = 0;
          move[5].vert = 1,   move[5].horiz = -1;
          move[6].vert = 0,   move[6].horiz = -1;
          move[7].vert = -1,  move[7].horiz = -1;
}

void push(Element ele)
{
          top = top+1;
          Stack[top].row = ele.row;
          Stack[top].col = ele.col;
          Stack[top].dir = ele.dir;
          return;
}

Element pop()
{
          Element delItem;
          delItem.row = Stack[top].row;
          delItem.col = Stack[top].col;
          delItem.dir = Stack[top].dir;
          top = top-1;
          return delItem;
}

void findpath()
/* function to search for path in the maze */
{
          int i,row,col,nextRow,nextCol,dir,found=0;
          Element position;
          mark[1][1] = 1,top=0;
          Stack[0].row = 1;
          Stack[0].col = 1;
          Stack[0].dir = 0;

          while(top>-1 && !found)
         {
                   position = pop();

                   row = position.row;
                   col = position.col;
                   dir = position.dir;

                   while(dir<8 && !found)
                   {
                             nextRow = row + move[dir].vert;
                             nextCol = col + move[dir].horiz;

                             if(nextRow == exit_row && nextCol == exit_col)
                                           found = 1;

                             else if(!maze[nextRow][nextCol] && !mark[nextRow][nextCol])
                             {
                                           mark[nextRow][nextCol] = 1;
                                           position.row = row;
                                           position.col = col;
                                           position.dir = ++dir;
                                           push(position);
                                           row = nextRow;
                                           col = nextCol;
                                           dir = 0;
                             }
                            else
                                       ++dir;
                  }
          }
          if(found)
          {
                     printf("\nThe path is:\n");
                     printf("row \t col \n");
                     for(i=0;i<=top;i++)
                             printf("%2d%5d \n",Stack[i].row,Stack[i].col);
               
                     printf("%2d%5d\n",row,col);
                     printf("%2d%5d\n",exit_row,exit_col);
            }
            else
                     printf("\nThe given maze does not have a path");
}

void main()
{
           readMaze();
           setMoveTable();
           findpath();
           return;
}

Output:

just put 1s for indicating border/wall (blue color)

Enter the no of rows in the matrix: 11

Enter the no of cols in the matrix:   8

Enter the elements of the matrix:
1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1
1 1 1 1 1 1 0 1
1 1 0 0 0 0 1 1
1 0 1 1 1 1 1 1
1 1 0 0 0 0 1 1
1 1 1 1 1 1 0 1
1 1 0 0 0 0 1 1
1 0 1 1 1 1 1 1
1 1 0 0 0 0 0 1
1 1 1 1 1 1 1 1

The path is:
row      col
 1          1
 1          2
 1          3
 1          4
 1          5
 2          6
 3          5
 3          4
 3          3
 3          2
 4          1
 5          2
 5          3
 5          4
 5          5
 6          6
 7          5
 7          4
 7          3
 7          2
 8          1
 9          2
 9          3
 9          4
 9          5
 9          6

Credits,
       Manoj T

Recursion Question set

Recursion 

Data Structures 15CS33

1.      What is recursion? Give two conditions to be followed for successive working of recursive program. Write a 'c' recursive program to solve tower of Hanoi problem.

(December 2007)

(December 2009)

(December 2010)

(June 2013)

(December 2014)

(December 2015)

(8 marks)

2.      Write a recursive function for computing n^th Fibonacci term of a Fibonacci sequence. Hence give the trace of stack contents for n=4.

(June 2009)

(10 marks)

3.      Write a recursive function to find the GCD of two integers

(December 2009)

(6 marks)

4.      Determine what the following recursive C function computes

int func(int n)

{

            if(n==0)

                        return 0;

            return (n+func(n-1));

}

Write an iterative function to accomplish the same.

(June 2010)

(5 marks)

5.      Write a recursive function fact(n) to find the factorial of an integer. Diagrammatically explain how the stacking and unstacking taking place during execution for fact(4)

(June 2010)

(10 marks)

6.      Write recursion function to find the maximum of n numbers.

(December 2010)

(8 marks)

7.      Write recursion function to reverse the positive integer number.

(June 2011)

(4 marks)

8.      Write a recursive function to implement a binary search.

(December 2011)

(December 2015)

(08 marks)

9.      Write a recursive function to sum a list of numbers.

(June 2015)

Queue Question Set

Queue

Data Structures 15CS33 

1.      What is a linear queue? What are the applications of linear queue? Implement/Write a C program to simulate the 1) insert 2) delete  3)display operations.

(December 2007)

(8 marks)

2.      What is circular queue? What ate the advantages of Circular queue over simple queue.

Write implementation for circular queue using array. Also write following routine of circular queue. 1)      insert 2) delete 3) display

(June 2009)

(December 2010)

(June 2011)

(December 2013)

(December 2015)

(10 marks)

3.      Explain priority queue.

(December 2009)

(6 marks)

4.      Explain the working of simple queue

(June 2010)

(5 marks)

5.      For a given circular queue shown in Fig below write the values of front and rear in the table after each specified operation is performed. Queue full/empty conditions must be considered. 0-7 indicates the array indices.

(December 2011)(4 marks)

6.      Explain how would you implement a circular queue using dynamically allocated arrays.

(June 2013)

Stack Questions set

Stack
Data Structures 15CS33 

1.     Define stack and List and implement basic operations in stack using C (push, pop, isempty, isfull). Implement reversing a string using stack (array implementation) in C.

(December 2007)

(June 2009)

(June 2010)

(December 2010)

(December 2010)

(December 2011)

(December 2012)

(December 2013)

(December 2014)

(December 2015)

(12 marks)

2.      Write a C program to implement multiple stacks using single array

(December 2007)

(12 marks)

3.      Write short notes on Applications of stacks

(December 2007)

(5 marks)

4.      Write an algorithm to evaluate postfix expression. Trace the same algorithm with stack contents for the following expression A B C + * C B A - + *    with A=1, B=2, C=3.

(June 2009)

(December 2009)

(10 marks)

5.      Convert each of the following expression to its postfix and prefix forms

a)      ( A + B ) * C – D $ E * F

b)     A - B / C * D $ E

c)      ( A + B ) * ( C + D – E ) * F

d)     ( ( ( A + ( B - C ) * D ) ^ E ) + F )

e)      ( a + b ) * d + e / ( f + a * d ) + c

f)       ( ( a / ( b - c + d ) ) * ( e - a ) * c )

g)      a / b – c + d * e – a * c

(June 2009)

(December 2012)

(December 2013)

(12 marks)

6.      What is stack? Indicate how stack is represented in C.

(December 2009)

(5 marks)

7.      Show using the tabular column how the expression (a+b)*c is converted to a postfix expression according to the infix to postfix coversion algorithm

(June 2010)

(5 marks)

8.  Write the algorithm to evaluate a valid postfix expression and hence evaluate the postfix expression.

      6 2 3 + - 3 8 2 / + *

  

      1 2 3 + * 3 2 1 - +  *

  

       A B + C D E - * /                   for A=5 B=6 C=4 D=3 E=7

  

       6 2 3 + 3 8 2 / + * 2 $ 3 +

All the operands are single digit positive integers and operators are binary in nature.

(June 2010)

(December 2010)

(December 2011)

(June 2013)

(June 2015)

(December 2015)

(10 marks)

9.      Write a algorithm and function to convert a valid infix expression to postfix expression. Demonstrate the same function with example.(using stack)

a)      ( a * b ) + c / d

b)     ( ( ( a / b ) – c ) + ( d * e ) ) - (a * c)

c)      a * ( b + c ) * d

d)     A $ B * C – D + E / F / ( G + H )

e)      A – B / ( C * D $ E )

(June 2011)

(June 2012)

(June 2014)

(December 2015)

(12 marks)

10.  Write a C program to implement a two primitive operations on stack using dynamic memory allocation.

(June 2012)

(8 marks)

11.  What is system stack? How the control is transferred to or from the function with the help of activation records.

(December 2012)

(6 marks)

12.  Convert the infix expression to postfix expression and evaluate the same.

a / b – c + d * e – a * c   for a=6 b=3 c=1 d=2 e=4

 (June 2013)

(6 marks)

13.  How multiple stacks implemented using one dimensional array? Explain with suitable example.

(June 2014)

(4 marks)

Circular Queue Using an Array

Circular Queue Using an Array

#include <stdio.h>

#include<stdlib.h>

#define MAX 3

char cq[MAX];

int front = -1,rear = -1;

void add(char);

void del();

void display();

int main()

{

            int ch;

            char item;

            while(1)

            {

                        printf("\n\n~~Main Menu~~");

                        printf("\n==> 1. Insertion and Overflow Demo");

                        printf("\n==> 2. Deletion and Underflow Demo");

                        printf("\n==> 3. Display");

                        printf("\n==> 4. Exit");

                        printf("\nEnter Your Choice: ");

                        scanf("%d", &ch);

                        switch(ch)

                        {

                                    case 1: printf("\n\nEnter the element to be inserted: ");

                                                scanf("%d", &item);

                                                add(item);

                                                break;

                                    case 2: del();

                                                break;

                                   case 3: display();

                                                break;

                                    case 4: exit(0);

                                    default: printf("\n\nPlease enter a valid choice");

                        }

            }

}

void add(char item)

{

            if(front == (rear+1)%MAX)

                        printf("\n\n~~Circular Queue Overflow~~");

            else

            {

                        if(front == -1)

                                    front = rear = 0;

                        else

                                    rear = (rear+1)%MAX;

                        cq[rear] = item;

            }

}

void del()

{

            char item;

            if(front == -1)

            {

                        printf("\n\n~~Circular Queue Underflow~~");

            }

            else

            {

                        item = cq[front];

                        if(front == rear) //only one element

                                    front = rear = -1;

                        else

                                    front = (front+1)%MAX;

                        printf("\n\nDeleted element from the queue is: %d ", item );

            }

}

void display ()

{

            int i ;

            if(front == -1)

            {

                        printf("\n\nCircular Queue Empty");

                        return;

            }

            else

            {

                        printf("\nCircular Queue contents are:\n");

                        printf("\nFront[%d]-> ", front);

                        for(i=front; i!=rear ; i=(i+1)%MAX)

                        {

                                    printf("  %d", cq[i]);

                        }

                        printf("  %d",cq[i]);

                        printf(" <-[%d]Rear", rear);

    }

}

Output:

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 11

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 22

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 33

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 44

~~Circular Queue Overflow~~

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[0]->   11  22  33 <-[2]Rear

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 2

Deleted element from the queue is: 11

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 2

Deleted element from the queue is: 22

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[2]->   33 <-[2]Rear

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 1

Enter the element to be inserted: 66

~~Main Menu~~

==> 1. Insertion and Overflow Demo

==> 2. Deletion and Underflow Demo

==> 3. Display

==> 4. Exit

Enter Your Choice: 3

Circular Queue contents are:

Front[2]->   33  66 <-[0]Rear