Book : Introduction to algorithms 3th

6. Concepts on polynomial-time complexity. (a) Exercise 34.1-4 (page 1060). (b) Professor Right finds a fast algorithm for the maximum flow problem on the network G = (V, E) with the capacity c(u, v) for the edge (u, v), which runs in O(VE(1g C)2) time, where C = max(u, v)E E C(u, v). Is it a polynomial-time algorithm? Justify your claim. 34.1-4 Is the dynamic-programming algorithm for the 0-1 knapsack problem that is asked for in Exercise 16.2-2 a polynomial-time algorithm? Explain your answer. 16.2-2 Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(n W) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack