Home > Data Structure EE2204 > Data Structure Algorithm

Data Structure Algorithm

Algorithm for Converting infix to postfix

Push a left parenthesis and its corresponding priority on the stacks

Append a right parenthesis onto the end of the infix expression

While the end of the infix expression has not been found

If the character in the infix expression is a letter or digit

Put it on the end of the postfix expression

Else if the character in the infix expression is a left parenthesis

Push it and its corresponding priority on the stacks

Else if the character in the infix expression is an operator

Find the priority of the current character in the infix expression

Find the priority of the top item on the character stack

While priority of top item on char stack >= priority of current char

Pop the character and integer stacks

Put the popped character on the end of the postfix expression

Find the priority of the new top item on the character stack

Endwhile

Push the current character and its priority on the stacks

Else if the character in the infix expression is a right parenthesis

Find the top character on the character stack

While the top character is not a left parenthesis

Pop the character and integer stacks

Put the popped character on the end of the postfix expression

Find the new top character on the character stack

Endwhile

Pop the character and integer stacks to remove the left parenthesis

Endif

Endwhile

Algorithm of BST

BST Property

• All elements stored in the left subtree of a node whose value is K have values less than K. All elements stored in the right subtree of a node whose value is K have values greater than or equal to K.

• That is, a node’s left child must have a key less than its parent, and a node’s right child must have a key greater or equal to its parent

Operations on BST ADT

• Create a BST

• Insert an element

• Remove an element

• Find an element

• Clear (remove all elements)

• Display all elements in a sorted order

For Display

BST – Inorder traversal

• Visit the left subtree, then the node, then the right subtree.

Algorithm:

– If there is a left child visit it

– Visit the node itself

– If there is a right child visit it

Algorithm for print function:

• If there is a left child display it

• display the node itself

• If there is a right child display it

BST – Clear the tree

What traversal should we use to clear the tree?

BST – Postorder traversal

Visit each node after visiting its children.

Algorithm:

– If there is a left child visit it

– If there is a right child visit it

– Visit the node itself

Algorithm for clear function:

• If there is a left child delete it

• If there is a right child delete it

• Delete the node itself

BST – find

What traversal should we use to find a value in a the tree?

Algorithm

• If value we are looking for = key of current node -> we have to found it

• If value we are looking for we have to check left subtree

• If value we are looking for > key of current node ->we have to check right subtree

BST – Insert Algorithm

• If value we want to insert We just delete the node.

• Node to be deleted has only one child-> Replace the node with its child and make the parent of the

deleted node to be a parent of the child of the deleted node

• Node to be deleted has two children

• The property of the BST must be maintained

Steps:

1. Find minimum value of right subtree

2. Delete minimum node of right subtree but keep its value

3. Replace the value of the node to be deleted by the minimum value whose node was deleted earlier.

AIM:-

To implement tree traversals

ALGORITHM:-

Step 1: Start the process.

Step 2: Initialize and declare variables.

Step 3: Enter the choice. Inorder / Preorder / Postorder.

Step 4: If choice is  Inorder then

a)       Traverse the left subtree in inorder.

b)       Process the root node.

c)       Traverse the right subtree in inorder.

Step 5: If choice is Preorder then

a)       Process the root node.

b)       Traverse the left subtree in preorder.

c)       Traverse the right subtree in preorder.

Step 6: If choice is postorder then

a)       Traverse the left subtree in postorder.

b)       Traverse the right subtree in postorder.

c)       Process the root node.

Step7: Print the Inorder / Preorder / Postorder traversal.

Step 8: Stop the process.

AIM:-

To implement priority queue using heaps.

ALGORITHM:-

 

function heapSort(a, count) is

input: an unordered array a of length count

(first place a in max-heap order)

heapify(a, count)

end := count – 1

while end > 0 do

(swap the root(maximum value) of the heap with the last element of the heap)

swap(a[end], a[0])

(decrease the size of the heap by one so that the previous max value will

stay in its proper placement)

end := end – 1

(put the heap back in max-heap order)

siftDown(a, 0, end)

function heapify(a,count) is

(start is assigned the index in a of the last parent node)

start := (count – 2) / 2

while start ≥ 0 do

(sift down the node at index start to the proper place such that all nodes below

the start index are in heap order)

siftDown(a, start, count-1)

start := start – 1

(after sifting down the root all nodes/elements are in heap order)

function siftDown(a, start, end) is

input: end represents the limit of how far down the heap

to sift.

root := start

while root * 2 + 1 ≤ end do (While the root has at least one child)

child := root * 2 + 1           (root*2+1 points to the left child)

(If the child has a sibling and the child’s value is less than its sibling’s…)

if child + 1 ≤ end and a[child] < a[child + 1] then

child := child + 1           (… then point to the right child instead)

if a[root] < a[child] then (out of max-heap order)

swap(a[root], a[child])

root := child                (repeat to continue sifting down the child now)

else

return

AIM:-

To perform topological sort on a directed graph to decide if it is acyclic.

ALGORITHM:-

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
output error message (graph has at least one cycle)
else
output message (proposed topologically sorted order: L)

AIM:-

To implement Dijkstra’s algorithm using priority queues.

ALGORITHM:-

  1. Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
  2. Mark all nodes as unvisited. Set initial node as current.
  3. For current node, consider all its unvisited neighbours and calculate their distance (from the initial node). 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 (infinity in the beginning, zero for the initial node), overwrite the distance.
  4. When we are done considering all neighbours 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.
  5. Set the unvisited node with the smallest distance (from the initial node) as the next “current node” and continue from step 3 .

1  function Dijkstra(Graph, source):

2      for each vertex v in Graph:           // Initializations

3          dist[v] := infinity               // Unknown distance function from source to v

4          previous[v] := undefined          // Previous node in optimal path from source

5      dist

[/source]

:= 0              // Distance from source to source

6      Q := the set of all nodes in Graph

// All nodes in the graph are unoptimized – thus are in Q

7      while Q is not empty:                 // The main loop

8          u := vertex in Q with smallest dist[]

9          if dist[u] = infinity:

10              break                         // all remaining vertices are inaccessible

11          remove u from Q

12          for each neighbor v of u:         // where v has not yet been removed from Q.

13              alt := dist[u] + dist_between(u, v)

14              if alt < dist[v]:             // Relax (u,v,a)

15                  dist[v] := alt

16                  previous[v] := u

17      return previous[]

AIM:-

To implement backtracking algorithm for Knapsack problem.

ALGORITHM:-

function backtracking (current depth)

if solution is valid

return / print the solution

else

for each element from A[] source array

let X[current depth] ß element

if possible candidate (current depth + 1)

backtracking (current depth + 1)

end if

end for

end if

end function

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: