Online Learning $[4+4+5=13$ points$]$

This question concerns online learning in a non$-$agnostic setting. Recall that at each time$-$step, a new example is revealed,

and a classification algorithm makes a prediction, and then the actual $($true$)$ label $($which is $0$ or $1$ based on an unknown

hypothesis c$)$ is revealed. Let n denote the number of variables $($features$).$ In your solution, you can refer to any

observation$/$result established in A$3$ without re$-$proving it$.$

$($a$)$ Prove that there is an online learning algorithm for learning monotone conjunctions that makes at most n mistakes

before learning an unknown monotone conjunction c$.$

$($b$)$ Prove that any online learning algorithm for learning monotone conjunction makes at least n mistakes before learning

an unknown monotone conjunction c$.$

$($c$)$ Prove that any online learning algorithm for learning decision lists makes at least n $+1$ mistakes before learning an

unknown decision list c$.$