Scribd
Upload
19 views2 pages

Daa Assignment-2

The document outlines various problems and algorithms related to dynamic programming, greedy methods, and branch and bound techniques, including the 0/1 Knapsack problem, Floyd-Warshall algorithm, and Traveling Salesperson Problem. It also covers job sequencing for maximum profit, Minimum Spanning Tree using Kruskal's algorithm, and shortest path algorithms like Dijkstra's. Additionally, it discusses NP-Hard and NP-Complete problems and includes numerical problems for practical application.

Uploaded by

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

Daa Assignment-2

The document outlines various problems and algorithms related to dynamic programming, greedy methods, and branch and bound techniques, including the 0/1 Knapsack problem, Floyd-Warshall algorithm, and Traveling Salesperson Problem. It also covers job sequencing for maximum profit, Minimum Spanning Tree using Kruskal's algorithm, and shortest path algorithms like Dijkstra's. Additionally, it discusses NP-Hard and NP-Complete problems and includes numerical problems for practical application.

Uploaded by

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

UNIT III – Dynamic Programming

1. Given weights = {2, 3, 4}, profits = {4, 6, 7}, and capacity = 5, solve the 0/1 Knapsack
problem using dynamic programming. [BTL-3]

2. Demonstrate Floyd-Warshall algorithm to find all pairs shortest paths for the graph

[ ]
0 4 ∞ 7
9 0 89 ∞
with the following distance matrix: [BTL-3]
∞ 5 0 8
5 7 ∞ 0

3. Solve the Traveling Salesperson Problem for 4 cities using dynamic programming with

[ ]
0 10 1 2 20
9 0 35 25
the given cost matrix: [BTL-3]
15 35 0 30
20 25 30 0
4. Given a system with 3 components with reliability values: R1 = 0.9, R2 = 0.95, R3 = 0.92,
with cost (10,15,20) with the maximum cost 90. [BTL-3]

5. Apply dynamic programming to fill the knapsack for the weights {4,5,3,2} and profits
{2,3,4,1} for the knapsack weight limited to 9. [BTL-4]

6. Analyze All pairs shortest path Algorithm with a Example. [BTL-4]

UNIT IV – Greedy Method & Traversal Techniques

7. Given 4 jobs with profits = {100, 19, 27, 25} and deadlines = {2, 1, 2, 1}, find the
maximum profit using job sequencing. [BTL-4]

8. Use Kruskal’s algorithm to find the Minimum Spanning Tree (MST) for the graph:
Vertices: {A, B, C, D}, Edges: A-B(1), A-C(3), B-C(1), B-D(4), C-D(2). [BTL-3]

9. Solve Dijkstra’s algorithm for the graph with vertices A to D and weights: A-B:1, A-C:4,
B-C:2, B-D:6, C-D:3. Start node: A. [BTL-3]
10. Solve the fractional knapsack problem with weights = {10, 20, 30}, values = {60, 100,
120}, and capacity = 50. [BTL-3]

11. Perform in-order, pre-order, and post-order traversal on the binary tree with example.
[BTL-3]

12. Apply single source shortest path Algorithm for the below Graph using Greedy method.
[BTL-4]

UNIT V – Branch and Bound & NP Problems (Numerical Problems)


13. Solve the 0/1 Knapsack problem using Least count Branch and Bound with items:
Weights = {5, 3, 4, 6}, profits = {40, 50, 55, 20}, Capacity = 15. [BTL-3]

14. Use Branch and Bound to solve the Traveling Salesperson Problem for the cost matrix:
R1:[∞, 20, 30, 10], R2:[15, ∞, 16, 4], R3:[3, 5, ∞, 2], R4: [19, 6, 18, ∞]. [BTL-3]

15. Apply Branch and Bound to Problem for cost matrix: [9, 2, 7], [6, 4, 3], [5, 8, 1]. [BTL-4]

16. Discuss NP-Hard and NP-Complete. [BTL-2]

17. Analyze Traveling Salesperson Problem using Branch and bound for

[ ]
∞ 5 8 9
5 ∞ 10 6
the cost matrix: [BTL-4]
4 3 ∞ 6
5 7 8 ∞
18. Apply FIFO using branch and bound with items: Weights = {2, 4, 5, 9}, profits = {9, 9, 12,
19}, Capacity = 15. [BTL-3]

You might also like