CSE 321 Homework 5
1) Suppose that you have an array A. A = {2, 3, -5, -8, 6, -1}. Propose a dynamic programming algorithm that checks whether there is a subset with total sum of elements equal to zero. Your algorithm should display the elements of each subset whenever it finds them. Implement your algorithm with Python and explain it in your report file.
2) Suppose that you have a set of integers arranged in the form of a triangle like below. Your aim is to find the smallest sum path from the triangle apex to its base through a sequence of adjacent numbers. The sequence in the following example is shown by the circles. Design a dynamic programming algorithm for this problem. Implement your algorithm with Python and explain it in your report file.
3) Suppose that you have a knapsack problem. You are given N items of weights 𝑤1, 𝑤2,… 𝑤n and their values are 𝑣1, 𝑣2, …, 𝑣n, respectively. The knapsack has capacity 𝑊. Your goal is to find the most valuable subset of the items that fit into the knapsack. You can pick from each item as many as you can. Design a dynamic programming algorithm and explain each step in your report file. Implement your algorithm with Python and explain it in your report file. Apply your algorithm with these values:
𝑤1 = 5, 𝑤2 = 4, 𝑤3 = 2; 𝑣1 = 10, 𝑣2 = 4, 𝑣3 = 3; W=9.
