N-Quaan Porn blam2
N ueen to be lacd NXN
hetb0Qud So t a t no Queen
lattaking +o eauh 0they :e. Quans
yame Colunm
chagsnal
hae Tuwo Vaiante Queen Problan
4 Quegn Poroblem. 4x4)
QUeen Pp blem
Fo usyqueene hat au
Plaed un Hene boaud
3
43+ (1,3
t2,)
Datc
Pagc No.
no plaue
Plae it we ned to bakh cuk
Jhue oþton + plau
buk hak
1 3
q2 2 &o" )
43 |43
44 attautng
2
1 2
Mirror&ol 11
922
4Quen PrbBum
Page No.
2
Same
3
pr
t
4
(B) (e)
3
(B) (8)
(B) (B)
3 3
y"l (6) þat
un Subset Parotlm and dui
Ne m dii tint þositine integen whose
numbet
Su findae ombi nati on
m Jhis t Caled
those
Subset
Poblam
22
m= B0
W= } 5, ID, 12il3, 15, 1%
Total Su
^um 3
|+3
5 68
558 o 58
5 58 |1o
10 52
22| u
25|33, 123
X
X
X
J45 o
X X
X
Q2 a)
2 28
3 20
2 24 |2
W= (it f kotsack )
ietl)olmalk)
2 12
Jo Go
20
2 7 28 4
3 4 24+2D
No Hen is loiy kss Dr equalto
=d42D = 44
Hen Con vot bbe splht
Ay dymic brogamig
roft t
|D
28 7 |28 20 20 oD66
20 2828 G
Y 22 242444 24 |44 |444|526D Go
Vos! =6D
dilerence. behseon Vopt - Vgiedy - Go-44
= l6
Auy
(5) T= þprqr
P D
ere areg Subyy
O2 2 -2<2 2
1f 22r 2133 :3
|Ir21334
)X+by= 443x0=34
Que-3(a): Floyd Warshall algorithm
Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted
graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the
graphs with negative cycles (where the sum of the edges in a cycle is negative).
QUE-3(b) Travelling Salesman Problem-
You are given-
A set of some cities
Distance between every pair of cities
Travelling Salesman Problem states-
A salesman has to visit every city exactly once.
He has to come back to the city from where he starts his journey.
What is the shortest possible route that the salesman must follow to complete his tour?
Example-
The following graph shows a set of cities and distance between every pair of cities-
If salesman starting city is A, then a TSP tour in the graph is-
A→B→D→C→A
Cost of the tour
= 10 + 25 + 30 + 15
= 80 units
Q.4 (A). Define NP-Hard and NP- complete problems. Specify the
problems already proved to be NP-complete.
Solution:
NP-Hard problems are decision problems that are at least as hard as the hardest
problems in NP. In other words, if there is a polynomial-time algorithm for any
NP-hard problem, then there is a polynomial-time algorithm for all problems in
NP.
NP-Complete problems are decision problems that are both NP-hard and in NP.
In other words, they are the hardest problems in NP.
Pictorial representation of all NP classes which includes NP, NP-hard, and
NP-complete
Some of the problems that have been proved to be NP-complete are:
• Travelling Salesman Problem (TSP): Given a list of cities and the
distances between each pair of cities, find the shortest possible route that
visits each city exactly once and returns to the starting point.
• Boolean Satisfiability Problem (SAT): Given a Boolean expression, can
the variables be assigned in such a way as to make the expression true?
• Knapsack Problem: Given a set of items, each with a weight and a
value, determine the number of each item to include in a collection so that
the total weight is less than or equal to a given limit and the total value is
as large as possible.
• Graph Coloring Problem: Given an undirected graph and a number of
colors, determine whether it is possible to color the vertices of the graph
with the given colors so that no two adjacent vertices have the same
color.
Q. 4 (B) Define approximation algorithms. Approximate the travelling
salesman problem with triangle inequality.
Solution:
Approximation algorithms: An Approximate Algorithm is a way of approach
NP-COMPLETENESS for the optimization problem.
This technique does not guarantee the best solution.
The goal of an approximation algorithm is to come as close as possible to the
optimum value in a reasonable amount of time which is at the most polynomial
time.
Such algorithms are called approximation algorithm or heuristic algorithm.
Travelling Salesman: In the traveling salesman Problem, a salesman must
visits n cities.
We can say that salesman wishes to make a tour or Hamiltonian cycle, visiting
each city exactly once and finishing at the city he starts from.
There is a non-negative cost c (i, j) to travel from the city i to city j.
The goal is to find a tour of minimum cost.
We assume that every two cities are connected.
Such problems are called Traveling-salesman problem (TSP).
We can model the cities as a complete graph of n vertices, where each vertex
represents a city.
It can be shown that TSP is NPC.
If we assume the cost function c satisfies the triangle inequality,
then we can use the following approximate algorithm.
Triangle inequality:
If we assume the cost function c satisfies the triangle inequality,
then we can use the following approximate algorithm.
Let u, v, w be any three vertices, we have
One important observation to develop an approximate solution is if we remove
an edge from H*, then
Tour becomes a spanning tree.
Travelling Salesman Approximation Algorithm :
Approx. TSP (G= (V, E))
1. Compute a MST of Graph G;
2. Select any vertex r is the root of the tree;
3. Let L be the list of vertices visited in a preorder tree walk of T;
4. Return the Hamiltonian cycle H that visits the vertices in the order L;
Intuitively, Approx TSP first makes a full walk of MST T, which visits each
edge exactly two times. To create a Hamiltonian cycle from the full walk, it
bypasses some vertices (which corresponds to making a shortcut)
Q. 5(a)
QUESTION 6-(A)Write Boyer Moore algorithm for string matching? Perform the
algorithm to search the occurrences of the pattern STRING in the text string
“WELCOMETOSTRINGWORLD”.
Solution:
Boyer Moore Matcher Algorithm(T[0---n], P[0----m])
1. n ←length [T]
2. m ←length [P]
3. i ←m-1 //Set i and j to the last index of P//
4. j←m-1 //Loop to the end of the text string//
5. While i<n // If both characters matches//
6. do If P[j]=T[i] // reached the end of the pattern//
7. then if j=0 // Then found a match//
8. then return i.
9. else i ←i-1
10. j ←j-1
11. Else i ← i + m –min(j, 1+ last [T[i]]) // Shift to last occurrences //
12. j←m-1
13. Return -1
QUESTION 6-(B) Write Rabin Karp string matching algorithm. Working modulo q=11,
how many spurious hits does the Rabin Karp matcher in the text T= 3141592653589793,
when looking for the pattern P=26.
Solution: The Rabin-Karp string matching algorithm calculates a hash value for the pattern, as
well as for each M-character subsequences of text to be compared. If the hash values are
unequal, the algorithm will determine the hash value for next M-character sequence. If the hash
values are equal, the algorithm will analyze the pattern and the M-character sequence. In this
way, there is only one comparison per text subsequence, and character matching is only
required when the hash values match.
RABIN-KARP-MATCHER (T, P, d, q)
1. n ← length [T]
2. m ← length [P]
3. h ← dm-1 mod q
4. p ← 0
5. t0 ← 0
6. for i ← 1 to m
7. do p ← (dp + P[i]) mod q
8. t0 ← (dt0+T [i]) mod q
9. for s ← 0 to n-m
10. do if p = ts
11. then if P [1.....m] = T [s+1.....s + m].
12. then "Pattern occurs with shift" s
13. If s < n-m
14. then ts+1 ← (d (ts-T [s+1]h)+T [s+m+1])mod q
