\documentclass[11pt,a4paper]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{stmaryrd}
\usepackage{enumerate}
%\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}
\usepackage{cancel}
\usepackage{arcs}
%\usepackage{fuzz}

\thispagestyle{empty}

\title{Softwaretechnik (WS 2005/2006) - Übungsblatt 11}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Übungsgruppe Mi, 8-10 Uhr \\
		Dirk Heine - Matrikelnummer 2030941 \\
		Übungsgruppe Di, 14-16 Uhr \\\\
		Rückgabe: Übungsgruppe Di, 14-16 Uhr
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
\begin{enumerate}
	\item \verb!rec1.equal(rec1);! \\
		Aufruf der \texttt{equal}-Methode von \verb!Rectangle! \\
		Begründung: \\
		Es wird nur die Klasse \texttt{Rectangle} verwendet. \texttt{Square} wird nicht genutzt, da man generell \texttt{Rectangle}-Objekte nicht in \texttt{Square}-Objekte umwandeln kann.
	\item
		\begin{itemize}
			\item \verb!rec1.equal(rec2);! \\
				Aufruf der \texttt{equal}-Methode von \verb!Rectangle!
			\item \verb!rec2.equal(rec1);! \\
				Aufruf der \texttt{equal}-Methode von \verb!Rectangle!
			\item \verb!rec2.equal(rec2);! \\
				Aufruf der \texttt{equal}-Methode von \verb!Rectangle!
		\end{itemize}
		Begründung: \\
		Es werden jeweils Objekte vom Typ \texttt{Rectangle} instantiiert, welche die \texttt{equal}-Methode der \texttt{Rectangle}-Klasse verwenden. Wird an \texttt{equal} ein \texttt{Square}-Objekt übergeben, wird dieses zu einem \texttt{Rectangle} umgewandelt. Dies ist deshalb ohne weiteres möglich, da \texttt{Square} von \texttt{Rectangle} abgeleitet ist.
	\item
		\begin{itemize}
			\item \verb!square.equal(rec1);! \\
				Aufruf der \texttt{equal}-Methode von \verb!Rectangle!
			\item \verb!square.equal(rec2);! \\
				Aufruf der \texttt{equal}-Methode von \verb!Rectangle!
		\end{itemize}
		Begründung: \\
		Beim Aufrufen von \texttt{square.equal(...)} wird zunächst versucht, die \texttt{equal}-Methode von \texttt{Square} aufzurufen. Da als Parameter allerdings jeweils ein Objekt vom Typ \texttt{Rectangle} (\texttt{rec1} und \texttt{rec2} wurden als \texttt{Rectangle} instantiiert) übergeben wird, muss auf die \texttt{equal}-Methode der Oberklasse \texttt{Rectangle} zurückgegriffen werden.
		\begin{itemize}
			\item \verb!rec1.equal(square);! \\
				Aufruf der \texttt{equal}-Methode von \verb!Rectangle!
			\item \verb!rec2.equal(square);! \\
				Aufruf der \texttt{equal}-Methode von \verb!Rectangle!
		\end{itemize}
		Begründung: \\
		Da \texttt{rec1} und \texttt{rec2} beide vom Typ \texttt{Rectangle} sind, wird die \texttt{equal}-Methode von \texttt{Rectangle} verwendet und das \texttt{Square}-Objekt wird in ein \texttt{Rectangle} umgewandelt und übergeben.
	\item \verb!square.equal(square);! \\
		Aufruf der \texttt{equal}-Methode von \verb!Square! \\
		Begründung: \\
		Es wird nur die Klasse \texttt{Square} verwendet. Der Zugriff auf die Klasse \texttt{Rectangle} ist nicht nötig, da das Objekt vom Typ \texttt{Square} problemlos (ohne Umwandlung) an die \texttt{equal}-Methode der Klasse \texttt{Square} übergeben werden kann.
\end{enumerate}

\section*{Aufgabe 2}
\subsubsection*{(a)}
\begin{verbatim}
qsort []     = []
qsort (x:xs) = (qsort (filter (\y -> y<=x) xs)) ++ [x] ++ 
               (qsort (filter (\y -> y>x) xs))
\end{verbatim}

\subsubsection*{(b)}
Die Verkettung von zwei Listen hat Zeitaufwand von $\OnotO(n)$, wobei $n$ die Länge der ersten Liste ist ($n = $ \texttt{length(x::xs)}). Dies ist deshalb der Fall, da die erste Liste vorne an die zweite Liste Element für Element angefügt wird. Insgesamt kommt man so auf \texttt{length(x::xs)} Einfügeoperationen.

\newpage
\section*{Aufgabe 3}
\begin{verbatim}
public class Aufgabe3 {
  public class EmptyNode implements Comparable {
    public int compareTo(Object o) {
      // da leere Knoten immer gleich sind, geben
      // wir 0 zurück
      // man könnte auch eine Exception werfen
      return 0;
    }
    
    int height() {
      // die Höhe eines leeren Knotens ist auch 0
      return 0;
    }
  }

  public class Node extends EmptyNode {
    Comparable marke;
    
    public int compareTo(Node node) {
      return node.marke.compareTo(this.marke);
    }
  }
	
  public class Tree extends Node {
    Tree left = (Tree) new EmptyNode();
    Tree right = (Tree) new EmptyNode();
		
    int height() {
      return 1 + Math.max(left.height(), right.height());
    }
		
    Tree insert(Comparable o) {
      if (this instanceof EmptyNode) {
        this.marke = o;
      } else {
        switch(this.compareTo(o)) {
        case 0:
          break;
        case -1:
          this.left = this.left.insert(o);
          break;
        case 1:
          this.right = this.right.insert(o);
          break;
        default:
          // braucht man nur zur Vollständigkeit
          // man könnte auch eine Exception werfen
        }
      }
      return this;
    }
  }
}
\end{verbatim}

\end{document}