Exercise $($seet the pic for correct symbols$)$: A decision list is defined by a sequence $l_1,$dots,$l_k$ of literals, together with $k+1$ binary

labels $b_1,$dots,$b_{k+1}.$ The function computed by this decision list is the one computed by the following

algorithm.

Let $D{L}_n$ be the class of functions computed by a decision list on $n$ variables. Show that

Every $hinD{L}_n$ can be computed by a decision list, in which each variable appears at most

once

$D{L}_n$ is efficiently learnable by ERM

$D{L}_n$ is efficiently reducible to $Hal{f}_n$ via the reduction ${}_n$:$\{+-1{\}}^n\{+-1{\}}^{n+1}$ defined by

${}_n(x)=(1,x_1,x_2,$dots,$x_n)$