UNIT V
1) Define tractable and intractable problems
Problems that can be solved in polynomial time are called tractable problems, problems that cannot be solved in polynomial time are called intractable problems.
2) Explain the theory of computational complexity
A problem's intractability remains the same for all principal models of computations and all reasonable input encoding schemes for the problem under consideration
3)Explain class P problems
Class P is a class of decision problems that can be solved in polynomial time by(deterministic) algorithms. This class of problems is called polynomial.
4)Explain undecidable problems
If the decision problem cannot be solved in polynomial time, and if the decision problems cannot be solved at all by any algorithm. Such problems are called Undecidable.
5) Explain the halting problem
Given a computer program and an input to it,determine whether the program will halt on that input or continue working indefinitely on it.
6) Explain class NP problems
Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms.Most decision problems are in NP. First of all, this class includes all the problems in P. This class of problems is called Nondeterministic polynomial.
7)Explain NP-complete problems
A decision problem d is said to be NP-complete if
1) it belongs to class NP
2) every problem in NP is polynomially reducible to D.
8)When a decision problem is said to be polynomially reducible
A decision problem Dl is said to be polynomially reducible to a decision problem D2 if there exists a function t that transforms instances of Dl to instances ofD2 such that
i) t maps all yes instances of d1 to yes instances odf d2 and all no instances of dl to no instances ofd2
ii) t is computable by a polynomial time algorithm
9) Define a Heuristic
A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved assertion.
Ex: Going to the nearest unvisited city in the traveling salesman problem is a good illustration for Heuristic
10) Explain NP-Hard problems
The notion of an NP-hard problem can be defined more formally by extending the notion of polynomial reducability to problems that are not necessary in class NP including optimization problems.
11)Define Traversals.
When the search necessarilyinvolves the examination of every vertex in the object being searched it is called a traversal.
12)List out the techniques for traversals in graph.
Breadth first search
Depth first search
13)What is articulation point.
A vertex v in a connected graph G is an articulation point if and only if the deletion of vertex v together with all edged incident to v disconnects the graph in to two or more nonempty components.
No comments:
Post a Comment