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]


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)
               Vertex cover problem  








Advanced Data Structures and Algorithms


Advanced Data Structures and Algorithms



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.


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


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/