# IGNOU MCS-031 SOLVED ASSIGNMENT 2013-14

Question 6:

(a)    Is there a greedy algorithm for every interesting optimization problems? Justify your Claim.

Ans :- Optimization problem is one in which some value or set of values of interest is required to be either minimized or maximized with respect to some given relation on the values. Finding the minimum number of coins is example of optimization problem.

The essence of greedy technique is that in the process of solving an optimization problem, initially and at subsequent stages, we evaluate the costs / benefits of the various available alternatives for the next step. Choose the alternative which is optimal in the sense that either it is the least costly or it is the maximum profit yielding. In this context, it may be noted that the overall solution, yielded by choosing locally optimal steps may not be optimal.

The algorithm for Greedy Technique is given below:

{Begin algorithm for Greedy Technique}

Begin

CV ← Φ {Initially the set of considered values is empty}

while GV ≠ RV and not SoIF(CV) do

begin

V ← SeIF((GV)

if FeaF(CV È {v}) then

CV ← CV È {v}

else

RV ← RV È {v}

end

if SoIF(CV) then

return ObjF(GV)

else

return “No solution is possible”

end

{End of algorithm for Greedy Techniques}

Question 7: Write note on each of the following: (20 marks)

(i) Unsolvability/ undecidability of a problem :- A problem is decidable if there exists Turing Machine that gives the correct answer for every statement in the domain of the problem. In other words, a class of problems with two outputs “Yes” or “No” is said to be decidable (solvable) if there exists some definite algorithm which always terminates or halts with one of the two outputs “Yes” or “No”. Otherwise, the class of problem is said to be un-decidable or un-solvable.

(ii) Halting problem :- Halting problem states that given a Turing machine M and an input w to the machine, determine if the machine M will eventually halt when it is given input w.

(iii) Reduction of a problem for determining decidability :- Examples of undecidable problems in Turing Machine

• Is a language accepted by a TM empty, finite, regular, or context free?
• Does a TM meet its specification? That is does it have any bugs?

Examples of undecidable in Context Free Languages

• Are two context free grammars equivalent?
• Is a context-free grammar ambiguous?

(iv) Rice theorem :- Rice’s theorem states that any functional property of programs is undecidable. A functional property is

1. a property of the input / output behavior of the program that is it describes the mathematical function the program computes.
2. Non-trivial in the sense that it is a property of some programs but not all programs.

(v) Post correspondence problem :- Post Correspondence Problem is to determine, given a correspondence system whether that system has a match. A correspondence system is a finite set P of ordered pairs of non-empty strings; that is, P is a finite subset of ∑+ x ∑+ for some alphabet ∑. A match of P is any string w Î ∑+ such that for some n > 0 and some pairs (u1,v1), (u2,v2)….(un,vn) Î P,

(vi) NP-complete problem :- A problem P or equivalently its language L1 is said to be NP-Complete if the following two conditions are satisfied.

(i)                  The problem L2 is in the class NP.

(ii)                For any problem L2 in NP, there is a polynomial time reduction of L1 to L2.

(vii) K-colourability problem :- Now the construction of H is complete. It follows from what we have said so far that every 3-coloring of H has properties (i), (ii), (iii), and so it yields a k-coloring f of G by letting f(u) be any i such that (i,u) is colored green. Conversely, every k-coloring f of G yields a 3-coloring of H: first, each vertex (i,u) of the screen can be colored

green if f(u)=i,
red     otherwise

and then this 2-coloring of the screen can be extended into a 3-coloring of the entire H as follows. The special vertex b is colored blue and the special vertex g is colored green. As for the n odd cycles that enforce property (ii), each of them corresponds to one of the n columns of the screen; its k vertices are matched with the k vertices of the column;of these k vertices, k-1 are red and one is green. The mate of the green vertex on the cycle gets colored red; the colors on the remaining k-1 vertices of the cycle alternate between green and blue. As for the various triangles xyz that enforce property (iii), its vertex z always gets colored red; one of the vertices (i,v), (i,w) is colored red and its neighbor in the triangle gets colored green; the other one of the vertices (i,v), (i,w) is colored red or green and its neighbor in the triangle gets colored blue.

(viii) Independent set problem :- In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I. The size of an independent set is the number of vertices it contains.

A maximal independent set is an independent set such that adding any other vertex to the set forces the set to contain an edge.

A maximum independent set is a largest independent set for a given graph G and its size is denoted α(G).[1] The problem of finding such a set is called the maximum independent set problem and is an NP-hard optimization problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.