$[3$pts$]$ Suppose you are given a set of positive integers $=\{1,2,...,\}$ and a positive integer $.$

A subset $$ is called feasible if the sum of the numbers in $$ does not exceed $,$ i$.$e$.$

$$ in $.$

The sum of the numbers in $$ will be called the total sum of $.$ You would like to select a feasible

subset $$ of $$ whose total sum is as large as possible.

Here is the algorithm:

Initially $=$

Define $=0$

For $=1,2,...,$

If $+$

then

$\{\}$

$+$

Endif

EndFor

a$.[1$pt$]$ Give an instance in which the total sum of the set $$ returned by this algorithm

is less than half the total sum of some other feasible subset of $.$

b$.[2$pts$]$ Give a polynomial$-$time approximation algorithm for this problem with the

following guarantee: It returns a feasible set $$ whose total sum is at least half

as large as the maximum total sum of any feasible set $.$ Your algorithm should

have a running time of at most $($ log $)$