3. Give recurrence relations (including base cases) that are suitable for dynamic programming solutions to the following problems. You do not need to prove your correctness, but provide justification for each. (a) ROD-CUT(n, P[1,..., n]): For a rod of length n and a list P of prices where P[i] is the price for a piece of length i, determine the maximal profit one could make by cutting up the rod and selling the pieces. For example, for n = 5 and P = [1, 6, 7, 4, 8], one would cut the rod into two pieces, one of length 3 and one of length 2, and sell them for 7 and 6 respectively to make a profit of 13. (b) FEED-QUACKERS(n): You have a pet duck named Quackers who only eats grapes 1, 2, or 3 at a time. If there are n grapes, determine the number of ways Quackers can eat the grapes, where number of ways represents the number of distinct ordered sums of 1,2, or 3 that add up to n. For example, if there are 3 grapes, eating 1 grape then 2 grapes would be considered distinct from eating 2 grapes then 1 grape. (c) SUBSET-SUM(S, T): For a set S of non-negative integers and an integer target sum T, determine whether there exists a subset of S which sums to T. The output should be true if such a subset exists and false otherwise. 3. Give recurrence relations (including base cases) that are suitable for dynamic programming solutions to the following problems. You do not need to prove your correctness, but provide justification for each. (a) ROD-CUT(n, P[1,..., n]): For a rod of length n and a list P of prices where P[i] is the price for a piece of length i, determine the maximal profit one could make by cutting up the rod and selling the pieces. For example, for n = 5 and P = [1, 6, 7, 4, 8], one would cut the rod into two pieces, one of length 3 and one of length 2, and sell them for 7 and 6 respectively to make a profit of 13. (b) FEED-QUACKERS(n): You have a pet duck named Quackers who only eats grapes 1, 2, or 3 at a time. If there are n grapes, determine the number of ways Quackers can eat the grapes, where number of ways represents the number of distinct ordered sums of 1,2, or 3 that add up to n. For example, if there are 3 grapes, eating 1 grape then 2 grapes would be considered distinct from eating 2 grapes then 1 grape. (c) SUBSET-SUM(S, T): For a set S of non-negative integers and an integer target sum T, determine whether there exists a subset of S which sums to T. The output should be true if such a subset exists and false otherwise