## 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)**