Übungsaufgaben
Um sich die einzelnen Verfahren zu verdeutlichen, sind folgende Aufgaben zu lösen.
1. Sortieren Sie die folgende Menge mit Quicksort Schritt für Schritt auf Papier: G = \{ 10; \ 2; \ 8; \ 19;\ 12;\ 16\}
Lösung: Quicksort.pdf
2. Sortieren Sie die folgende Menge mit Mergesort Schritt für Schritt auf Papier: G = \{ 10; \ 2; \ 8; \ 19;\ 12;\ 16\}
Lösung: Mergesort.pdf
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: