lOMoARcPSD|41001828

Daa UNIT5 notes

Design and Analysis of Algorithm (Symbiosis International University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

Downloaded by Thanush S ([email protected])
 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

UNIT – V

Deterministic and non-deterministic algorithms

Deterministic: The algorithm in which every operation is uniquely defined is
called deterministic algorithm.
Non-Deterministic: The algorithm in which the operations are not uniquely
defined but are limited to specific set of possibilities for every operation, such
an algorithm is called non-deterministic algorithm.
The non-deterministic algorithms use the following functions:
1. Choice: Arbitrarily chooses one of the element from given set.
2. Failure: Indicates an unsuccessful completion
3. Success: Indicates a successful completion

A non-deterministic algorithm terminates unsuccessfully if and only if there

exists no set of choices leading to a success signal. Whenever, there is a set of
choices that leads to a successful completion, then one such set of choices is
selected and the algorithm terminates successfully.
In case the successful completion is not possible, then the complexity is O(1).
In case of successful signal completion then the time required is the minimum
number of steps needed to reach a successful completion of O(n) where n is
the number of inputs.
The problems that are solved in polynomial time are called tractable problems
and the problems that require super polynomial time are called non-tractable
problems. All deterministic polynomial time algorithms are tractable and the
non-deterministic polynomials are intractable.

A nondeterministic algorithm is considered as a superset for deterministic

algorithm i.e., the deterministic algorithms are a special case of
nondeterministic algorithms.

NP

Example1: A non-deterministic algorithm for searching an element X in the

given set of elements A[1:n] in the time complexity O(1).

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

Algorithm Search(A,x)
{
i<-choice(1:n)
if(A(i)=X) then
{
Write(i);
Success();
}
else
{
Write(0);
Failure();
}
}

Satisfiability Problem:
The satisfiability is a boolean formula that can be constructed using the
following literals and operations.
1. A literal is either a variable or its negation of the variable.
2. The literals are connected with operators Ç, Æ͢, ⇒ , ⇔
3. Parenthesis

The satisfiability problem is to determine whether a Boolean formula is true

for some assignment of truth values to the variables. In general, formulas are
expressed in Conjunctive Normal Form (CNF).

A Boolean formula is in conjunctive normal form iff it is represented by

( xi ( xj ( xk1 ) ' ( xi ( xj1 ( xk )

A Boolean formula is in 3CNF if each clause has exactly 3 distinct literals.

Example:

The non-deterministic algorithm that terminates successfully iff a given

formula E(x1,x2,x3) is satisfiable.

Reducability:
A problem Q1 can be reduced to Q2 if any instance of Q1 can be easily
rephrased as an instance of Q2. If the solution to the problem Q2 provides a
solution to the problem Q1, then these are said to be reducable problems.

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

Let L1 and L2 are the two problems. L1 is reduced to L2 iff there is a way to
solve L1 by a deterministic polynomial time algorithm using a deterministic
algorithm that solves L2 in polynomial time and is denoted by L1α L2.

If we have a polynomial time algorithm for L2 then we can solve L1 in

polynomial time. Two problems L1 and L2 are said to be polynomially
equivalent iff L1α L2 and L2 α L1.

Example: Let P1 be the problem of selection and P2 be the problem of sorting.

Let the input have n numbers. If the numbers are sorted in array A[ ] the ith
smallest element of the input can be obtained as A[i]. Thus P1 reduces to P2
in O(1) time.

Decision Problem:
Any problem for which the answer is either yes or no is called decision
problem. The algorithm for decision problem is called decision algorithm.
Example: Max clique problem, sum of subsets problem.

Optimization Problem: Any problem that involves the identification of an

optimal value (maximum or minimum) is called optimization problem.
Example: Knapsack problem, travelling salesperson problem.
In decision problem, the output statement is implicit and no explicit
statements are permitted.
The output from a decision problem is uniquely defined by the input
parameters and algorithm specification.

Many optimization problems can be reduced by decision problems with the

property that a decision problem can be solved in polynomial time iff the
corresponding optimization problem can be solved in polynomial time. If the
decision problem cannot be solved in polynomial time then the optimization
problem cannot be solved in polynomial time.

NP HARD AND NP COMPLETE

Polynomial Time algorithms
Problems whose solutions times are bounded by polynomials of small degree
are called polynomial time algorithms

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

Example: Linear search, quick sort, all pairs shortest path etc.
Non- Polynomial time algorithms
Problems whose solutions times are bounded by non-polynomials are called
non-polynomial time algorithms
Examples: Travelling salesman problem, 0/1 knapsack problem etc

It is impossible to develop the algorithms whose time complexity is

polynomial for non-polynomial time problems, because the computing times
of non-polynomial are greater than polynomial. A problem that can be solved
in polynomial time in one model can also be solved in polynomial time.
NP-Hard and NP-Complete Problem:
Let P denote the set of all decision problems solvable by deterministic
algorithm in polynomial time. NP denotes set of decision problems solvable
by nondeterministic algorithms in polynomial time. Since, deterministic
algorithms are a special case of nondeterministic algorithms, P ⊆ NP. The
nondeterministic polynomial time problems can be classified into two classes.
They are
1. NP Hard and
2. NP Complete

NP-Hard: A problem L is NP-Hard iff satisfiability reduces to L i.e., any

nondeterministic polynomial time problem is satisfiable and reducable then
the problem is said to be NP-Hard.
Example: Halting Problem, Flow shop scheduling problem

NP-Complete: A problem L is NP-Complete iff L is NP-Hard and L belongs

to NP (nondeterministic polynomial).

A problem that is NP-Complete has the property that it can be solved in

polynomial time iff all other NP-Complete problems can also be solved in
polynomial time. (NP=P)

If an NP-hard problem can be solved in polynomial time, then all NP-

complete problems can be solved in polynomial time. All NP-Complete
problems are NP-hard, but some NP-hard problems are not known to be NP-
Complete.
Normally the decision problems are NP-complete but the optimization
problems are NP-Hard.

However if problem L1 is a decision problem and L2 is an optimization

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

problem, then it is possible that L1α L2.

Example: Knapsack decision problem can be reduced to knapsack

optimization problem.

There are some NP-hard problems that are not NP-Complete.

Relationship between P,NP,NP-hard, NP-Complete

Let P, NP, NP-hard, NP-Complete are the sets of all possible decision
problems that are solvable in polynomial time by using deterministic
algorithms, non-deterministic algorithms, NP-Hard and NP-complete
respectively. Then the relationship between P, NP, NP-hard, NP-Complete
can be expressed using Venn diagram as:

Problem conversion
A decision problem D1 can be converted into a decision problem D2 if there
is an algorithm which takes as input an arbitrary instance I1 of D1 and delivers
as output an instance I2 of D2such that I2 is a positive instance of
D2 if and only if I1 is a positive instance of D1. If D1 can be converted into
D2, and we have an algorithm which solves D2, then we thereby have an
algorithm which solves D1. To solve an instance I of D1, we first use the

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

conversion algorithm to generate an instance I0 of D2, and then use the

algorithm for solving D2 to determine whether or not I0 is a positive instance
of D2. If it is, then we know that I is a positive instance of D1, and if it is not,
then we know that I is a negative instance of D1. Either way, we have solved
D1 for that instance. Moreover, in this case, we can say that the computational
complexity of D1 is at most the sum of the computational complexities of D2
and the conversion algorithm. If the conversion algorithm has polynomial
complexity, we say that D1 is at most polynomially harder than D2. It means
that the amount of computational work we have to do to solve D1, over and
above whatever is required to solve D2, is polynomial in the size of the
problem instance. In such a case the conversion algorithm provides us with a
feasible way of solving D1, given that we know how to solve D2.
Given a problem X, prove it is in NP-Complete.
1. Prove X is in NP.
2. Select problem Y that is known to be in NP-Complete.
3. Define a polynomial time reduction from Y to X.
4. Prove that given an instance of Y, Y has a solution iff X has a
solution.

Cook’s theorem

Cook’s Theorem implies that any NP problem is at most polynomially harder

than SAT. This means that if we find a way of solving SAT in polynomial
time, we will then be in a position to solve any NP problem in polynomial
time. This would have huge practical repercussions, since many frequently
encountered problems which are so far believed to be intractable are NP. This
special property of SAT is called NP-completeness. A decision problem is
NP-complete if it has the property that any NP problem can be converted into
it in polynomial time. SAT was the first NP-complete problem to be
recognized as such (the theory of NP-completeness having come into
existence with the proof of Cook’s Theorem), but it is by no means the only
one. There are now literally thousands of problems, cropping up in many
different areas of computing, which have been proved to be NP-complete.
In order to prove that an NP problem is NP-complete, all that is needed is to
show that SAT can be converted into it in polynomial time. The reason for
this is that the sequential composition of two polynomial-time algorithms is
itself a polynomial-time algorithm, since the sum of two polynomials is itself
a polynomial.
Suppose SAT can be converted to problem D in polynomial time. Now take
any NP problem D0. We know we can convert it into SAT in polynomial time,

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

and we know we can convert SAT into D in polynomial time. The result of
these two conversions is a polynomial-time conversion of D0 into
D. since D0 was an arbitrary NP problem, it follows that D is NP-complete

NP-Hard Graph Problems:

The strategy adopted to show that a problem L2 is NP-hard is:
1. Pick a problem L1, already known to be NP-Hard.
2. Show how to obtain the solution to instance I of L1
3. Conclude from step(2) that L1αL2
4. Conclude from steps (1) and (3) that L2 is NP-hard.

Clique Decision problem:

Let G be a non-directed graph consisting of a set of vertices V and set of edges
E. A maximal complete sub graph of a graph G is a clique. The size of the
clique is the number of vertices in it. The max clique problem is an
optimization problem that has to determine whether graph has a clique of size
atleast k for some integer k.

The brute force algorithm finds a 4-clique in this 7-vertex graph (the complement of the 7-
vertex path graph) by systematically checking all C(7,4) = 35 4-vertex subgraphs for
completeness.

The clique decision problem is NP-complete. This problem was also mentioned in Stephen
Cook's paper introducing the theory of NP-complete problems. Because of the hardness of
the decision problem, the problem of finding a maximum clique is also NP-hard. If one

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

could solve it, one could also solve the decision problem, by comparing the size of the
maximum clique to the size parameter given as input in the decision problem.

Karp's NP-completeness proof is a many-one reduction from the Boolean satisfiability

problem. It describes how to translate Boolean formulas in conjunctive normal form (CNF)
into equivalent instances of the maximum clique problem Satisfiability, in turn, was proved
NP-complete in the Cook–Levin theorem. From a given CNF formula, Karp forms a graph
that has a vertex for every pair (v,c), where v is a variable or its negation and c is a clause
in the formula that contains v. Two of these vertices are connected by an edge if they
represent compatible variable assignments for different clauses. That is, there is an edge
from (v,c) to (u,d) whenever c ≠ d and u and v are not each other's negations. If k denotes
the number of clauses in the CNF formula, then the k-vertex cliques in this graph represent
consistent ways of assigning truth values to some of its variables in order to satisfy the
formula. Therefore, the formula is satisfiable if and only if a k-vertex clique exists.

Some NP-complete problems (such as the travelling salesman problem in planar graphs)
may be solved in time that is exponential in a sublinear function of the input size parameter
n, significantly faster than a brute-force search. However, it is unlikely that such a
subexponential time bound is possible for the clique problem in arbitrary graphs, as it
would imply similarly subexponential bounds for many other standard NP-complete
problems.

The 3-CNF Satisfiability instance (x ( x ( y) ' (~x ( ~y ( ~y) ' (~x ( y ( y) reduced to
Clique. The green vertices form a 3-clique and correspond to a satisfying assignment.

Node Cover Problem:

Let G(V,E) be a undirected graph. A set S which is a subset of V is a node cover if all S.
The size of node cover is the edges in E are incident to atleast one vertex in S. The size of
node cover is the number of vertices in it. The node cover decision problem is to find
minimum size vertex cover in the given graph.

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

Clique decision problem α to node cover decision problem:

Let G be a non-directed graph consisting of set of vertices V and set of edges
E.
Let G1 be the complement of a graph G such that G 1 has node cover of size
atmost n-k iff G has a clique of size atleast k. The graph G 1 is given by G1-
(V,E1) where E1 ={(u,v)| uϵV,vϵV and (u,v) ∉ E}
We have to show that G has a clique of size atleast k iff G 1 has a node cover
of size atmost n-k.
Let C be any clique of G. Since there are no edges in E1 connecting vertices
in C, the remaining n-C vertices in G1 , must cover all edges in E1. Similarly
if S is node cover of G1, then V-S must form a complete subgraph in G.
Since G1 can be obtained from G in polynomial time, clique decision problem
can be solved in polynomial deterministic time then we have polynomial
deterministic time for node cover decision problem.

ExampleConsider the following graph (which has a clique of size 4 as shown

in red)

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

We first construct the complement graph G̅ giving

Clearly a vertex cover for G̅ is {1,6} (shown in blue) which has size 6 - 4 =
2.

Thus if we could solve vertex cover in polynomial time we could solve

clique in polynomial time (and by extension any NP problem in polynomial
time).

NP-Hard Code Generation Problems: Given an expression tree and a

machine architecture, generate a set of instructions that evaluate the tree

– Initially, consider only trees (no common subexpressions)

– Interested in the quality of the program
– Interested in the running time of the algorithm

10

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

• Nodes represent
– Operators (including assignment)
– Operands (memory, registers, constants)
• No flow of control operations

A B C

In fact, we want the tree to represent where the operands are found

MEM MEM
(A)
(B)

load B,r1
load C,r2
add r1,r2,r1
store A,r1

• A program is a sequence of instructions

• A program computes an expression tree if it transforms the tree
according to the desired goal
– Compute the tree into a register
– Compute the tree into memory

11

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

– Compute the tree for its side-effects

• Condition codes
• Assignments

Code generation with common subexpressions:

A directed acyclic graph (DAG!) is a directed graph that contains no cycles. A rooted
tree is a special kind of DAG and a DAG is a special kind of directed graph. For example,
a DAG may be used to represent common subexpressions in an optimising compiler.

+ +
. . . .
. . . .
* () *<---| ()
. . . . . . | . .
. . . . . . | . |
a b f * a b | f |
. . ^ v
. . | |
a b |--<----

Tree DAG

expression: a*b+f(a*b)

Example of Common Subexpression.

The common subexpression a*b need only be compiled once but its value can be used
twice.

12

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

Example of DAG Representation

• t1:= 4*i
• t2:= a[t1]
• t3:= 4*i
• t4:= b[t3]
• t5:= t2 * t4
• t6:= prod + t5
• prod:= t6
• t := i + 1

13

Downloaded by Thanush S ([email protected])

 lOMoARcPSD|41001828

Design and Analysis of Algorithm P.Amba Bhavani, Asst. Professor, IT Dept.

+
t5
prod * (1)
t2 t4
[] [] <=
t1, t3
* t7, i
a b + 20
4 i0 1

Corresponding DAG

Practice Questions:
1. What is Decision Problem?
2. What is NP-hard generation problem?
3. State Cooks theorem.
4. Define NP-hard and NP-complete.
5. Write short notes on a) Node covering problem b) NP-hard graph
problems c) hard code generation problems

14

Downloaded by Thanush S ([email protected])