[Solved] CS317 Homework 3

Submission Instructions: You have two options. Either you can submit the paper copy in class on the due date or you can upload it on the Canvas. If you chose to upload it on the Canvas, it must be a single PDF file.

Q1. What is Dynamic Programming (DP) technique? Explain the 4 generic steps to solve a given problem using DP technique. Explain the Optimal Substructure and Overlapping Subproblems properties of DP. (5 points)

Q2. Read section 15.2 Matrix-chain multiplication problem (p370-p377) from Introduction to Algorithms (3^rd edition). Describe in detail the 4 steps sequence that are used to solve the Matrix Chain Multiplication problem. (10 points)

Note: Introduction to Algorithms (3^rd edition) book is available for free through UAH library as an ebook.

Q3. Read section 15.4 Longest Common Subsequence problem (p390-p395) from Introduction to Algorithms (3^rd edition). Describe in detail the 4 steps sequence that are used to solve the LCS problem. Determine an LCS of <1, 0, 0, 1, 0, 1, 0, 1> and <0, 1, 0, 1, 1, 0, 1, 1, 0>. (10+ 5 points)

Q4. Explain the Floyds Algorithm for the all-pair shortest paths problem. Solve the all-pairs shortest-path problem for the digraph with the following weight matrix:

(10 points)

Q5. Explain the 0-1 Knapsack problem. Describe the DP approach to solving 0-1 Knapsack problem. Consider the following knapsack problem:

Use bottom-up DP approach to fill the DP table. Find the maximum value that can be put in the knapsack and the optimal solution set (items that were put in the knapsack). (10 points)

Q6. Explain P and NP class of problems. Explain P=NP? argument. What would happen if P=NP is found to be true? Why do we classify problems into different complexity classes such as P, NP, NP-Complete, NP-Hard etc? Why it is so important to study these complexity classes? (20 points)

Q7. Explain the Backtracking technique. Explain the nQueens problem and solve the 4-queens problem using state-space tree. Show the each steps while generating the final state-space tree. (10 points)

Q8. Explain the Branch-and-Bound technique. Solve the following knapsack problem using branch-and-bound technique. (10 points)

Knapsack Weight (W) = 10

Q9. Use Huffman coding technique to find the encoding table for the word Honorificabilitudinitatibus. Show the final Huffman tree. What is the compression ratio (compared to its 8-bit binary representation)? (10 points)

Q10. Construct a BST from these numbers 15, 26, 30, 31, 17, 18, 10, 8, 11, 13, 14, 12. When does the search, insertion and deletion on BST perform worst? Give an example of a worst case input. (10 points)

Q11. Delete number 20 from the following BST and then delete number 25. Show the deletion steps. (10 points)