[go: up one dir, main page]
Scribd
Upload
13 views2 pages

DAA Asignment 2

This assignment covers various topics in algorithm design and analysis, including dynamic programming, optimization problems, minimum cost spanning trees using Prim's and Kruskal's algorithms, and shortest path algorithms like Dijkstra's and Bellman-Ford. It also includes sorting algorithms such as counting sort, radix sort, and bucket sort, as well as topics like the Longest Common Subsequence (LCS) and matrix chain multiplication. Additionally, it discusses NP-hard and NP-complete problems, and the differences between greedy methods and dynamic programming.

Uploaded by

Abhishek Anand
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
13 views2 pages

DAA Asignment 2

This assignment covers various topics in algorithm design and analysis, including dynamic programming, optimization problems, minimum cost spanning trees using Prim's and Kruskal's algorithms, and shortest path algorithms like Dijkstra's and Bellman-Ford. It also includes sorting algorithms such as counting sort, radix sort, and bucket sort, as well as topics like the Longest Common Subsequence (LCS) and matrix chain multiplication. Additionally, it discusses NP-hard and NP-complete problems, and the differences between greedy methods and dynamic programming.

Uploaded by

Abhishek Anand
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/ 2

Design and Analysis of Algorithm

Assignment -2
(For B1, B2,B3 & B4 Batch)
Attempt all questions:
Q1. Explain dynamic programming method. Formulate dynamic programming recurrence equations
for 0/1 knapsack problem.
Q2. What is an optimization problem? How greedy method can be used to solve the optimization
problem?
Q3. (a) Define minimum cost spanning tree. Write Prim’s algorithm to generate a minimum cost
spanning tree for any given weighted graph. Generate minimum cost spanning tree for
following graph using Prim’s algorithm.

Q3. (b) For the graph shown below fond out the minimum cost spanning tree (MST) by Kruskal’s
method.

Q4. Suppose that all edge in a weights in a graph are integers ranging from 1 to |V|. How
fast can you make Kruskal’s algorithm run? What if the edge weights are integers in the range
from 1 to W for some constant W.

Q5. (a) Solve the shortest path problems using Dijkstra’s algorithm. Count the number of
distance updates.
Q5. (b) How can the output of the Floyad-Warshall algorithm be used to detect the presence of a
negative cycle? Apply Floyad-Warshall algorithm for constructing shortest path.

Q6. Solve the single source shortest path from node 1 to 7 in the graph given below using Bellman
Ford algorithm.

Q7. Explain counting sort, radix sort, and bucket sort by one example each.
Q8. Determine the LCS (Longest Common Subsequence) of <1,0,0,1,0,1,0,1> and
<0,1,0,1,1,0,1,1,0
Q9. We have given the matrices A1 A2 A3 and A4. Find an optimal parenthesization sequence of
a matrix chain multiplication whose sequence of dimension is 3x2, 2x4, 4x2, 2x5.

Q10. Write short notes on:


(a) Explain NP-hard and NP-complete problems with examples
(b) Differentiate between Greedy method and Dynamic programming.
(c) N – Queens problem using back tracking
(d) Travelling salesman problem using branch and bound

You might also like