\documentclass[12pt,a4paper]{article}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth     155mm
\topmargin     -15mm
\textheight    240mm

\begin{document}

%-----------------------------------------------------------------------

\noindent
{\bf Data Mining 2: Frequent Pattern Mining} \hfill Summer 2018 \\
Christian Borgelt \hfill from 04.06.2018

%-----------------------------------------------------------------------

\vskip3ex
\centerline{\bf Exercise Sheet 5}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 18 \quad\rm SaM Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How is support counted in the SaM algorithm? \\
     What does SaM have to ensure for the transaction array
     for this to work?
\item[b)\hfill]
     What does the merge step of the SaM algorithm achieve? \\
     Why can the merge step of the SaM algorithm be a problem? \\
     (Hint: What corresponds to the merge step in the Eclat algorithm?)
\item[c)\hfill]
     \parbox[t]{100mm}{Construct the initial database representation
     for the SaM algorithm for the transaction database shown
     on the right!}\hfill
     \begin{tabular}[t]{@{}l@{}}
     $a$ $d$ $e$ \\
     $b$ $c$ $d$ \\
     $a$ $c$ $e$ \\
     $a$ $c$ $d$ $e$ \\
     $a$ $e$ \\
     \end{tabular}\hskip10mm
     \begin{tabular}[t]{@{}l@{}}
     $a$ $c$ $d$ \\
     $b$ $c$ \\
     $a$ $c$ $d$ $e$ \\
     $c$ $b$ $e$ \\
     $a$ $d$ $e$ \\
     \end{tabular}
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 19 \quad\rm RElim Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How does the RElim algorithm improve over the SaM algorithm? \\
     Which sorting principle is exploited in SaM, which in RElim?
\item[b)\hfill]
     How can the RElim algorithm achieve merging of equivalent
     transactions (or transaction suffixes)?
     When should this be done?
\item[c)\hfill]
     Construct the initial database representation
     for the RElim algorithm for the transactions
     shown in Exercise 19c!
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 20 \quad\rm $k$-items Machine}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     What is a $k$-items machine?
     Why can it be used only for few items (small $k$)?
\item[b)\hfill]
     How is a $k$-items machine related to the RElim algorithm? \\
     What are the differences and the advantages/disadvantages?
\item[c)\hfill]
     Even though the $k$-items machine can be used only for few items,
     it is highly useful for frequent item set mining. Why? How are
     items beyond the limit~$k$ of the $k$-items machine handled?
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 21 \quad\rm FP-growth Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     What is an FP-tree?
     How is it constructed from a transaction database? \\
     Why does it combine a horizontal and a vertical representation?
\item[b)\hfill]
     How is support counted with an FP-tree?
\item[c)\hfill]
     How is an FP-tree projected? What does the projection yield?
\item[d)\hfill]
     How do we obtain the conditional transaction database
     for the second subproblem in the FP-growth algorithm?
\item[e)\hfill]
     \parbox[t]{100mm}{Execute the FP-growth algorithm
     for the transaction database shown on the right and
     a minimum support $s_{\min} = 3$! \\[1ex]
     You may skip the steps of finding the item frequencies and
     resorting the items in the transactions w.r.t.\ the frequency
     order (that is: use the alphabetical order).}\hfill
     \begin{tabular}[t]{@{}l@{}}
     $a$ $d$ $e$ \\
     $b$ $c$ $d$ \\
     $a$ $c$ $e$ \\
     $a$ $c$ $d$ $e$ \\
     $a$ $e$
     \end{tabular}\hskip10mm
     \begin{tabular}[t]{@{}l@{}}
     $a$ $c$ $d$ \\
     $b$ $c$ \\
     $a$ $c$ $d$ $e$ \\
     $b$ $c$ $e$ \\
     $a$ $d$ $e$
     \end{tabular}
\end{enumerate}

%-----------------------------------------------------------------------

\end{document}
