Algorithms Notes

mobiprep (6).png

Algorithm Basics

mobiprep (6).png

Divide And Conquer

mobiprep (6).png

Greedy Algorithm

mobiprep (6).png

Dynamic Programming

mobiprep (6).png

Shortest Path

mobiprep (6).png

Backtracking

mobiprep (6).png

Minimum Spanning Tree

mobiprep (6).png

Maximum Flow

mobiprep (6).png

Complexity Classes

Heading

Q

1

What is complexity theory?

LRM_EXPORT_207556595493866_20190724_1939

Ans

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.

LRM_EXPORT_207556595493866_20190724_1939

Q

2

What is Hamiltonian cycle problem:-

LRM_EXPORT_207556595493866_20190724_1939

Ans

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)

LRM_EXPORT_207556595493866_20190724_1939

Q

3

Explain Relation of P and NP classes

LRM_EXPORT_207556595493866_20190724_1939

Ans

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 contant 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.

LRM_EXPORT_207556595493866_20190724_1939

Q

4

Explain NP-Completeness

LRM_EXPORT_207556595493866_20190724_1939

Ans

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

1. p ∈ NP (you can solve it in polynomial time by a non-deterministic Turing machine) and

2. All other problems in class NP can be reduced to problem p in polynomial time.

LRM_EXPORT_207556595493866_20190724_1939