.png)
Mobiprep has created last-minute notes for all topics of Algorithm to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Algorithm.
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Complexity Classes
Question- 1) What is complexity theory?
Answer: Complexity theory is a central topic in theoretical computer science. It has direct applications to computability theory and uses computation models such as Turing machines to help test complexity. Complexity theory helps computer scientists relate and group problems together into complexity classes. Sometimes, if one problem can be solved, it opens a way to solve other problems in its complexity class. Complexity helps determine the difficulty of a problem, often measured by how much time and space (memory) it takes to solve a particular problem. For example, some problems can be solved in polynomial amounts of time and others take exponential amounts of time, with respect to the input size.
Question- 2) What is Hamiltonian cycle problem?
Answer: In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected).
Question- 3) Explain Relation of P and NP classes.
Answer: Class P If a problem can be solved by a deterministic Turing machine in polynomial time, the problem belongs to the complexity class P. All problems in this class have a solution whose time requirement is a polynom on the input size n. i.e. f(n) is of form akn k +ak−1n k−1 +...+a2n 2 +a1n+a0 where ak, ..., a0 are constant factors (possibly 0). The order of polynom is the largest exponent k such that ak = 0 (if ak = 0, then the polynom is ak−1n k−1+...+a0 and the order is k − 1, unless ak−1 = 0. If ak−1 = 0, too, then the polynom is ak−2n k−2 + ... + a0 etc.).
Class NP contains all computational problems such that the corresponding decision problem can be solved in a polynomial time by a nondeterministic Turing machine.
Question- 4) Explain NP-Completeness.
Answer: NP-complete problems
NP-complete problems are special problems in class NP. I.e. they are a subset of class NP. An problem p is NP-complete, if
p ∈ NP (you can solve it in polynomial time by a non-deterministic Turing machine) and
All other problems in class NP can be reduced to problem p in polynomial time