Unit 5
1.
Design a tree stage system with device Types D1,
D2, D3 with costs of rs.30, Rs 20, rs.15 Rupees respectively. The cost of the
system is to be no more than Rs 105 the reliability of each device type is
0.9,0.8 and 0.5 respectively
2.
A) Define principal of optimality. B) Write and explain algorithm for
all-Paris-shortest path.
3.
Let n=4 and {a1,a2,a3,a4}={do , if , int ,while}
let p(1:4)=(3,3,1,1),q(0:4)=(2,3,1,1,1) construct OBST.
4.
Explain
and write about Matrix Chain Multiplication Algorithm with a Example?
5.
Solve 0/1 Knapsack problem with Dynamic
programming method for the given data n=3,{w1,w2,w3}={2,3,4} and
{p1,p2,p3}={1,2,5} and capacity of knapsack m=6
Unit 6
1. Define
the following terms a. State
space b.
Live node c. E-Node d.
Answer state e. Dead Node
2. Explain
and write the algorithm for N-Queens with an Example.
3. Explain
sum of subsets with example of for the
set { 7,11,13,24} with m=31
4. Explain
algorithm of graph coloring problem?
5. Explain
Algorithm for Hamiltonian cycle?
Unit 7
1. A)Define
the term Branch and Bound. Explain with an example. B) Explain properties of LC
search
2. Explain
the principles of a. Control Abstraction of least cost search b.
FIFO BB c. LIFO BB
3. Generate state space tree of travelling sales
person problem for the given cost matrix
* 20 30
10 11
15
* 16 4
2
3 5
* 2 4
19 6
18 * 3
16 4
7 16 *
Heare * means infinity
4.
Explain
the 0/1 knapsack problem using LC Branch and Bound for the given data
n=4,{p1,p2,p3,p4}={10,10,12,18} and {w1,w2,w3,w4}={2,4,6,9} with capacity of
knapsack m=15
5.
Generate state space tree of travelling sales
person problem for the given cost matrix
* 7 3 12 8
3 * 16 4 2
5 8 * 6 18
9 3 5 * 11
18 14 9 8 *
Unit 8
1.Np-hrd and np-complete problems
2. Explain cook’s theorm
8 th unit lo evae
itcharu
No comments:
Post a Comment