1. One form of the knapsack problem is as follows: We are given a set of integers, A = a1, a2, ... , aN, and an integer, K. Is there a subset of A whose sum is exactly K?
a. Give an algorithm that solves the knapsack problem in O(NK) time.
b. Why does this not show that P = NP?
2. You are given a currency system with coins of (decreasing) value c1, c2, ... , cN cents.
a. Give an algorithm that computes the minimum number of coins required to give K cents in change.
b. Give an algorithm that computes the number of different ways to give K cents in change.