Allgemeine Aufgaben in Haskell

Sortieren

1. Quicksort
2. Mergesort
3. Insertionsort
4. Selectionsort

Suchen

5. lineares Suchen
6. binäre Suche

diverses in Haskell

7. reverse
8. Fibonacci
9. Fakultät
10. Summe einer Liste
11. map Funktion selbst schreiben
12. Binärer Suchbaum mit insert, delete, contains, sum, gib Baum als sortierte List aus...
13. Ein Stack in Haskell
14. Eine Queue in Haskell
15. Eine Menge in Haskell

Allgemeine Aufgaben in Java

1. Binärbaum - ein ziemlicher Klopper, aber man sollte das mal gemacht haben.
2. "1. Spezifizieren Sie ein Interface für einen Stack und implementieren Sie den Stack in Java mit einem Array" - Lösung
3. "1. Spezifizieren Sie ein Interface für eine Schlange und implementieren Sie die Schlange in Java mit einem Array" - Lösung

Allgemeine Aufgaben

Vollständige Induktion

1. Um das Prinzip zu verstehen: 1 + 3 + 5 + ... + (2n-1) = n², wobei n > 0.
2. x ++ [] = x, wobei (a) [] ++ v = v und (b) (a:v) ++ w = a:(v ++ w)
3. rev (a ++ b)= (rev b) ++ (rev a), wobei (a) rev [] = [] und (b) rev (a:v) = (rev v) ++ [a]
4. rev (rev xs) = xs, wobei (a) rev [] = [] und (b) rev (a:v) = (rev v) ++ [a] und (c) rev [x] = [x] und (d) [x] = x:[]

Primitiv rekursive Funktion

1. Vorgängerfunktion pred
2. Gleichheit mit Null eq0, wobei True 1 und False 0 entspricht
3. Subtraktion sub von zwei Zahlen, wobei bei Rojas x-y = sub(y, x)
4. and, not, größer-gleich ≥
5. if (x, y, z), wobei if x then y else z

O-Notation

1. Sortieren Sie die folgenden Laufzeiten aufsteigend.
   (a) n³ (b) log₂ n (c) 1,8ⁿ (d) n (e) 3ⁿ (f) √n (g) n(log₂ n)² (h) n²
2. Finden Sie möglichst einfache Ausdrücke der Form Θ(·) für folgende Funktionen:
   (a) 3n² − 4n + 32 + 27 n · ⌈log₂ n⌉ / 2
   (b) max{n⌈log₂ n⌉, (⌈log₂ n⌉)⁴}
   (c) 2^{2n + ⌈log₂ n⌉}

Algorithmen

1. Dijkstra
   a ist der Startknoten.
   
2. Kleinster aufspannender Baum
   Prim und Kruskal am obigen Graphen.
3. Huffman
   Für das Wort ABRACADABRASIMSALABIM die Wahrscheinlichkeiten der einzelnen Buchstaben bestimmen und dann einen Binärcode nach dem Huffman-Algorithmus erstellen.
4. Verschiebefunktion
   Aufstellen der Verschiebefunktion des Musters babcabb und überprüfen ob es im Text abbababcababcabbbca entghalten ist.

Graphen und Bäume

1. AVL-Baum
   Erstelle einen neuen AVL-Baum und füge folgende Werte nacheinander ein: 3, 2, 1, 4, 5, 6, 7, 16, 15
   Nun lösche die Werte 4 und 2.
2. B-Baum
   Erstelle einen neuen (2,3)-Baum und füge folgende Werte nacheinander ein: 1, 5, 2, 6, 7, 4, 8, 3
   Ich denke, dass man Löschen nicht können muss. Das ist ziemlich kompliziert!
3. Rot-Schwarz-Baum
   Wandle den folgenden Rot-Schwarz-Baum in einen einen (2,4)-Baum um.
   
   Die Grafik ist ein Screenshot von Arsen Gogeshvilis Binärbaum-Applet
4. Suffixbaum
   Erstelle einen Suffixbaum des Wortes ananas$.
5. Adjazenzliste und -matrix
   Gebe für folgenden Graphen eine Adjazenzliste und eine Adjazenzmatrix an und überlege welche Darstellung hier sinnvoller ist.
   
   Grafik entnommen aus Saake, Sattler: "Algorithmen & Datenstrukturen"
6. Konvexe Hülle
   Folgende Punkte im Koordinatenkreuz bilden einen Graphen: A(1/9), B(3/7), C(4/8), D(5/1), E(7/5), F(7/7), G(9/3), H(10/8)
   Nenne die Punkte, die in der komplexen Hülle enthalten sind.
7. Infix, Prefix und Postfix
   Folgende Terme in Pre- und Postoder darstellen.
   (a) 2 + 3 * 6 - 4 / 1
   (b) 5 * (6 + 2) - 7 / 4 + 2 * 5
   Am Einfachsten geht das mit Hilfe eines Termbaums.
   (c) Pre-, In- und Postorder von folgendem Termbaum