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 a
ay 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 a
ay 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.