Data Structures and Algorithms 2071

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.

 It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.

Difference between Stack and Queue

Program to implement stack operations

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void push(int);

void pop();

void display();

int stack[SIZE], top = -1;

void main()

{

   int value, choice;

   clrscr();

   while(1){

      printf("\\n\\n***** MENU *****\\n");

      printf("1. Push\\n2. Pop\\n3. Display\\n4. Exit");

      printf("\\nEnter your choice: ");

      scanf("%d",&choice);

      switch(choice){

          case 1: printf("Enter the value to be insert: ");

                  scanf("%d",&value);

                  push(value);

                  break;

          case 2: pop();

                  break;

          case 3: display();

                  break;

          case 4: exit(0);

          default: printf("\\nWrong selection!!! Try again!!!");

      }

   }

}

void push(int value){

   if(top == SIZE-1)

      printf("\\nStack is Full!!! Insertion is not possible!!!");

   else{

      top++;

      stack[top] = value;

      printf("\\nInsertion success!!!");

   }

}

void pop(){

   if(top == -1)

      printf("\\nStack is Empty!!! Deletion is not possible!!!");

   else{

      printf("\\nDeleted : %d", stack[top]);

      top--;

   }

}

void display(){

   if(top == -1)

      printf("\\nStack is Empty!!!");

   else{

      int i;

      printf("\\nStack elements are:\\n");

      for(i=top; i>=0; i--)

          printf("%d\\n",stack[i]);

   }

}

A linked list is a non-sequential collection of data items (nodes). It is a dynamic data structure. For every data item in a linked list, there is an associated pointer that would give the memory location of the next data item in the linked list. The data items in the linked list are not in consecutive memory locations. They may be anywhere, but the accessing of these data items is easier as each data item contains the address of the next data item.

Each node (data item) consists of two parts:

      • Info: the actual element to be stored in the list. It is also called data field.

      • Link: one or two links that points to next and previous node in the list. It is also called next or pointer field.

info   next                                         

Steps involved in inserting a node at the beginning of singly linked list:

let *head be the pointer to first node in the current list

1. Create a new node using malloc function

        NewNode=(NodeType*)malloc(sizeof(NodeType));

2. Assign data to the info field of new node

        NewNode->info=newItem;

3. Set next of new node to head

        NewNode->next=head;

4. Set the head pointer to the new node

        head=NewNode;

5. End

Steps involved in inserting a node at the end of the singly linked list:

let *head be the pointer to first node in the current list

1. Create a new node using malloc function

        NewNode=(NodeType*)malloc(sizeof(NodeType));

2. Assign data to the info field of new node

        NewNode->info=newItem;

3. Set next of new node to NULL

        NewNode->next=NULL;

4. if (head ==NULL)then

        Set head =NewNode.and exit.

5. Set temp=head;

6 while(temp->next!=NULL)

        temp=temp->next;     //increment temp

7. Set temp->next=NewNode;

8. End

Steps involved in deleting the first node of singly linked list:

let *head be the pointer to first node in the current list

1. If(head==NULL) then

        print “Void deletion” and exit

2. Store the address of first node in a temporary variable temp.

        temp=head;

3. Set head to next of head.

        head=head->next;

4. Free the memory reserved by temp variable.

        free(temp);

5. End

Steps involved in deleting the last node of singly linked list:

let *head be the pointer to first node in the current list

1. If(head==NULL) then //if list is empty

        print “Void deletion” and exit

2. else if(head->next==NULL) then //if list has only one node

        Set temp=head;

        print deleted item as,

        printf(“%d” ,head->info);

        head=NULL;

        free(temp);

3. else

        set temp=head;

        while(temp->next->next!=NULL)

            set temp=temp->next;

        End of while

        free(temp->next);

Set temp->next=NULL;

4. End

Traversing a graph means visiting all the vertices in a graph exactly one. In graph all nodes are treated equally. So the starting nodes in graph can be chosen arbitrarily.

A graph traversal finds the edges to be used in the search process without creating loops that means using graph traversal we visit all vertices of graph without getting into looping path.

Depth First Traversal (DFS)

This technique picks up a node and marks it. An unmarked adjacent node to previous node is then selected and marked, become the new start node, possibly leaving the previous node with unexplored edges for the present. The traversal continued recursively, until all unmarked nodes of the current path are visited. The process is continued for all the paths of the graph. If this cannot be done, move back to another vertex and repeat the process. The whole process is continued until all the vertices are met. This method of search is also called backtracking. A stack data structure is maintained in the technique to maintain the list of incident edges and marked nodes.

Algorithm:

DFS(G,s)

{

    T = {s};

    Traverse(s);

}

Traverse(v)

{

    for each w adjacent to v and not yet in T

    {

        T = T ∪ {w};     //put edge {v, w} also

        Traverse (w);

    }

}

Example:

Choose a as initial vertex then we have

Let A be an array of type T and has n elements then it satisfied the following operations:

• CREATE(A): Create an array A
• INSERT(A,X): Insert an element X into an array A in any location
• DELETE(A,X): Delete an element X from an array A
• MODIFY(A,X,Y): modify element X by Y of an array A
• TRAVELS(A): Access all elements of an array A
• MERGE(A,B): Merging elements of A and B into a third array C

Thus by using a one-dimensional array we can perform above operations thus an array acts as an ADT.

Given postfix expression:

AB − C + DEF − + $

Converting it into infix:

 The infix expression of given postfix expression is: (((A-B)+C)$ (D-(E-F)))

Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a previous result.

In order to solve a problem recursively, two conditions must be satisfied. First, the problem must be written in a recursive form, and second, the problem statement must include a stopping condition.

Recursive program to find factorial of a number:

#include<stdio.h>

#include<conio.h> 

void main( )

{

clrscr( );

 int factorial(int);

 int n,f;

 printf("Enter the number: ");

 scanf("%d",&n);

 f=factorial(n);

 printf("Factorial of the %d number is %d",n,f);

 getch();

}

int factorial(int n)

{

  int f;

  if(n==1)

     return 1;

  else

     f=n*factorial(n-1);

     return f;

}

A almost complete binary tree is a binary tree in which every level of the tree is completely filled except the last level. Also, in the last level, nodes should be attached starting from the left-most position.

A binary tree is a almost complete binary tree (of height h , we take root node as 0 ) if and only if :-

• Level 0 to h-1 represent a full binary tree of height h-1
• One or more nodes in level h-1 may have  0, or 1 child nodes

• If F, G are nodes in level h-1, then F has  more child nodes than G if and only if F is to the left of G , i.e. the last level (h) can be missing leaf nodes, however the ones present must be shifted to the left

Example:

Fig: almost complete binary tree

#include<stdio.h>

int main()

{

    int a[10],i,j,temp,min,loc,n;

    printf("\\n Enter the max no.of Elements to Sort: \\n");

    scanf("%d",&n);

    printf("\\n Enter the Elements : \\n");

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

    {

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

    }

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

    {

        min=a[i];

        loc=i;

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

        {

            if (a[j]<min)

            {

                min=a[j];

                loc=j;

            }

        }

        if (loc!=i)

        {

            temp=a[i];

            a[i]=a[loc];

            a[loc]=temp;

        }

    }

    printf("The sorted array is: \\n");

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

    {

        printf("%d\\t",a[i]);

    }

    return 0;

}

Binary search is an extremely efficient search technique that searches the given item in minimum possible comparisons in the already sorted list of given elements. The logic behind the technique is:

1. First find the middle element of the list

2. Compare the mid-element with searched item.

    There are three cases:

      a. If it is a desired element then search is successful.

      b. If it is less than desired item then search only in the first half of the list.

      c. If it is greater than desired item then search in the second half of the list.

Recursive Algorithm:

BinarySearch(A,l,r, key)

{

    if(l= = r)

    {

        if(key = = A[l])

            return l+1;         //index starts from 0

        else

            return 0;

    }

     else

    {

        m = (l + r) /2 ;

        if(key = = A[m])

                return m+1;

        else if (key < A[m])

                return BinarySearch(l, m-1, key) ;

        else

                return BinarySearch(m+1, r, key) ;

    }

}

Example:

Consider an array of data:

 21, 36, 56, 79, 101, 123, 142, 203

Now,

Tracing binary search for above data;

Set L=0, R=7, key=123 (search for 123)

Therefore, search successful and key(123) is at position (Mid+1)=5+1=6.

Efficiency:

From the above algorithm we can say that the running time of the algorithm is

T(n) = T(n/2) + O(1)

        = O(logn)

In the best case output is obtained at one run i.e. O(1) time if the key is at middle.

In the worst case the output is at the end of the array so running time is O(logn) time. In the average case also running time is O(logn).

