\documentclass[a4paper,12pt]{scrartcl}
\usepackage[ngerman]{babel}
\usepackage{graphicx} %BIlder einbinden
\usepackage{amsmath} %erweiterte Mathe-Zeichen
\usepackage{amsfonts} %weitere fonts
\usepackage[utf8]{inputenc} %Umlaute & Co
\usepackage{hyperref} %Links
\usepackage{ifthen} %ifthenelse
\usepackage{enumerate}
\usepackage{listings}
\lstset{language=Python}

\usepackage{algpseudocode} %Pseudocode
\usepackage{dsfont} % schöne Zahlenräumezeichen
\usepackage{amssymb, amsthm} %noch stärker erweiterte Mathe-Zeichen
\usepackage{tikz} %TikZ ist kein Zeichenprogramm
\usetikzlibrary{trees,automata,arrows,shapes}

\pagestyle{empty}


\topmargin-50pt

\newcounter{aufgabe}
\def\tand{&}

\newcommand{\makeTableLine}[2][0]{%
  \setcounter{aufgabe}{1}%
  \whiledo{\value{aufgabe} < #1}%
  {%
    #2\tand\stepcounter{aufgabe}%
  }
}

\newcommand{\aufgTable}[1]{
  \def\spalten{\numexpr #1 + 1 \relax}
  \begin{tabular}{|*{\spalten}{p{1cm}|}}
    \makeTableLine[\spalten]{A\theaufgabe}$\Sigma$~~\\ \hline
    \rule{0pt}{15pt}\makeTableLine[\spalten]{}\\
  \end{tabular}
}

\def\header#1#2#3#4#5#6#7{\pagestyle{empty}
\begin{minipage}[t]{0.47\textwidth}
\begin{flushleft}
{\bf #4}\\
#5
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushright}
#6 \vspace{0.5cm}\\
%                 Number of Columns    Definition of Columns      second empty line
% \begin{tabular}{|*{5}{C{1cm}|}}\hline A1&A2&A3&A4&$\Sigma$\\\hline&&&&\\\hline\end{tabular}\\\vspace*{0.1cm}
\aufgTable{#7}
\end{flushright}
\end{minipage}
\vspace{1cm}
\begin{center}
{\Large\bf Sheet #1}

{(Hand in #3)}
\end{center}
}



%counts the exercisenumber
\newcounter{n}

%Kommando für Aufgaben
%\Aufgabe{AufgTitel}{Punktezahl}
\newcommand{\Aufgabe}[2]{\stepcounter{n}
    \textbf{Exercise \arabic{n}: #1} (#2 Points)}


\begin{document}
    %\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben}
    \header{8}{}{2015-07-02}{Intelligent Systems I}{\textit{Maximus Mutschler}\\ \textit{Jan-Peter Hohloch}
    }{SS 15}{4}
    \vspace{1cm}
    \Aufgabe{Kidney Stones}{25}
        \begin{align*}
            P(\text{large stone})&=\frac{343}{343+357}=0.49\\
            P_A(R=1)&=\sum\limits_Z P(R=1|Z=z,T=A)P(Z=z)\\
            &=0.73\cdot 0.49 + 0.93\cdot 0.51\approx 0.832\\
            P_B(R=1)&=\sum\limits_Z P(R=1|Z=z,T=B)P(Z=z)\\
            &=0.69\cdot 0.49 + 0.87\cdot 0.51\approx 0.782
        \end{align*}
        (Formula from the lecture)\\
    \Aufgabe{PC}{25}
        \begin{itemize}
            \item Assume X and Y are directly connected.\\
            There can't exists a set d-seperating them, because they are always linked over the direct connection.\checkmark
            \item Assume X,Y are not directly connected, i.e. $X\not\in N(Y)\wedge Y\not\in N(X)$.\\
            Any non-direct path between X and Y can be blocked:\begin{itemize}
                \item directed paths are blocked by taking one of the intermediate nodes in the separation set
                \item common ancestors can also be blocked
                \item common descendants are not taken in the separation set
            \end{itemize}
            Because the graph is acyclic each path belongs clearly to one of the above categories and so can be blocked.\\
            \textcolor{red}{If nodes are not connected at all they're ``blocked'' by any set.}
        \end{itemize}
    \Aufgabe{IC}{25}\\
        \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto, node distance=2cm]
                \node[circle, draw] (A) {A};
                \node[circle, draw] (B) [right of=A] {B};
                \node[circle, draw] (C) [below of=A] {C};
                \node[circle, draw] (D) [below of=B] {D};

                \draw (A) -- (B);
                \draw (B) -- (D);
                \draw (C) -- (D);
                \draw (A) -- (C);
            \end{tikzpicture}
            \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto, node distance=2cm]
                \node[circle, draw] (A) {A};
                \node[circle, draw] (B) [right of=A] {B};
                \node[circle, draw] (C) [below of=A] {C};
                \node[circle, draw] (D) [below of=B] {D};

                \draw (B) -- (A);
                \draw (B) -- (D);
                \draw (C) -- (D);
                \draw (A) -- (C);
            \end{tikzpicture}
            \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto, node distance=2cm]
                \node[circle, draw] (A) {A};
                \node[circle, draw] (B) [right of=A] {B};
                \node[circle, draw] (C) [below of=A] {C};
                \node[circle, draw] (D) [below of=B] {D};

                \draw (A) -- (B);
                \draw (B) -- (D);
                \draw (C) -- (D);
                \draw (C) -- (A);
            \end{tikzpicture}\\
    \Aufgabe{IC Performance}{25}\\
        \begin{itemize}
            \item worst case:\\
                All nodes are dependent of each other, so it has to check all possible subsets (the powerset) for all pairs of nodes:
                $$\frac{p\cdot (p-1)}{2}\cdot 2^{p-2}\in\mathcal{O}(2^p)$$
                \begin{tikzpicture}[auto, node distance=2cm]
                \node[circle, draw] (A) {A};
                \node[circle, draw] (B) [right of=A] {B};
                \node[circle, draw] (C) [below of=A] {C};
                \node[circle, draw] (D) [below of=B] {D};

                \draw (A) -- (B);
                \draw (A) -- (D);
                \draw (B) -- (D);
                \draw (B) -- (C);
                \draw (C) -- (D);
                \draw (C) -- (A);
            \end{tikzpicture}\\
            \item best case:\\
                first test shows independence, so we need only one test per pair:
                $$\frac{p\cdot (p-1)}{2}\cdot 1\in\mathcal{O}(p^2)$$
                \begin{tikzpicture}[auto, node distance=2cm]
                \node[circle, draw] (A) {A};
                \node[circle, draw] (B) [right of=A] {B};
                \node[circle, draw] (C) [below of=A] {C};
                \node[circle, draw] (D) [below of=B] {D};
            \end{tikzpicture}\\
        \end{itemize}
\end{document}

