# Algorithmen und Datenstrukturen: Blatt 1

## Aufgabe 1

Gegeben sei folgender Algorithmus:


#### 1a)

Angewandt auf das Array $[24|5|6|23|42|45|2|1|8]$ ergibt sich nach dem:

1. Durchgang: $[1|5|6|23|42|45|2|24|8]$
2. Durchgang: $[1|2|6|23|42|45|5|24|8]$
3. Durchgang: $[1|2|5|23|42|45|6|24|8]$
4. Durchgang: $[1|2|5|6|42|45|23|24|8]$
5. Durchgang: $[1|2|5|6|8|45|23|24|42]$
6. Durchgang: $[1|2|5|6|8|23|45|24|42]$
7. Durchgang: $[1|2|5|6|8|23|24|45|42]$
8. Durchgang: $[1|2|5|6|8|23|24|42|45]$

#### 1b)

0. Schleifeninvariante:
$j\leq n-1$ und die Elemente $1,...,j+1$ im Array sind sortiert.
1. Initialisierung:
Für $n = 1$ gilt:
Das Array ist bereits sortiert und
die Schleife in Zeile 2 wird nicht betreten.
Deshalb gehen wir für den weiteren Beweis von $n \geq 2$ aus.
Beim ersten Schleifendurchlauf gilt $j = 1 \leq n-1$.
Diese Aussage trifft zu für $n \geq 2$.
Die Variable *smallest* soll immer auf das kleinste Element zeigen.
Dies wird in den Zeilen 4 und 5 erreicht (Beweis folgt).
In Zeile 6 wird der Wert an der Stelle $j$ im Array
mit dem an der Stelle $smallest$ ausgetauscht.
Wenn nun aber $smallest$ immer auf das
kleinste Element im unsortierten Teil des Arrays zeigt,
wandert genau dieses kleinste Element an die Stelle $j$.
Im ersten Durchlauf ist $j=1$.
Das bedeutet, dass das kleinste Element an die erste Stelle im Array getauscht wird.
Damit gilt: $A[1] \leq A[2]$.
2. Aufrechterhaltung:
Bei weiteren Durchläufen wird (wie oben beschrieben)
immer kleinste Element $A[smallest]$ des unsortieren Teils des Array nach vorne,
an die erste Stelle des unsortierten Teils ($A[j]$) gesetzt und
damit genau hinter den bereits sortierten Teil.
Damit gilt: $A[j] \leq A[j+1]$.
Das kleinste Element des unsortierten Teils ist aber größer
als das größte Element des sortierten Bereichs ($A[j-1]$),
da im Durchlauf zuvor jeweils das kleinste Element einsortiert wurde.
Daraus folgt, dass das kleinste Element des unsortierten Teils
am Ende des Durchlaufs das größte Element des sortierten Teils ist.
Da das Element $j+1 \geq j$ gilt, dass die Elemente $A[1],A[2],...,A[j+1]$ sortiert sind.

3. Terminierung:
Die Schleife endet nach dem $j = n-1$. Durchgang.
Die Schleifeninvariante terminiert also in dem Moment,
in dem auch die Schleife endet.
Da die Elemente $A[1],A[2],...,A[j+1]$ nach jedem Durchgang sortiert sind
(siehe 2.) und $j+1 = n$ gilt, sind alle $n$ Elemente sortiert,
sobald die Schleife fertig durchlaufen ist.

Zu den Zeilen 4 und 5:
Zu zeigen ist, dass die Variable $smallest$ nach jedem Schleifendurchlauf
auf das kleinste Element im Teilarray von $A[j+1]$ bis $A[n]$ zeigt,
also dass $A[smallest]$ das kleinste Element in dem beschriebene Bereich ist.

#### 1c)

- Best-Case:

| Zeile | Kosten | Anzahl der Ausführungen |
| ----- | ------ | ----------------------- |
| 1 | 1 | 1 |
| 2 | 1 | n-1 |
| 3 | 1 | n-1 |
| 4 | 1 | $\sum_{i=1}^{n-1} i$ |
| 5 | 1 | $(\sum_{i=1}^{n-1} i)-1$|
| 6 | 1 | n-1 |

