Data Structures and Algorithms 2070

Given Infix expression.

A + (((B-C) * (D-E) + F)/G) $ (H-I)

Converting it to postfix:

 Therefore, postfix expression of given infix expression is: ABC-DE-*F+G/HI-$+

Now, 

Evaluating the postfix expression for the given values:

A = 6, B = 2, C = 4, D = 3, E = 8, F = 2, G = 3, H = 5, I = 1

ABC-DE-*F+G/HI-$+

6 2 4 - 3 8 - * 2  +3 / 5 1 - $ +

Doubly linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.

In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field. Every node in a double linked list contains three fields and they are shown in the following figure...

Here, 'link1' field is used to store the address of the previous node in the sequence, 'link2' field is used to store the address of the next node in the sequence and 'data' field is used to store the actual value of that node.

Example:

Binary Search Tree

A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

• All keys in the left sub-tree of the root are smaller than the key in the root node
• All keys in the right sub-tree of the root are greater than the key in the root node
•  The left and right sub-trees of the root are again binary search trees

Example:

Given the following sequence of numbers,

        14, 4, 15, 3, 9, 14, 18

The following binary search tree can be constructed:

Algorithm to insert node in non-empty BST

Create a Node with given value and set its left and right to NULL.

insert(struct bnode *root, int item)

{

    if(item < root->info)

         root->left = insert(root->left, item);

    else

         root->right = insert(root->right, item);

    return root;

}

E.g.

Given data

10, 20, 30, 25, 27, 7, 4, 23, 26, 21

Binary Search Tree (BST) for given data is given below:

C function to insert an item circular queue in array implementation:

void enQueue(int value)

{

   if((front == 0 && rear == SIZE - 1) || (front == rear+1))

      printf("\\nCircular Queue is Full! Insertion not possible!!!\\n");

   else{

      if(rear == SIZE-1 && front != 0)

         rear = -1;

      cQueue[++rear] = value;

      printf("\\nInsertion Success!!!\\n");

      if(front == -1)

         front = 0;

   }

}

An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer

Algorithms are used to convert our problem solution into step by step statements. These statements can be converted into computer programming instructions which forms a program. This program is executed by computer to produce solution. Here, program takes required data as input, processes data according to the program instructions and finally produces result as shown in the following picture

The analysis of algorithms is the process of finding the computational complexity of algorithms – the amount of time, storage, or other resources needed to execute them.

Big  Oh notation

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

Tower of Hanoi (TOH) is a mathematical puzzle which consists of three pegs named as origin, intermediate and destination and more than one disks. These disks are of different sizes and the smaller one sits over the larger one.

In this problem we transfer all disks from origin peg to destination peg using intermediate peg for temporary storage and move only one disk at a time.

Algorithm for TOH problem:

Let’s consider move ‘n’ disks from source peg (A) to destination peg (C), using intermediate peg (B) as auxiliary.

1. Assign three pegs A, B & C

2. If n==1

Move the single disk from A to C and stop.

3. If n>1

a) Move the top (n-1) disks from A to B.

b) Move the remaining disks from A to C

c) Move the (n-1) disks from B to C

4. Terminate

Recursive solution:

void TOH(int n, char A, char B, char C)

{

  if(n>0)

 {

   TOH(n-1, A, C, B);

   Printf(“Move disk %d from %c to%c\\n”, n, A, B);

   TOH(n-1, C, B, A);

 }

}

Selection sort algorithm sorts the elements in an array by finding the minimum element in each pass from unsorted part and keeps it in the beginning. This sorting technique maintains two sub arrays, one sub array which is already sorted and the other one which is unsorted. In each iteration the minimum element (ascending order) is picked from unsorted array and moved to sorted sub array.

Given data:

42, 23, 74, 11, 65, 58, 94, 86

Tracing using selection sort;

Which is the sorted array.

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.

Collision

The situation in which the hash function returns the same hash key for more than one record is called collision. For e.g.

Consider a hash function:

H(key) = recordkey%10 having the hash table size of 10

The record keys to be placed are: 131, 44, 43, 78, 19, 36, 57 and 77

131%10= 1

44%10=4

43%10=3

78%10=8

19%10=9

36%10=6

57%10=7

77%10=7

Now if we try to place 77 in the hash table then we get the hash key to be 7 and at index 7 already the record key 57 is placed. This situation is called collision. 

Collision resolution techniques

If collision occurs then it should be handled by applying some techniques. Such a technique is called collision handling technique. Some collision resolution techniques are:

    1.Chaining

    2.Open addressing (linear probing)

    3.Quadratic probing

    4.Double hashing

    5.Rehashing

