Home

Stack

Stack

Stack is an ordered collection of items into which new items may be inserted or deleted at one end of the stack called top

Stack follow LIFO [Last In First Out ]. That is the element to be deleted first is the one which is  inserted last. Stack is also called a push down list

Operations on Stack

       1. PUSH
                Inserting an element on the top of the stack

        2. POP
                  Remove the top element

        Empty (S)  : check whether stack is empty or not
 
        Stacktop(S)   : returns the top element

 


Convert Infix into Prefix and Postfix

Infix                   Prefix                        Postfix

( A+B) * C              * + ABC                          AB+C*

  A+ (B*C)               +A*BC                            ABC*+

(A+B) / ( C- D)          / + AB -  CD                AB+CD - /

A-B / ( C*D  $ E )      - A / B*C $ D E            ABCDE$ * / -       

P NP NP Complete

Analysis of algorithm and computational complexity : P, NP, NP Complete

 

Algorithm :  A well defined computational procedure that takes some value / set of values as input , and produces some value / set of values as output.

 

Class P :  P is a class of language that are decidable in polynomial time on a deterministic single tape turing machine,

Example:   Kruskal's algorithm

                 Path problem  - in a graph to determine whether a directed path exist from s to t.

                 Relative prime [REL prime]

                 CFL   

Class NP : Polynomial time algorithm to solve them are not known to exist till now.

Example:  Hamiltonian path

                Composite problem (check for composite )

                Traveling salesman problem.

                CLIQUE problem

                The subset sum problem. 

 

NP Complete :If a polynomial time algorithm exist for an NP problem , then all problems in NP would be polynomial time solvable. These problems are called NP complete.

Example: Satisfiability Problem (SAT)
                SAT
               Vertex cover problem  

 

 

 

 

 

 

 

Advanced Data Structures and Algorithms

 

Advanced Data Structures and Algorithms

Algorithm:

 

Algorithm is a finite sequence of abstract steps which will halt on all inputs.An algorithm is said to be correct if,for every input instances,it halt with the correct output. An incorrect algorithm might not halt at all on some input instances or it might halt with an incorrect answer.

 

Data Structures: Data structure is an abstract data type (ADT) which allows to store and organize data to facilitate access and modifications.


Example : Stack , Queue , Tree , Search Tree etc

Behavior of an algorithm


The behavior of an algorithm is characterized by the following three parameters. 

                           Time, Space and the Communication Complexity.

Time includes  Creation time , Query Response time, update time , Running time

Creation time: Data structure creation time(or setup time) of the data structure being used.

Query Response time : Example: Is there a path from a vertex Vi to another Vertex Vj in a given graph? The time it require to respond to this query is called response time.

Update Time: For example time required to destroy a data structure.

Running Time: Total time require to execute the algorithm from the first statement to termination.

 


Note
-------
In  this tutorial we will cover advanced concepts in data structures and  we will do analysis of algorithms in terms of running time.

Prerequisites:

----------------
Knowledge of basic data structures. Basic knowledge of random variables, expectation, and  combinatorics.

Applications of Binary Tree

Applications of Binary Tree

   1. Two way decision making

   2. Number of comparison can be reduced

   3. Traversing binary tree

Infix to Postfix Conversion

Infix to Postfix Conversion

 

Algorithm for Infix to Postfix Conversion

1.  scan infix expression from left to right

2.  if an operand is encountered add to P

3.  if an operator is found

         i) repeatedly pop the operator from stack which are having higher precedence than the operator found

         ii) add the new operator to stack

4.  if a right parenthesis found
           i) repeatedly pop the stack and add the poped operators to the expression until a left parenthesis is found.
           ii) remove the left parenthesis

5.   stop    

 Example for Infix to Postfix Conversion

Example : The Given Infix expression is ((A+B)/ C)


  Symbols Scanned  Stack              Postfix form P


          (                              (

          

           (                             ( (

      

           A                            ( (                      A


           +                             ( ( +                   A


           B                             ( ( +                   AB


           )                                ( (                     AB+


           /                                 ( (  /                  AB+


          C                                 ( (  /                 AB+C           


          )                                   ( (                    AB+C/