(20 points) This is a \warm-up" exercise on algorithm design and analysis. The knapsack problem is dened as follows: Given as input a knapsack of size K and n items whose sizes are k1; k2; : : : ; kn, where K and k1; k2; : : : ; kn are all positive real numbers, the problem is to nd a full \packing" of the knapsack (i.e., choose a subset of the n items such that the total sum of the sizes of the items in the chosen subset is exactly equal to K). It is well known that the knapsack problem is NP-complete, which implies that it is very likely that ecient algorithms (i.e., those with a polynomial running time) for this problem do not exist. Thus, people tend to look for good approximation algorithms for solving this problem. In this exercise, we relax the constraint of the knapsack problem as follows. We still seek a packing of the knapsack, but we need not look for a \full" packing of the knapsack; instead, we look for a packing of the knapsack (i.e., a subset of the n input items) such that the total sum of the sizes of the items in the chosen subset is at least K=2 (but no more than K). This is called a factor of 2 approximation solution for the knapsack problem. To simplify the problem, we assume that a factor of 2 approximation solution for the knapsack problem always exists, i.e, there always exists a subset of items whose total size is at least K=2 and at most K. For example, if the sizes of the n items are f9; 24; 14; 5; 8; 17g and K = 20, then f9; 5g is a factor of 2 approximation solution. Note that such a solution may not be unique. For example, f9; 8g is also a solution. Design a polynomial time algorithm for computing a factor of 2 approximation solution, and analyze the running time of your algorithm (in the big-O notation). Note that although there may be multiple solutions, your algorithm only needs to nd one solution. If your algorithm runs in O(n) time and is correct, then you will get full points.

Note: I would like to emphasize the following, which applies to the algorithm design questions in all assignments of this course.

1. Algorithm Description You are required to clearly describe the main idea of your al gorithm. 2. Pseudocode The pseudocode is optional. However, I usually nd pseudocode very help- ful to explain the algorithm. So you are strongly encouraged to provide pseudocode for your algorithm as well. (The reason I want to see the algorithm description instead of only the code or pseudocode is that it would be dicult to understand another person's code without any explanation.) 3. Correctness You also need to explain why your algorithm is correct, i.e., why your algorithm can produce a factor of 2 approximation solution. 4. Time Analysis Please make sure that you analyze the running time of your algorithm.