Design and Analysis of Algorithm 2016-17 Previous Year Paper Solution
Short Notes

Q8 Write short notes any (two) of the following [Marks: 5 x2]

a) NP-Complete

Ans: A problem is called NP (nondeterministic polynomial) if its solution can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess. If a problem is NP and all other NP problems are polynomial-time reducible to it, the problem is NP-complete. Thus, finding an efficient algorithm for any NP-complete problem implies that an efficient algorithm can be found for all such problems, since any problem belonging to this class can be recast into any other member of the class. It is not known whether any polynomial-time algorithms will ever be found for NP-complete problems, and determining whether these problems are tractable or intractable remains one of the most important questions in theoretical computer science. When an NP-complete problem must be solved, one approach is to use a polynomial algorithm to approximate the solution; the answer thus obtained will not necessarily be optimal but will be reasonably close.

b) N-Queen’s Problem

Ans: The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

The chess queens can attack in any direction as horizontal, vertical, horizontal and diagonal way.

The solution to the problem requires that we place a queen on the board and then analyze all of the attack positions to see if there is a queen that could capture the new queen. If there is, then we try another position.

To explain, Let’s analyze a 4 Queen problem solution on a 4 x 4 chessboard. The one solution is shown below:

8-Queen Problem

We can solve this problem using a stack and backtracking logic. A pseudocode solution using stack is:

Algorithm NQueenProblem(boardsize)
1 createstack(stack)
2 set row = 1
3 set col = 0
4 loop (row <= boardsize)
    1    loop (col <= boardsize AND row <= boardsize)
         1    increment col
         2    if (not guarded (row, col))
                  1 place queen at row-col intersection on board
                  2 pushstack (row-col into stack)
                  3 increment row
                  4 set col to 0
         3    end if
         4    loop (col >= boardsize)
              1    popstack (row-col from stack)
              2    remove queen from row-col intersection on board
         5    end loop
     2   end loop
5 end loop
6 printboard(stack)
7 return
end NQueenProblem

c) Vertex-Cover Algorithm

Ans: The vertex-cover problem is a NP-complete problem  which is the problem of finding a vertex cover of minimum size in a given undirected graph.

Given a graph, one must find a smallest set of vertices such that every edge has at least one end vertex in the set. Such a set of vertices is called a minimum vertex cover of the graph and in general can be very difficult to find.

The vertex-cover algorithm is a polynomial-time algorithm for finding minimal vertex covers in graphs.

1 C = Θ
2 E' = G.E
3 while E' ≠ Θ
4    let (u,v) be an arbitrary edge of E'
5    C = C U {u,v}
6    remove from E' every edge incident on either u or v
7 return C