Homework 4Problem 1. Rod cuttingIn the rod-cutting problem, we are given a rod of length n and a table of prices p;,¢ = 1,2, ...,n. Suppose thateach cut incurs a fixed cost of C, i.e. the revenue...

I need help with these 5 questions!


Homework 4 Problem 1. Rod cutting In the rod-cutting problem, we are given a rod of length n and a table of prices p;,¢ = 1,2, ...,n. Suppose that each cut incurs a fixed cost of C, i.e. the revenue of a cutting the rod into k pieces is now the the sum of the prices of the pieces minus the costs of making the cuts (i.e. minus (k — 1)C). (a) Find a solution forn =4,C =0.5and py = 1,ps = 5,p3 = 8,p4 = 9. (b) Find a solution forn =4,C =1.5and p; =1,py; =5,p3 =8,py = 9. (c) Give a dynamic-programming algorithm to solve this problem. Problem 2. Longest common subsequence LCS Show how to compute the length of an LCS using only 2 * min(m, n) entries in the c table plus O(1) additional space. Then show how to do the same thing, but using only min(m, n) entries plus O(1) additional space. Problem 3. Longest Increasing Subsequence LIS Given an array a[0..n — 1] of n numbers, the task is to find the longest super-increasing subsequence where each number is bigger than the previous number by 10. Apply dynamic programming to solve it. Use the link “algorithm” in the notes where array d[0..n — 1] is computed (for LIS). Problem 4. Bellman-Ford algorithm Suppose that graph G = (V, E)) contains one negative-weight cycle reachable from the source s. Show that it can be computed in O(V E) time. Problem 5. Reliable path We are given a directed graph G = (V, E) and a probability p(u,v) € [0, 1] of failure for each edge (u,v) € E. We assume that these probabilities are independent. Give an algorithm with O(V 1g V + E) running time to find the most reliable path between two given vertices a and b in G.