$3$ PAC$-$Learning of Threshold Functions $[5+10=15$ points$]$

In the class, we saw an algorithm A for PAC$-$learning of threshold function. That algorithm computed the uncertainty

interval $($the interval between the right$-$most negative point and the left$-$most positive point$)$ and output hA as the middle

point in the uncertainty interval.

$($a$)$ A talented student named Sarah devises a different algorithm B that partitions the uncertainty interval into three

equal parts and outputs the rightmost point of the first part. For example, if the uncertainty interval is $(0\mathrm{.}5,0\mathrm{.}62],$

B returns hB $=0\mathrm{.}54.$ Specify whether the analysis we saw in the class for A also applies to B or not $($without any

modification$).$ That is$,$ whether the sample complexity of B can be bounded by $1$

$$

ln$(2$

$\backslash$delta

$)$ as we saw in Slide $12.$ Justify

your answer in a few sentences.

$($b$)$ Sarah devises another algorithm C that simply returns the rightmost point of the uncertainty interval. For example,

if the uncertainty interval is $(0\mathrm{.}5,0\mathrm{.}62],$ it returns hC $=0\mathrm{.}62.$ Take a similar approach as we did in the slides to devise

the sample complexity of C$.$ Show your work and make your analysis as tight as possible. How does C compare with

A$?$