Hashing is a well-known technique to search any particular element among several elements. It minimizes the number of comparisons while performing the search. 

In hashing, an array data structure called as Hash table is used to store the data items. Hash table is a data structure used for storing and retrieving data very quickly. Insertion of data in the hash table is based on the key value. Hence every entry in the hash table is associated with some key. Using the hash key the required piece of data can be searched in the hash table by few or more key comparisons.

    Fig: Hashing Mechanism

Hash function is a function which is used to put the data in the hash table. Hence one can use the same hash function to retrieve the data from the hash table. Thus hash function is used to implement the hash table. The integer returned by the hash function is called hash key.

In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data. Thus, using hashing insertion and search operations are very fast irrespective of the size of the data. So we need hashing.

Linear Probing

Linear probing  is the  method of handling collision. When collision occurs i.e. when two records demand for the same home bucket in the hash table then collision can be solved by placing the second record linearly down whenever the empty bucket is found. When use linear probing,  the hash table is represented as a one-dimensional array with indices that range from 0 to the desired table size-1. Before inserting any elements into this table, we must initialize the table to represent the situation where all slots are empty. This allows us to detect overflows and collisions when we inset elements into the table. Then using some suitable hash function the element can be inserted into the hash table.

For example:

Consider that following keys are to be inserted in the hash table

131, 4, 8, 7, 21, 5, 31, 61, 9, 29

Initially, we will put the following keys in the hash table.

We will use Division hash function. That means the keys are placed using the formula

H(key) = key % tablesize

H(key) = key % 10

For instance the element 131 can be placed at

H(key) = 131 % 10 = 1

Index 1 will be the home bucket for 131. Continuing in this fashion we will place 4, 8, 7.

Now the next key to be inserted is 21. According to the hash function

H(key)=21%10 = 1

But the index 1 location is already occupied by 131 i.e. collision occurs. To resolve this collision we will linearly move down and at the next empty location we will prob the element. Therefore 21 will be placed at the index 2.

The complexity of an algorithm is a function f (n) which measures the time and space used by an algorithm in terms of input size n. The complexity of an algorithm is a way to classify how efficient an algorithm is, compared to alternative ones.

The process of finding complexity of given algorithm by counting number of steps and number of memory references used by using RAM model is called detailed analysis. For detailed time complexity algorithm we count the number of steps and finally add all steps and calculate their big oh notation. Similarly for detailed analysis of space complexity we count the number of memory references and finally add all steps and find their big oh notation.

E.g.

#include<stdio.h>

int main()

{

    int i, n, fact=1;

    printf("Enter a number to calculate factorial:");

    scanf("%d",&n);

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

            fact = fact*i;

    printf("Factorial of %d=%d", n, fact);

    return 0;

}

Time Complexity:

The declaration statement takes 1 step.

Printf statement takes 1 step.

Scanf statement takes 1 step.

In for loop:

    i=1 takes 1 step

    i<=n takes (n+1) step

    i++ takes n step

    within for loop fact=fact*i takes n step

printf statement takes 1 step

return statement takes 1 step

Total time complexity = 1+1+1+1+n+1+n+n+1+1

           = 3n+7

           = O(n)

Space complexity:

total memory references used = 3 = O(1)

Given array:

16   7   31   2   9   41   -10

Tracing using insertion sort:

Which is the sorted array.

a) Tree Traversal

The tree traversal is a way in which each node in the tree is visited exactly once in a symmetric manner.

The binary tree can be traverse in 3 ways:

1. Pre-order traversal

2. In-order traversal

3. Post-order traversal

1. Pre-order Traversal: In Pre-Order traversal, the root node is visited before left child and right child nodes. In this traversal, the root node is visited first, then its left child and later its right child. This is performed recursively for all nodes in the tree. For e.g.

The preorder traversal output of the given above tree is: A B D H I E C F G

2. In-order Traversal: In In-Order traversal, the root node is visited between left child and right child. In this traversal, the left child node is visited first, then the root node is visited and later we go for visiting right child node. This is performed recursively for all nodes in the tree. For e.g.

The inorder traversal output of the given tree is: H D I B E A F C G

3. Post-order Traversal: In Post-Order traversal, the root node is visited after left child and right child. In this traversal, left child node is visited first, then its right child and then its root node. This is recursively performed until the right most node is visited. For e.g.

The post-order traversal output of the given above tree is: H I D E B F G C A