Chaining:

In collision handling method chaining is a concept which introduces an additional field with data i.e. chain. A separate chain table is maintained for colliding data. When collision occurs then a linked list(chain) is maintained at the key. For e.g.

Consider the keys to be placed in their hash key are 131, 3, 4, 21, 61, 7, 97, 8, 9 then we will apply a hash function as

H(key) = key % D  Where D is the size of table. The hash table will be:

Here D = 10

A chain is maintained for colliding elements. for instance 131 has a home bucket (key) 1. similarly key 21 and 61 demand for home bucket 1. Hence a chain is maintained at index 1.

Weighted Graph

A weighted graph is a graph G, in which each edge, e, is assigned a non-negative real number, w(e), called the weight of e. For e.g.

Depth First Traversal (DFS)

Depth-first traversal (DFS) is an algorithm for traversing graph data structures. 

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

Given,

Now sort these characters according to their frequencies in non-decreasing order.

The tree constructed for the given characters is shown below:

Now from variable length code we get following code sequence.

The process of allocating memory at runtime is known as dynamic memory allocation. Library routines known as memory management functions are used for allocating and freeing memory during execution of a program. These functions are defined in stdlib.h header file.

A 2D array can be dynamically allocated in C using a single pointer. This means that a memory block of size row*column*dataTypeSize is allocated using malloc and pointer arithmetic can be used to access the matrix elements.

A program that demonstrates this is given as follows:

#include <stdio.h>
#include <stdlib.h> 
int main() {
   int row = 2, col = 3;
   int *arr = (int *)malloc(row * col * sizeof(int)); 
   int i, j;
   for (i = 0; i < row; i++)
      for (j = 0; j < col; j++)
         *(arr + i*col + j) = i + j;    
   printf("The matrix elements are:\\n");
   for (i = 0; i < row; i++) {
      for (j = 0; j < col; j++) {
         printf("%d ", *(arr + i*col + j)); 
      }
      printf("\\n");
   }
   free(arr); 
   return 0;
}

a) Binary Searching

Algorithm for Binary Searching:

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) ;

    }

}

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).

b) Quick Sort

Algorithm for Quick Sort:

QuickSort(A, l, r)

{

    if(l<r)

    {

        p = Partition(A,l,r);

        QuickSort(A,l,p-1);

        QuickSort(A,p+1,r);

    }

}

Partition(A, l, r)

{

    x =l; y =r ; p = A[l];

    while(x<y)

    {

       do {

                x++;

         }while(A[x] <= p);

    do {

                y--;

         } while(A[y] >=p);

    if(x<y)

        swap(A[x],A[y]);

}

A[l] = A[y];

A[y] = p;

return y;     //return position of pivot

}

Efficiency:

Time Complexity:

Best Case: T(n) = O(nlogn)

Worst Case: T(n) = O(n2)

Average Case: T(n) = O(nlogn)

a) Queue in Circular Linked List

By using a circular list, a queue may be specified by a single pointer q to that list. node(q) is the rear of the queue and the following node is its front.

Insertion function:

void insert(int item)

{

    NodeType *nnode;

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

    nnode->info=item;

    if(pq==NULL)

          pq=nnode;

    else

    {

        nnode->next=pq->next;

        pq->next=nnode;

        pq=nnode;

    }

}

Deletion function:

void delet(int item)

{

    NodeType *temp;

    if(pq==NULL)

    {

        printf(“void deletion\\n”);

        exit(1);

    }

    else if(pq->next==pq)

    {

        printf(“poped item=%d”, pq->info);

        pq=NULL;

    }

    else

    {

        temp=pq->next;

        pq->next=temp->next;

        printf(“poped item=%d”, temp->info);

        free(temp);

    }

}

b) ADT

Abstract data types are a set of data values and associated operations that are precisely independent of any particular implementation. Generally the associated operations are abstract methods. E.g. stack, queue etc.

c) MST (Minimum Cost Spanning Tree) of a graph

A spanning tree is a subset of Graph G, which has all the vertices of G with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.

In a weighted graph, a minimum spanning tree (MST) is a spanning tree that has minimum weight than all other spanning trees of the same graph.

There are three different algorithms to construct the minimum spanning tree:

• Prim’s algorithm: Grows the tree in stages. Selects an edge with lowest cost that can be added to the tree without forming cycle.
• Kruskal’s algorithm: In each stage select the edge in non-decreasing order of cost.
• Sollin’s algorithm: Select several edges at each stage.