\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 18.06.2018

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

\vskip3ex
\centerline{\bf Exercise Sheet 7}

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

\subsubsection*{Exercise 25 \quad\rm Carpenter Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How does the Carpenter algorithm exploit the alternative
     characterization of closed item sets (i.e., the one based
     on a closure operator)? What is the core problem of exploiting
     this characterization? (Hint: minimum support)
\end{enumerate}\unskip\vskip-1ex
\parbox{120mm}{\begin{enumerate}\itemsep0pt
\item[b)\hfill]
     What data structure does the Carpenter algorithm use? \\
     Could it also use a horizontal transaction representation? \\
     What might be reasons why it is {\em not\/} implemented that way?
\item[c)\hfill]
     \parbox[t]{100mm}{Execute the Carpenter algorithm for the
     transaction database shown on the right! Use a simple set
     as the repository, not a prefix tree as described in the
     lecture!}
\end{enumerate}\unskip}\hfill
     \begin{tabular}{@{}l@{}}
     \\
     $a$ $d$ $e$ \\
     $b$ $c$ $d$ \\
     $a$ $c$ $e$ \\
     $b$ $c$ $d$ \\
     $a$ $e$ \\
     \end{tabular}
\begin{enumerate}\itemsep0pt
\item[d)\hfill]
     How can one prune the search with minimum support
     in the Carpenter algorithm?
\end{enumerate}

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

\subsubsection*{Exercise 26 \quad\rm Carpenter Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Can perfect extension pruning be used
     in the Carpenter algorithm? If yes, how? \\
     In what way is this analogous to perfect extension
     pruning in item set enumeration algorithms
     (like Eclat, FP-Growth etc.)?
\item[b)\hfill]
     Can one use the Carpenter algorithm to find the maximal
     (frequent) item sets?
\item[c)\hfill]
     Can one use the Carpenter algorithm to find
     {\em all\/} frequent item sets?
\item[d)\hfill]
     Why is the Carpenter algorithm not advisable
     for market basket data? \\
     What kind of data is it recommendable for? Why? \\
     (Hint: Argue with the time complexity in the parameters of
     the database.)
\end{enumerate}

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

\subsubsection*{Exercise 27 \quad\rm IsTa Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     What recursive relationship does the IsTa algorithm exploit
     to find closed frequent item sets? Where lies the complexity?
\item[b)\hfill]
     Suppose the IsTa algorithm completed its work and we have the
     final prefix tree representing the repository of found closed
     frequent item sets. How are these closed item sets actually
     reported from this repository? What conditions need to be
     checked when traversing the prefix tree?
\item[c)\hfill]
     How could one report the {\em maximal\/} item sets
     from this repository? \\
     What conditions need to be checked in this case?
\item[d)\hfill]
     Why is the IsTa algorithm not advisable
     for market basket data? \\
     What data is it recommendable for? Why? \\
     (Hint: Argue with the time complexity in the parameters of
     the database.)
\end{enumerate}

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

\end{document}
