This problem is based on a strategy I followed for a Grad Algo endsem exam some years ago. There were many questions with different marks, say m1 m2...mn, more than what even the brightest student could attempt. The students had to choose some questions of total marks at most a given T. For simplicity assume that students score the full marks in whatever questions that they attempt. Call the problem of finding the best score that they can obtain as ENDSEM (there may or may not be questions that add to T marks). 


1 [2 points]. Explain in at most 10 sentences why ENDSEM is a difficult problem in itself. But be as precise and mathematical in explanation as you can, just be brief in explaining your idea and detailed proofs can be left out or shortened. 
2 [3 points]. Let OPT denote the best possible marks. Consider the strategy of choosing questions one by one in some order and stopping when including the next question would cross the limit of T. Explain why this strategy does not yield a 2-relative approximation algorithm.
3 [5 points]. Design a linear time 2-relative approximation algorithm. Justify ratio and running time. Hint: deja vu. 
4 [5 points]. Describe a (1+e)-relative approximation algorithm where e is any positive number (e.g., 0.05, 1, 3.5, etc.). Derive ratio and complexity. Hint: reduction.

Page limit: 2 pages ( strict). So be clever in your arguments. I intend you to reuse known results as much as possible in a mathematically rigorous manner.


Looking back at where you were before the 1st lecture, I will consider my job done well if you reached this far on your own.