KEMBAR78
Daa | PDF
Scribd
Upload
29 views3 pages

Daa

The document outlines various algorithmic problems and techniques, including the 0/1 Knapsack problem, Job Sequencing with deadlines, Greedy methods, and Dijkstra's algorithm. It also discusses NP-hard and NP-complete classes, the Travelling Salesman problem, Optimal Binary Search Trees, and minimum cost spanning trees using Kruskal's and Prim's algorithms. Each problem is accompanied by specific examples and requests for optimal solutions or explanations of algorithms.

Uploaded by

Saisrikar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
29 views3 pages

Daa

The document outlines various algorithmic problems and techniques, including the 0/1 Knapsack problem, Job Sequencing with deadlines, Greedy methods, and Dijkstra's algorithm. It also discusses NP-hard and NP-complete classes, the Travelling Salesman problem, Optimal Binary Search Trees, and minimum cost spanning trees using Kruskal's and Prim's algorithms. Each problem is accompanied by specific examples and requests for optimal solutions or explanations of algorithms.

Uploaded by

Saisrikar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

1.

Solve the following 0/1 Knapsack problem using dynamic programming P= (11, 21, 31,

33), W= (2, 12, 23, 15), C=42, n=4 .( by applying Merging & purging rule)

2. State the Job– Sequencing with deadlines problem. Find an optimal sequence to the n= 5

Jobs where profits (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and deadlines (d1, d2, d3,

d4, d5) =(2, 2, 1, 3, 3).

3. a) Explain the general method of Greedy method.

b) Write and explain the Kruskal’s algorithm with an illustrative example.

4. Discuss in detail about the classes of NP-hard and NP-complete classes?

5. Explain the techniques for Binary Trees?

6. Explain Dijkstra’s algorithm and find out single source shortest path with example?

1. Explain the Travelling salesman problem by using branch and bound with an example?

2. Draw an Optimal Binary Search Tree for n=4 identifiers (a1,a2,a3,a4) = ( do, if, read,

while) P(1:4)=(3,3,1,1) and Q(0:4)=(2,3,1,1,1).

3. Consider the following graph and apply Dijkstra's algorithm and find out single source

shortest path?

4. a) Compare NP Hard and NP Complete b) State and prove the Cook’s theorem

5. Find the optimal solution by using Krushkals Algorithm to find minimum cost spanning of the

following graph.
6. Solve the following 0/1 Knapsack

problem using Branch and Bound Technique for the given values P= (11, 21, 31, 33), W= (2, 12,

23, 15), C=42, n=4 .

1 Explain OBST with an example by using dynamic programming?

2 a. Write an algorithm of all pairs shortest path problem?

b. Explain Job sequencing with dead line problem with an example?

3 Find the optimal solution by using Prim’s minimum cost spanning of the following

graph.
4 Solve the following 0/1 Knapsack problem using dynamic programming P= (11, 21, 31,

33), W= (2, 12, 23, 15), C=42,n=4.

5 Explain different Traversing Technique with example?

6 Explain Connected and Biconnected Components with example?

You might also like