- Worst-Case:

| Zeile | Kosten | Anzahl der Ausführungen |
| ----- | ------ | ----------------------- |
| 1 | 1 | 1 |
| 2 | 1 | n-1 |
| 3 | 1 | n-1 |
| 4 | 1 | $\sum_{i=1}^{n-1} i$ |
| 5 | 1 | $(\sum_{i=1}^{n-1} i)-1$|
| 6 | 1 | n-1 |

$T(n) = 1 + (n-1) + (n-1) + \sum_{i=1}^{n-1} i + (\sum_{i=1}^{n-1} i)-1 + (n-1)$
$= 1 + 3(n-1) +\sum_{i=1}^{n-1} i + (\sum_{i=1}^{n-1} i)-1 =$
$=3(n-1) +\sum_{i=1}^{n-1} i + (\sum_{i=1}^{n-1} i)=
3(n-1) +2*(\sum_{i=1}^{n-1} i)$
$= 3(n-1) + 2*\frac{n(n-1)}{2} \Leftrightarrow T(n) \in \Theta(n^2)$

#### 1d)

- InsertionSort:
Best-Case : $an+b \in \Theta(n)$
Worst-Case: $an^2+bn+c \in \Theta (n^2)$
- SelectionSort:
Best-Case: $T(n) \in \Theta(n^2)$
Worst-Case: $T(n) \in \Theta(n^2)$

Im Best-Case würden wir InsertionSort bevorzugen,
da sich die Laufzeit linear und bei SelectionSort quadratisch erhöht.
Im Worst-Case verhalten sich beide Laufzeiten gleich,
weshalb hier die Bevorzugung dem Programmierer selbst überlassen ist,
wenn dieser dies über die Laufzeit entscheidet.

## Aufgabe 2

#### 2a)

Der Algorithmus soll den ersten und den letzten Buchstaben vergleichen,
sind die beiden gleich, dann den zweiten und den vorletzten, usw
bis er in der Mitte angekommen ist.
Sobald einmal $false$ rauskommt,
ist das Wort kein Palindrom und der Algorithmus soll ein $false$ ausgeben.

#### 2b)

boolean Palindrom(char [] wort)
    n = wort.length
    o = 1
    bool ergebnis = true
    while (o <= n && ergebnis)
        if(wort[o] == wort[n])
            n = n-1
            o = o+1
        else
            ergebnis = false
    return ergebnis

## Verbesserung:

#### Aufgabe 1b) Schleifeninvariante
Invariante muss immer nach Ausführung des Schleifenkopfes gelten.
Schleifeninvariante: Zu Beginn der Iteration besteht das Teilarray A[1 ... j-1]
aus den j-1 kleinsten Elementen und dieses Teilarray ist sortiert.
Außerdem enthält das Teilarray die gleichen Elemente wie zuvor.

1. Initialisierung:
j = 1. Das Teilarray besteht aus den 0 kleinsten Elementen und diese sind sortiert.
2. Aufrechterhaltung:
Wenn Invariante zu Beginn erfüllt ist, tauscht der Algor.
Das kleinste Element im Teil-Array A[j...n],
sodass es am Ende an der Stelle A[j] steht. A[1...j-1]: kleinste Elemente und sortiert.
--> A[1...j] ist sortiert.
3. Terminierung:
Nach den ersten n-1 Iterationen enthält das Array A[1...n-1] die kleinsten n-1 Elemente
und ist sortiert.
Daher muss A[n] das größte Element sein.
--> A[1...n] ist sortiert und enthält die kleinsten Elemente.

#### Aufgabe 1c) Laufzeitanalyse

| Zeile | Kosten | Anzahl der Ausführungen |
| ----- | ------ | -------------------------- |
| 1 | 1 | 1 |
| 2 | 1 | n |
| 3 | 1 | n-1 |
| 4 | 1 | $\sum_{i=1}^{n-1} )n-i+1)$ |
| 5 | 1 | $(\sum_{i=1}^{n-1} n-i)$ |
| 6 | 1 | n-1 |

###### tags: `Algorithmen und Datenstrukturen` `Informatik` `Uni`