All the houses in the town SingleLongRoad are built sparsely along a single long road, which

can be viewed as a long horizontal line segment with houses being points on that line. The

residents of all these houses are enthusiastic users of mobile phones, and your task is to

build mobile phone base stations along the road, so that every house is within $6$ kilometres

of one of these base stations; again you can view the base stations as points on the line

segment. We assume that a base station built at point p on the line covers all houses within

$6$ km to the left from p$,$ and all the houses within $6$ km to the right from p$.$

$($i$)$ Give an efficient algorithm that achieves this goal using the smallest possible number

of base stations. $[6$ marks$]$

$($ii$)$ Provide an argument as to why your algorithm indeed uses the minimum number of

base stations. $[4$ marks$]$

$($b$)$ Define the Fractional Knapsack Problem and the $\{0,1\}$ Knapsack Problem. Be sure to

explain their similarities and differences. $[4$ marks$]$

What is the name of the general solution method that we can use to solve the Fractional

Knapsack Problem, and what is the different solution method that we can use to solve the

$\{0,1\}$ Knapsack Problem? $[2$ marks$]$

Briefly describe a procedure for solving the Fractional Knapsack Problem. $($No pseudo$-$

code is necessary, just a short description in words will suffice.$)$

$[4$ marks$]$

PAPER CODE COMP$202$ page $5$ of $6$ Continued