\documentclass[11pt, a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={},
            pdfauthor={Jan Hendrik Dithmar},
            pdfsubject={},
            pdfkeywords={},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\thispagestyle{empty}

\title{Programmierung II - Übungsblatt 9 \\
	Übungsgruppe Do 14-16 \\	
	Andreas Augustin}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Dirk Heine (Matrikelnummer 2030941) \\
	Andreas Glitsch (Matrikelnummer 2026130)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}
Gegeben: $$H^{fool} = \{h_{(a,b)} : a,b \in 0...m-1\} \text{ mit } h_{(a,b)}(x) = ax + b \mod m$$
$N$ sei die Anzahl aller Schlüssel.\\
Menge $M$ von $\displaystyle \left\lfloor \frac{N}{m} \right\rfloor$ Schlüsseln für die gilt:
$$\forall x,y \in M:\forall h_{(a,b)} \in H^{fool} : h_{(a,b)}(x) = h_{(a,b)}(y)$$
Beweis:\\
\begin{eqnarray*}
	h_{(a,b)}(x) = h_{(a,b)}(y) & \Leftrightarrow & ax + b \mod m = ay + b \mod m \\
	& \Leftrightarrow & ax + b + tm = ay + b + t'm \\
	& \Leftrightarrow & ax + tm = ay + t'm \\
	& \Leftrightarrow & ax + tm - t'm = ay \\
	& \Leftrightarrow & ax + m(t - t') = ay \\
	& \Leftrightarrow & ax - ay + m(t - t') = 0 \\
	& \Leftrightarrow & a(x - y) + m(t - t') = 0 \\
	& \Leftrightarrow & a(x - y) \mod m = 0
\end{eqnarray*}

\section*{Aufgabe 2}
Problematisch bei allen Hashstrategien mit offener Adressierung ist das Löschen von Elementen. Die belegte Tabellenposition darf nicht ohne zusätzliche Vorkehrungen
freigegeben werden! \glqq Dahinterliegende\grqq\ Elemente, die aufgrund einer Kollision auf die folgenden Plätze eingefügt wurden, könnten dadurch nicht mehr erreicht werden. \\
Lösung bei linear probing: \\
Das zu löschende Element ans Ende der Hashtabelle \glqq shiften\grqq\ und dann dort löschen, da dann kein Element dem zu löschenden nachfolgt. Bei linear probing wird beim
Einfügen bei einer Kollision so lange gesucht, bis ein freies Feld gefunden wurde; Einfügen und Suchen eines Elementes sind durch das \glqq Shiften\grqq\ nicht beeinflusst.
%Zusätzliches Flag, zur Kennzeichnung ob der Tabellenplatz frei ist oder
%bereits einen Wert enthielt, der inzwischen wieder gelöscht wurde.
%
%Bei Hashing mit offener Adressierung kann es zu einer Kollision kommen, d.h., zwei verschiedene Schlüssel $k$ und $k'$ werden auf die gleiche Adresse abgebildet ($h(k) = h(k')$). \\
%Bei Auftreten einer Kollision wird bei linear probing so lange ein neuer Hashwert mit einer Linearkombination des alten Hashwertes und dem Laufindex $i$ berechnet, bis man auf ein
%freies Feld stößt. $h(k,i) = (h_{\text{alt}}(k) + i) \mod m$

\section*{Aufgabe 3}
Algorithmus zum Auswerten der Kosten von Teilnehmern aus einer Log-Datei:\\
Ich lese die Log-Datei ein und beginne mit der ersten Zeile. Die Kosten des dortigen Teilnehmers
werden zusammen mit seinem Namen in einer Zelle gespeichert. Den Namen verwende ich in einer
Suchfunktion. Bevor die Suche beginnt wird die aktuelle Zeile noch gelöscht. Ich lasse die Suchfunktion
laufen und bei jedem Treffer die dort gespeicherten Kosten in der Speicherzelle des Namens hinzuzählen.
Dann wird die Zeile gelöscht und die Suche fährt fort. Dasselbe Verfahren wende ich bei allen anderen
Treffern an, solange bis ich das EOF erreiche. Name und Kosten werden dann ausgegeben. Dann gehe ich an den
Anfang zurück, an dem jetzt ein neuer Name steht. Bei diesem wende ich dieselbe Vorgehensweise an wie schon
mit dem Vorherigen. Kosten aufsummieren, Zeile löschen, Suche fortführen bis zum EOF. Die ganze Prozedur
läuft solange die erste Zeile kein EOF ist.\\

\section*{Aufgabe 4}
\subsection*{(i)}
Pseudo-Code für die insert-Funktion des Kuckuck-hashing:
\begin {verbatim}void insert(item y)
{
  while(true)
  {
    item tmp;
    if(t_1[h_1(y)] != leer)
    {
      tmp = t_1[h_1(y)];
      t_1[h_1(y)] = y;
    }
    else
    {
      t_1[h_1(y)] = y;
      return;
    }
    if(t_2[h_2(tmp)] != leer)
    {
      y = t_2[h_2(tmp)];
      t_2[h_2(tmp)] = tmp;
    }
    else
    {
      t_2[h_2(tmp)] = tmp;
      return;
    }
  }
}
\end{verbatim}

\subsection*{(ii)}
Die insert-Funktion könnte endlos laufen, wenn keine freie Speicherzelle gefunden wird. Dies kann z.B. passieren, wenn beide Arrays $t_1$ und $t_2$ voll sind und darauf die insert-Funktion angewendet wird.

\section*{Aufgabe 5}
Beweis: \\
Sei $x$ Knoten des Baumes, dann gilt für jeden Knoten $y$
\begin{itemize}
	\item im linken Unterbaum von $x$: $y.key \le x.key$
	\item im rechten Unterbaum von $x$: $y.key \ge x.key$
\end{itemize}
D.h., dass alle Elemente, die kleiner gleich der Wurzel sind, links vom aktuellen Knoten eingefügt werden und alle Elemente großer gleich der Wurzel rechts davon. \\
Für $n=0$ macht \verb!tree_walk! garnichts. \\[0.3cm]
{\bfseries Induktionsanfang:} $n=1$ \\
$n=1 \Leftrightarrow$ Baum besteht nur aus Wurzel. \\
Die Zeiger \verb!left_child! und \verb!right_child! zeigen auf \verb!NULL!, d.h. die Aufrufe von \verb!tree_walk! für linkes und rechtes Kind machen nichts (vgl. Fall $n=0$). Somit wird
der Baum korrekt sortiert ausgegeben. \\
Bemerkung: Dies ist der Fall, wenn ein (Unter-)Baum keine Kinder hat. \\[0.3cm]
{\bfseries Induktionsannahme:} Die Aussage gilt für alle natürlichen Zahlen $n$. \\[0.3cm]
{\bfseries Induktionsschluss:} $n \leadsto n+1$ \\
Einem Baum mit $n$ Knoten wird 1 Element hinzugefügt. \verb!tree_insert! aus der Vorlesung behält die Eigenschaften des Suchbaums beim Einfügen bei, d.h., der neue Knoten wurde an der richtigen Stelle eingefügt.
Da \verb!tree_walk! zuerst rekursiv den linken Teilbaum hinabsteigt, bekommt man hier das kleinste Element im Baum. Falls kein linker Teilbaum (mehr) vorhanden ist,
gibt \verb!tree_walk! den aktuellen Knoten aus (kleinstes Element im linken Teilbaum), steigt auf und geht rekursiv in den jeweils rechten Teilbaum. Ist in diesem ein linker Unterbaum
vorhanden, so arbeitet die Prozedur wie oben bereits beschrieben. Der rekursive Abstieg im rechten Teilbaum liefert (am Ende) das größte Element im Baum. Ist kein rechter Teilbaum
(mehr) vorhanden, gibt \verb!tree_walk! das aktuelle Element aus (größtes Element im Baum). \\
Somit gilt für jeden ausgegebenen Knoten $k$:
$$k_i \leq k_j \quad \forall i<j$$
und der Baum ist sortiert ausgegeben. \QED

\section*{Aufgabe 6}
Das Löschen im binären Suchbaum ist kommutativ. \\
{\bfseries Begründung:} \\
Fallunterscheidung:
\begin{enumerate}[1.]
	\item Fall: {\bfseries Die zu löschenden Knoten $x$ und $y$ sind Blätter} \\
		Hier ist es offensichtlich, dass die Reihenfolge bei der Löschung keine Rolle spielt.
	\item Fall: {\bfseries Einer der Knoten ist ein Blatt, der andere ist Teil eines Teilbaums} \\
		Bei der Löschung von einem Knoten wird der Baum so umsortiert, dass vorherige Blätter danach immernoch Blätter sind. Somit spielt es keine Rolle, ob das Blatt zuerst oder
		an zweiter Stelle gelöscht wird. Auf den Teilbaum hat die Reihenfolge ebenfalls keine Auswirkung, da die Struktur des Teilbaums bis auf das Verschieben des kleinsten Elementes
		an die Stelle der Wurzel ebenfalls erhalten bleibt.
	\item Fall: {\bfseries Beide zu löschenden Knoten $x$ und $y$ sind Teil eines Teilbaums} \\
		Wie oben gesagt wird die Struktur des Teilbaums bis auf das Verschieben des kleinsten Elements an die Stelle der Wurzel nicht verändert. Ob dabei zuerst
		$x$ und dann $y$ gelöscht wird oder umgekehrt spielt keine Rolle, da bei jeder Löschung nur das kleinste Element verschoben wird und ggf. die Kinder dieses Elements
		\glqq nachrücken\grqq .
\end{enumerate}

\end{document}
