Scribd
Upload
2 views1 page

DAA Assignment

The document outlines important questions for an assignment on Design and Analysis of Algorithms (DAA). It covers various algorithms and concepts including the Bellman-Ford Algorithm, Floyd-Warshall algorithm, Dynamic Programming, Greedy methods, and string matching algorithms, among others. Additionally, it discusses complexity classes such as P, NP, NP-Complete, and NP-Hard, along with examples and problem-solving techniques.

Uploaded by

fagom57011
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
2 views1 page

DAA Assignment

The document outlines important questions for an assignment on Design and Analysis of Algorithms (DAA). It covers various algorithms and concepts including the Bellman-Ford Algorithm, Floyd-Warshall algorithm, Dynamic Programming, Greedy methods, and string matching algorithms, among others. Additionally, it discusses complexity classes such as P, NP, NP-Complete, and NP-Hard, along with examples and problem-solving techniques.

Uploaded by

fagom57011
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

Assignment -2

Important questions
Sub.- DAA
1. Define “Rate of Growth of Functions” in the context of algorithm analysis.
2. Explain the Bellman-Ford Algorithm with an example graph having
negative weights.
3. Explain the working of the Floyd-Warshall algorithm with a suitable
example. Trace the changes in the distance matrix after each iteration of
the algorithm.
4. Define the Fibonacci sequence using a recurrence relation. Explain how it
can be solved using Dynamic Programming.
5. Solve the following Fractional Knapsack problem using Greedy method:
6. Items = { (value=60, weight=10), (value=100, weight=20), (value=120,
weight=30) },
7. Capacity = 50.
8. Construct a Huffman Tree for the string ‘mississippi’. Determine the
binary code for each character and compute the total number of bits
required to encode the message using Huffman Coding. Compare the
result with standard 8-bit ASCII encoding.
9. Explain Merge Sort algorithm with recurrence relation and time
complexity.
10. Solve the Maximum Subarray Sum problem using Divide and Conquer.
11. Explain the Closest Pair of Points problem using Divide and Conquer.
12. Discuss the Fractional Knapsack problem with Greedy method.
13. Explain the 0/1 Knapsack problem using Dynamic Programming.
14. Solve the Matrix Chain Multiplication problem using DP.
15. Explain the Longest Common Subsequence (LCS) problem with example.
16. Differentiate between Divide & Conquer and Dynamic Programming.
17. Solve the N-Queen problem using Backtracking.
18. Explain the Subset Sum problem using Backtracking.
19. Explain the Rabin–Karp string matching algorithm with example.
20. Explain the Knuth–Morris–Pratt (KMP) algorithm with failure function.
21. Write a short note on Boyer–Moore string matching algorithm.
22. Compare Naïve string matching with Rabin Karp, KMP and Boyer Moore.
23. Explain the Ford–Fulkerson method for Maximum Flow with example.
24. Write short notes on Cuts and Maximum Flow in network flow problems.
25. Define and explain P, NP, NP-Complete, NP-Hard with examples.
26. Write short notes on Cook’s Theorem and its significance.
27. Give examples of problems belonging to P, NP, NP-Complete, NP-Hard
classes.

You might also like