4. (20 points) This is a warm-up exercise on algorithm design and analysis.

The knapsack problem is defined 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 find 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 efficient 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 {9,24,14,5,8,17} and K = 20, then {9,5} is a factor of 2 approximation solution. Note that such a solution may not be unique. For example, {9, 8} 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 find 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 find 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 difficult to understand another persons 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.