Übungsaufgaben
1. Sortieren Sie die folgende Liste mit Quicksort Schritt für Schritt auf Papier: G = \{ 10; \ 2; \ 8; \ 19;\ 12;\ 16\}
Lösung:
2. Sortieren Sie die folgende Liste mit Mergesort Schritt für Schritt auf Papier: G = \{ 10; \ 2; \ 8; \ 19;\ 12;\ 16\}
Lösung:
3.
a) Suchen Sie mit Hilfe der binären Suche (schriftlich auf Papier) das Element x = 16 aus folgender sortierter Liste: G = \{ 2; \ 7; \ 8; \ 10;\ 12;\ 16;\ 19; \ 21}
b) Suchen Sie mit Hilfe der sequenziellen Suche (schriftlich auf Papier) das Element x = 16 aus folgender sortierter Liste: G = \{ 2; \ 7; \ 8; \ 10;\ 12;\ 16;\ 19; \ 21}
Lösung:
4. Zu Beginn unserer Vorlesung wiesen wir die Effizienz von Teile-und-Herrsche-Algorithmen mit der Meister-Methode nach. Aufgabe ist es nun, die Effizienz iterativ nachzuweisen. Folgende Aufwandsbeziehungen gelten:
T_C \left( n \right) =\begin{cases} T_A \left( n \right), & \text{wenn } \ n \ \leq \ n_0, \\ 3 \cdot T_C \left( \frac{n}{2}\right), & \text{sonst } \end{cases}Lösung:
5. Multiplizieren Sie schriftlich und ohne Taschenrechner die Zahlen 135\ 746\ 823\ 107 und 248\ 672\ 423\ 897 nach der Methode von Karatsuba. Als Basis verwenden Sie b = 10 .
Lösung: