---
# System prepended metadata

title: AlgoDat Tutorium 3
tags: [Algorithmen und Datenstrukturen, Informatik, Uni]

---

# AlgoDat Tutorium 3

## Aufgabe 1

Rekursionsgleichung: $T(n)=2 \cdot T(n/2) + n$

### 1a)

Behauptung: $\exists c > 0$, sodass gilt: $T(n) \leq c \cdot n \cdot log(n)$  
T(1)?  
Induktionsannahme: $T(k) \leq c \cdot k \cdot log(k), k<n$  
Induktionsschluss:  
$T(n)=2 \cdot T(n/2) + n$  
$\leq 2c \cdot n/2 \cdot log(n/2) +n$
$=cn \cdot (log_2 n - log_2 2)+n = cn \cdot log_2 n - cn + n = cn \cdot log_2 n + n(1-c)$
$\leq cn\cdot log_2 n$ für $c \geq 1$.

### 1b)

![Rekursionsbaum](https://i.imgur.com/1x4t9dD.png)

| Ebene    | Knotenanzahl | Beitrag                |
| -------- | ------------ | ---------------------- |
| $0$      | $2^0 = 1$    | $n$                    |
| $1$      | $2^1 = 2$    | $\frac{n}{2}$          |
| $2$      | $2^2 = 4$    | $\frac{n}{4}$          |
| ...      | ...          | ...                    |
| $i$      | $2^i$        | $\frac{n}{2^i}$         |
| ...      | ...          | ...                    |
| $log_2n$ | $2^{log_2n}$ | $\frac{n}{2^{log_2n}}$ |

$T(n) = 1+ \sum_{i=0}^{(log_2n)-1}\frac{n}{2^i}
\leq 1+n \cdot \sum_{i=0}^{\infty} (\frac{1}{2})^i =
1+2n$ (, da $x^i=\frac{1}{1-x}$)  
$\Rightarrow T \in O(n)$

### 1c)

$a = 2, b = 2, f(n) = n$  
$\Rightarrow$ Fall 2: $f \in \Theta n^{log_2 2} = n$  
$\Rightarrow: T(n) \in \Theta(n \cdot log n)$

## Aufgabe 2

### 2a)

![Teil 1](https://i.imgur.com/AJnSLF2.jpg)
![Teil 2](https://i.imgur.com/QWlpHRU.png)

### 2b)

$T(n) = 2T(n-1) + a$  
$a :=$ Laufzeit von MoveDiskOnTopFromTo$(S_1, S_3)$

### 2c)

Induktionsanfang: $n = 1$:
move(0, s1, s3, s2)
moveTop(s1, s3)
--> wandert auf s3
move(0, s2, s1, s3)
offensichtlich richtig

Induktionsannahme: Gilt für k < n Scheiben.
Induktionsschluss: n = k+1

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