\documentclass[a4paper,10pt]{scrartcl}
\setlength{\topmargin}{-2cm}
\setlength{\oddsidemargin}{-1cm}
\setlength{\evensidemargin}{-1cm}
\setlength{\textwidth}{18cm}
\setlength{\textheight}{24cm}
\setlength{\delimitershortfall}{0cm}

\usepackage[active]{srcltx}
\usepackage[german]{babel}
\usepackage[utf8]{inputenc}
\usepackage[pdftex,a4paper,colorlinks=true,linkcolor=black]{hyperref}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{graphicx}
%\usepackage{trfsigns}
\usepackage[usenames]{color}
\usepackage{listings}

% Shortcuts für Matrizen, '&' und '\\' gelten wie gewohnt
\newcommand{\mtrx}[1]{\begin{matrix}#1\end{matrix}} % ( normal Matrix )
\newcommand{\smtrx}[1]{\begin{smallmatrix}#1\end{smallmatrix}} % ( small Matrix )
\newcommand{\pmtrx}[1]{\begin{pmatrix}#1\end{pmatrix}}	% ( (...) )
\newcommand{\bmtrx}[1]{\begin{bmatrix}#1\end{bmatrix}}	% ( [...] )
\newcommand{\Bmtrx}[1]{\begin{Bmatrix}#1\end{Bmatrix}}	% ( {...} )
\newcommand{\e}{\text{e}}
\newcommand{\im}{\text{i}}

% code box
\setlength{\fboxrule}{1.2pt}
%\definecolor{codeFrame}{rgb}{0.1,0.1,0.1}
\definecolor{codeBg}{rgb}{0.96,0.96,0.96}
%\definecolor{codeFg}{rgb}{0.2,0.2,0.2}
%\definecolor{brown}{rgb}{0.6,0.3,0.3}
\definecolor{grey}{rgb}{0.4,0.4,0.4}
%\newcommand{\codebox}[1]{\fcolorbox{codeFrame}{codeBg}{\texttt{#1}}}
%\newcommand{\code}[2][codeFg]{\codebox{\textcolor{#1}{#2}}}

% paragraph settings, http://docutils.sourceforge.net/docs/user/latex.html
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}

\lstset{% general command to set parameter(s)
    basicstyle=\footnotesize,          % print whole listing small
    keywordstyle=\color{black}\ttfamily,
                                % underlined bold black keywords
    identifierstyle=,           % nothing happens
    commentstyle=\color{grey}, % white comments
    stringstyle=\color{brown}\ttfamily,      % typewriter type for strings
    showstringspaces=false,     % no special string spaces
    backgroundcolor=\color{codeBg},%
    framerule=0pt,%
    frame=single,%
    float=h,%
    extendedchars=true}
\lstset{language=C++}
\lstset{tabsize=2}

%opening
\title{Algorithmen und Datenstrukturen}
\author{Franz Brauße}

\begin{document}
%\maketitle
\tableofcontents

\section{Probeklausur}
\subsection{Aufgabe 1}
Zu zeigen:
\[ \lim_{n \to \infty} \frac{f(n)}{g(n)} = c, \; 0<c<\infty \Rightarrow f(n) \in \Theta(g(n)) \]

\begin{eqnarray*}
	\lim_{n\to\infty} \frac{f(n)}{g(n)} &=& c \\
	\Rightarrow \lim_{n\to\infty} f(n) &=& c \cdot \lim_{n\to\infty} g(n) \\
	\Rightarrow |\lim_{n\to\infty} f(n)| &=& | c \cdot \lim_{n\to\infty} g(n)|
\end{eqnarray*}
Daraus folgt 
\begin{align*}
	\exists M, n_0 \in \mathbbm N, M \geq c \colon \forall n \leq n_0 \colon && \wedge && \exists M',n_0' \in \mathbbm N, M' \leq \frac{1}{c} \colon \forall n \geq n_0' \colon \\
	\begin{array}{rr@{\extracolsep{2pt}}c@{\extracolsep{2pt}}l}
		& |f(n)| &\leq& |M\cdot g(n)| \\
		\Rightarrow & f &\in& \mathcal O(g)
	\end{array} && \wedge &&
	\begin{array}{rr@{\extracolsep{2pt}}c@{\extracolsep{2pt}}l}
		& |f(n)| &\geq& |\frac{1}{M'}\cdot g(n)| \\
		\Rightarrow & |M' \cdot f(n)| &\geq& |g(n)| \\
		\Rightarrow & |g(n)| &\leq& |M' \cdot f(n)| \\
		\Rightarrow & g &\in& \mathcal O(f) \\
		\Rightarrow & f &\in& \Omega(g) \\
	\end{array}
\end{align*}
Da $f \in \Omega(g) \wedge f \in \mathcal O(g) \Rightarrow f \in \Theta(g)$

\subsection{Aufgabe 2}
\subsubsection*{1)}
\begin{tabular}{ll}
	\begin{minipage}{160pt}
		\begin{lstlisting}
struct ListElem {
	int data;
	ListElem *next, *prev;
};
		\end{lstlisting}
	\end{minipage} &
	\begin{minipage}{160pt}
		\begin{lstlisting}
struct DynamicLinkedList {

	ListElem *head, *tail;
};
		\end{lstlisting}
	\end{minipage}
\end{tabular}

\begin{tabular}{ll}	\begin{minipage}{160pt}		\begin{lstlisting}
void pushfront(int x) {
	ListElem *e = new ListElem;
	e->data = x;
	if (head == NULL) {
		head = tail = e;
	} else {
		e->next = head;
		head->prev = e;
		head = e;
	}
}
		\end{lstlisting}	\end{minipage} &	\begin{minipage}{160pt}		\begin{lstlisting}
int popfront() {
	ListElem *e = head;
	int r = e->data;
	head = e->next;
	head->prev = NULL;
	delete e;
	return r;
}
		\end{lstlisting}	\end{minipage}\end{tabular}

\subsubsection*{2)}
\begin{tabular}{ll}	\begin{minipage}{110pt}		\begin{lstlisting}
int size() {
	int r = 0;
	ListElem *e = head;
	while (e != NULL) {
		r++;
		e = e->next;
	}
	return r;
}
\end{lstlisting}	\end{minipage} &	\begin{minipage}{250pt}		\begin{lstlisting}
DynamicLinkedList*[] splithalf() {
	if (head == NULL)
		return new DynamicLinkedList*[2];
	
	DynamicLinkedList *l1 = new DynamicLinkedList;
	DynamicLinkedList *l2 = new DynamicLinkedList;
	l1->head = head; l1->tail = head;
	l2->tail = tail; l2->head = tail;
	
	while (l1->tail != l2->head->prev &&
	       l1->tail->next != l2->head->prev) {
		l1->tail = l1->tail->next;
		l2->head = l2->head->prev;
	}
	l1->tail->next = NULL;
	l2->head->prev = NULL;
	return new DynamicLinkedList*[] { l1, l2 };
}
\end{lstlisting}	\end{minipage}\end{tabular}

\subsubsection*{3)}
\begin{lstlisting}
DynamicLinkedList *merge(DynamicLinkedList *l1, DynamicLinkedList *l2) {
	if (l1->head == NULL) return l2;
	if (l2->head == NULL) return l1;
	
	DynamicLinkedList *l = new DynamicLinkedList;
	ListElem *e1 = l1->head;
	ListElem *e2 = l2->head;
	l->head = new ListElem;
	if (e1->data <= e2->data) {
		l->head->data = e1->data;
		e1 = e1->next;
	} else {
		l->head->data = e2->data;
		e2 = e2->next;
	}
	l->tail = l->head;
	
	while (e1 != NULL && e2 != NULL) {
		ListElem *e = new ListElem;
		e->prev = l->tail;
		l->tail->next = e;
		l->tail = e;
		if (e1->data <= e2->data) {
			e->data = e1->data;
			e1 = e1->next;
		} else {
			e->data = e2->data;
			e2 = e2->next;
		}
	}
	
	ListElem *e0 = (e1 == NULL) ? e2 : e1;
	while (e0 != NULL) {
		ListElem *e = new ListElem;
		e->prev = l->tail;
		l->tail->next = e;
		l->tail = e;
		e->data = e0->data;
		e0 = e0->next;
	}
	
	return l;
}
\end{lstlisting}

\subsubsection*{4)}
\begin{lstlisting}
DynamicLinkedList *mergesort(DynamicLinkedList *l) {
	if (l->size() <= 1)
		return l;
	DynamicLinkedList*[] lists = l->splithalf();
	return merge(mergesort(lists[0]), mergesort(lists[1]));
}
\end{lstlisting}

\subsection{Aufgabe 3}
\[ p := \text{Pivot}, i := \text{Linker Zeiger}, j := \text{Rechter Zeiger} \]
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
	\hline
	5 & 3 & 17 & 10 & 84 & 19 & 6 & 22 & 9 \\ \hline
	$\stackrel{\uparrow}{p}$ & $\stackrel{\uparrow}{j}$ & $\stackrel{\uparrow}{i}$ &&&&&& \\ \hline
	\hline
	3 & 5 & 17 & 10 & 84 & 19 & 6 & 22 & 9 \\ \hline
	$\surd$ & $\stackrel{\uparrow}{p, j}$ & $\stackrel{\uparrow}{i}$ &&&&&& \\ \hline
	\hline
	3 & 5 & 17 & 10 & 84 & 19 & 6 & 22 & 9 \\ \hline
	$\surd$ & $\surd$ & $\stackrel{\uparrow}{p}$ && $\stackrel{\uparrow}{i}$ &&&& $\stackrel{\uparrow}{j}$ \\ \hline
	\hline
	3 & 5 & 17 & 10 & 9 & 19 & 6 & 22 & 84 \\ \hline
	$\surd$ & $\surd$ & $\stackrel{\uparrow}{p}$ &&& $\stackrel{\uparrow}{i}$ & $\stackrel{\uparrow}{j}$ && \\ \hline
	\hline
	3 & 5 & 17 & 10 & 9 & 6 & 19 & 22 & 84 \\ \hline
	$\surd$ & $\surd$ & $\stackrel{\uparrow}{p}$ &&& $\stackrel{\uparrow}{j}$ & $\stackrel{\uparrow}{i}$ && \\ \hline
	\hline
	3 & 5 & 6 & 10 & 9 & 17 & 19 & 22 & 84 \\ \hline
	$\surd$ & $\surd$ & $\stackrel{\uparrow}{p_1, j_1}$ & $\stackrel{\uparrow}{i_1}$ && $\surd$ & $\stackrel{\uparrow}{p_2, j_2}$ & $\stackrel{\uparrow}{i_2}$ & \\ \hline
	\hline
	3 & 5 & 6 & 10 & 9 & 17 & 19 & 22 & 84 \\ \hline
	$\surd$ & $\surd$ & $\surd$ & $\stackrel{\uparrow}{p_1}$ & $\stackrel{\uparrow}{i_1, j_1}$ & $\surd$ & $\surd$ & $\stackrel{\uparrow}{p_2, j_2}$ & $\stackrel{\uparrow}{i_2}$ \\ \hline
	\hline
	3 & 5 & 6 & 9 & 10 & 17 & 19 & 22 & 84 \\ \hline
	$\surd$ & $\surd$ & $\surd$ & $\surd$ & $\surd$ & $\surd$ & $\surd$ & $\surd$ & $\surd$ \\ \hline
\end{tabular}

\subsection{Aufgabe 4}

\subsection{Aufgabe 5}
\begin{lstlisting}
TreeNode *createTree(int[] a, int n) {
	return createTree(a, 0, n);
}

TreeNode *createTree(int[] a, int l, int r) {
	if (l > r) return NULL;
	TreeNode *n = new TreeNode;
	int m = (l + r + 1) / 2;
	n->data = a[m];
	n->left = createTree(a, l, m - 1);
	n->right = createTree(a, m + 1, r);
	return n;
}
\end{lstlisting}
\begin{lstlisting}
TreeNode *lookup(Tree *t, int x) {
	TreeNode *n = t->root;
	while (n != NULL && n->data != x) {
		if (n->data < x)   n = n->left;
		else               n = n->right;
	}
	return n;
}
\end{lstlisting}

\subsection{Aufgabe 6}

\subsection{Aufgabe 7}
\[ \begin{array}{c@{\!\!\!}c@{\!\!\!}c@{\!\!\!}c@{\!\!\!}c@{\!\!\!}c|l|c@{\qquad}c}
	 \to a &&&&&&& \text{\texttt{dfsnum}}[a] = 1 & \text{\texttt{compnum}}[a] = 8 \\
	& \to b &&&&&& \text{\texttt{dfsnum}}[b] = 2 & \text{\texttt{compnum}}[b] = 7 \\
	&& \to c &&&&& \text{\texttt{dfsnum}}[c] = 3 & \text{\texttt{compnum}}[c] = 5 \\
	&&& \to d &&&& \text{\texttt{dfsnum}}[d] = 4 & \text{\texttt{compnum}}[d] = 2 \\
	&&&& \to c && \text{bekannt} \\
	&&&& \to h &&& \text{\texttt{dfsnum}}[h] = 5 & \text{\texttt{compnum}}[h] = 1 \\
	&&& \to g &&&& \text{\texttt{dfsnum}}[g] = 6 & \text{\texttt{compnum}}[g] = 4 \\
	&&&& \to f &&& \text{\texttt{dfsnum}}[f] = 7 & \text{\texttt{compnum}}[f] = 3 \\
	&&&&& \to g & \text{bekannt} \\
	&&&& \to h && \text{bekannt} \\
	&& \to f &&&& \text{bekannt} \\
	&& \to e &&&&& \text{\texttt{dfsnum}}[e] = 8 & \text{\texttt{compnum}}[e] = 6 \\
	&&& \to f &&& \text{bekannt} \\
	&&& \to a &&& \text{bekannt}
\end{array} \]


\end{document}
