%root: main.tex
\begin{algorithm}[t]
	\caption{\sampmon(\circuit)}
	\label{alg:sample}
	\begin{algorithmic}[1]
		\Require \circuit: Circuit
		\Ensure \vari{vars}: TreeSet
		\Ensure \vari{sgn} $\in \{-1, 1\}$
		\Comment{\Cref{alg:one-pass-iter} should have been run before this one} 
		\State $\vari{vars} \gets \emptyset$ \label{alg:sample-global1}
		\If{$\circuit.\type = +$}\Comment{Sample at every $+$ node}
			\State $\circuit_{\vari{samp}} \gets$ Sample from left input ($\circuit_{\linput}$) and right input ($\circuit_{\rinput}$) w.p. $\circuit.\vari{Lweight}$ and $\circuit.\vari{Rweight}$. \label{alg:sample-plus-bsamp} \Comment{Each call to \sampmon uses fresh randomness}
			\State $(\vari{v}, \vari{s}) \gets \sampmon(\circuit_{\vari{samp}})$\label{alg:sample-plus-traversal}
			\State $\Return ~(\vari{v}, \vari{s})$
		\ElsIf{$\circuit.\type = \times$}\Comment{Multiply the sampled values of all inputs}
			\State $\vari{sgn} \gets 1$\label{alg:sample-global2}
			\For {$input$ in $\circuit.\vari{input}$}\label{alg:sample-times-for-loop}
				\State $(\vari{v}, \vari{s}) \gets \sampmon(input)$
				\State $\vari{vars} \gets \vari{vars} \cup \{\vari{v}\}$\label{alg:sample-times-union}
				\State $\vari{sgn} \gets \vari{sgn} \times \vari{s}$\label{alg:sample-times-product}
			\EndFor
			\State $\Return ~(\vari{vars}, \vari{sgn})$
		\ElsIf{$\circuit.\type = \tnum$}\Comment{The leaf is a coefficient}
			\State $\Return ~\left(\{\}, \func{sgn}(\circuit.\val)\right)$\label{alg:sample-num-return}\Comment{$\func{sgn}(\cdot)$ outputs $-1$ for \circuit.\val $\geq 1$ and $-1$ for \circuit.\val $\leq -1$}\label{alg:sample-num-leaf}
		\ElsIf{$\circuit.\type = var$}
			\State $\Return~\left(\{\circuit.\val\}, 1\right)	$\label{alg:sample-var-return}
		\EndIf
	\end{algorithmic}
\end{algorithm}