6. Infix to Postfix Conversion

Algorithm

Get the infix expression as input

Read the character one by one from the infix expression

If the character is an operand, write the character in to the postfix expression directly

If it is an operator, check the precedence of the operator with the top element

  • If the operator of the top element is having lower precedence than the current element, push the symbol into the stack
  • Else, pop the elements from the stack which are having higher precedence than the current element and write it into the postfix expression
  • Push the operator into the stack

Repeat the process until the end of the infix expression

Finally, check the stack, if it is not empty, pop the characters from the stack and write it into the postfix expression and display the result

7. Producer Consumer Problem using array based Circular Queue

Algorithms

Create a queue using an array

Insert the element into the queue using enqueue() function

Delete an item from the queue in the FIFO manner using dequeue() function

Producer can perform the insertion operation into the queue until the queue is full

Consumer can delete the items from the queue in FIFO manner until the queue is empty

8. Tree Traversals

Aim :

To perform In-order, Preorder and Post order traversals in Binary Search Tree

Algorithm:

  • Create the binary search tree

To perform in-order traversals

process the left sub tree

process the root

process the right sub-tree

To perform preorder traversal

process the root node

process the left

process the right

To perform post-order traversal

process the left node

process the right node.

process the root node.

9. Binary Search Tree Implementation

Algorithm

Create a empty binary search tree

Perform the insertion in Binary search tree by

  • Get the value of the node X to be inserted
  • If the tree is empty, insert the node X as the root node of the tree and assign the left child and right child of the root to be NULL
  • Else, compare X with the root. If X is less than the root node, insert it into the left subtree of the root, Otherwise insert it into the right subtree of the root node

Perform the deletion from the search tree by

  • Get the value of the node X to be deleted
  • Check whether the node is present in the search tree or not
  • If it is not, display an error
  • Else, check the position of the node X in the search tree
  • If X is a leaf node, then simply delete by assigning the left and right child of the parent of X to the NULL
  • If X is having either left child or right child, delete it by assigning the left child or right child of the parent of X to be NULL
  • If X is having both left and right child, delete the node X by assigning the right child of the parent of X to be the minimum value of the right subtree of X

Display the lowest and highest value of the search tree using Findmin() and Findmax() function

10. Priority Queues using Heaps

Algorithm

Get the number of items to construct a heap which satisfy the staructure and heap order property

Get the item X to be inserted

Insert X into the last level of heap and compare the node X with the parent up to the root node that satisfies the property of the heap

Delete_min() is used to delete the minimum value of the heap and rearrange the items in the heap that satisfies the heap property

11. Hashing Technique

Algorithm

Create a hash table with size 10

Get the value of X to be inserted into the hash table

  • Apply hash function to the item X to identify the bucket
  • If the bucket is free, insert the item X into that bucket
  • Else, Identify the next free bucket and insert the item X in to that bucket

Get the value of X to be deleted

  • Apply hash function to the item X to identify the bucket
  • If the bucket is free, then display an error
  • Otherwise, delete the item X from the bucket

12. Dijkstra’s Algorithm

Aim

To write a C program to implement Dijkstra’s Algorithm to find the shortest path from the source vrtex to all other vertex

Algorithm

  1. Get the input value for the directed graph
  2. Assign to every node a distance value: set it to zero for our initial node and to infinity for all other nodes.
  3. Mark all nodes as unvisited. Set initial node as current.
  4. For current node, consider all its unvisited neighbors and calculate their tentative distance. For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance, overwrite the distance. All unvisited neighbors are added to an unvisited set.
  5. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.
  6. The next current node will be the node with the lowest distance in the unvisited set.
  7. If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node, considering all nodes in graph) as the next "current node" and continue from step 3.
  8. Display the result