begin{algorithm}[H]
caption{LSM Algorithm}label{euclid}
begin{algorithmic}
State Generate $M$ paths of stock prices $S_i(t)$, $i = 1,ldots,M$
State which evolves in discreet time index $j = 1,ldots, N$ (time interval $Delta t = frac{T}{N}$)
For{$i$}
    For{$j$}
      State Generate $S_{i} = S_{i-1}e^{(r-q-frac{sigma^2}{2})Delta t + sigmasqrt{Delta t}Z_{i,j}}, Z_{i,j}sim N(0,1)$
EndFor
EndFor
    textbf{end for}\
textbf{end for}
State Put $P_i gets f(S_{i}(t_N))$ for all $i$
For{$t$ from $t_{N-1}$ to $t_1$}\
    Find in the money paths ${i_1,i_2,ldots, i_n}$ such that $f(S_i(t)) > 0$\
    Set $ipaths gets {i_1,i_2,ldots, i_n}$\
    Set $x_igets S_i(t)$ and $y_igets e^{-rDelta t}P_i$ for $iin ipaths$\
    Apply regression on $x,y$ to obtain regression coefficients $hat{beta}_0,ldots, hat{beta}_k$\
    Estimate continuation values $hat{C}(S_i(t))$ then calculate the value of immediate exercise $f(S_i(t))$\    for $iin ipaths$
For{$i$}
If{$iin ipaths$ textbf{and} $f(S_i(t)) > hat{C}(S_i(t))$ }
State $P_igets f(S_i(t))$\
            textbf{else}\
State $P_igets e^{-rDelta t}P_i$\
EndIf
EndFor
    textbf{end if}\
   textbf{end for}\
 textbf{end for}\
$pricegets frac{1}{M}sum_{i=1}^{M}e^{-rDelta t}P_i$
end{algorithmic}
end{algorithm}