Problem 1 (PERCEPTRON CONVERGENCE) = (a) Assume that (21, y),..., (Xm, Ym), di Rd, Yi E {+1, -1}, Vi [m] is separable, let B = min{||0|| : Vi E [m], y;wTIi > 1}, and let R= max || 21 ||. Prove that the Perceptron algorithm ie[m] stops after at most (RB)2 iterations, and when it stops it holds that Vi e [m], ywTx; > 0. (b) For the homogeneous Perceptron (i.e., with zero bias), prove that (a) is tight in the following sense: For any positive integer m, there exist a vector wt e Rd (for some appropriate d) and a sequence of examples {(x1, y),..., (I'm, Ym)} such that the following hold: i. R = max ||*|| 1. Note that, using the notation in (a), we therefore get B = min{||w|| : Vi [m], yiwFri > 1}