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.
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
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
1. Two way decision making
2. Number of comparison can be reduced
3. Traversing binary tree
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
Example for Infix to Postfix Conversion
Example : The Given Infix expression is ((A+B)/ C)