Zusammenfassung teil1

Question 1

Arrays und Listen vergleich;

Answer 1

Beliebiges Element suchen: Array Θ(n), List Θ(n)
Auf Element mit Index i zugreifen: Array Θ(1), List Θ(n)
Element am Anfang einfugen: Array Θ(n), List Θ(1)

Question 2

Bubblesort

Answer 2

Laufzeit liegt im Worst- und Average-Case in Θ(n^2). Im
Best-Case kann die Laufzeit bei optimierten
Implementierungen in Θ(n) liegen.

Question 3

Selectionsort:

Answer 3

(nicht stabil) Selectionsort sucht in jeder Iteration das kleinste
Element in der noch unsortierten Teilfolge, entnimmt es und fügt es dann an die sortierte Teilfolge an.

Laufzeit/Vergleiche: Die Laufzeit liegt immer (Best/Average/Worst-Case) in Θ(n^2).

Vertauschungen immer Θ(n)

Question 4

Insertionsort:

Answer 4

(stabil) Insertionsort entnimmt der unsortierten Teilfolge ein Element und fugt es an richtiger Stelle in die (anfangs leere) sortierte Teilfolge ein.

Laufzeit/Vergleiche:
Best-Case Θ(n)
Worst-Case Θ(n^2).
Average-Case Θ(n^2)

Vertauschungen:
Best-Case Θ(n)
Worst-Case Θ(n^2).
Average-Case Θ(n^2)

Question 5

Wann ist Algorithmus effizient?

Answer 5

Wir nennen einen Algorithmus effizient, wenn seine

Laufzeit polynomiell in der Eingabegröße ist.

Question 6

Internes Sortieren:

Answer 6

bezeichnet Sortierverfahren die nur im Hauptspeicher arbeiten

Question 7

Stabiles Sortieren:

Answer 7

Ordnungserhalten bei gleichen Schlüsseln. Das bedeutet bei gleichen Schlüsseln
bleibt die ürsprungsreihenfolge erhalten. Bspw. Radix-Sort

Question 8

Merge Sort:

Answer 8

(stabil)
* Teile Array in zwei Hälften.
* Sortiere jede Hälfte rekursiv.
* Verschmelze zwei Hälften zu einem sortierten Ganzen.

Laufzeit/Vergleiche immer : Θ(n log n)
Vertauschungen immer: Θ(n log n)
Speicher: immer Θ(n)

Question 9

Quick Sort:

Answer 9

(nicht stabil)
Quicksort: Benutzt auch das Divide-and-Conquer-Prinzip, aber auf
eine andere Art und Weise.
Teile: Wähle ”Pivotelement“ x aus Folge A, z.B. das an der letzten Stelle stehende Element.

Teile A ohne x so in zwei Teilfolgen A1 und A2, dass gilt:
A1 enthält nur Elemente ≤ x.
A2 enthält nur Elemente ≥ x.
Herrsche:
Rekursiver Aufruf für  A1.
Rekursiver Aufruf für  A2.

Laufzeit/Vergleiche:
Best/AVG Θ(n log n)
Worst Θ(n^2)

Speicher:
Best/AVG Θ(log n)
Worst Θ(n)

Vertauschungen:
Best Θ(n)
Worst/AVG Θ(n log n)

Question 10

Lineare Suche

Answer 10

Best Case : Θ(1)
naives, sequenzielles Durchsuchen der Liste.

Worst/AVG Case: Θ(n)

Question 11

Binäre Suche

Answer 11

Suchen in sortierter Liste durch Halbierung des Suchintervalls

Best Case : Θ(1)
naives, sequenzielles Durchsuchen der Liste.

Worst/AVG Case: Θ(logn)

Question 12

Einsatz von Sortierverfahren Merge und quicksort

Answer 12

Quicksort:
Wird sehr oft in allgemeinen Sortiersituationen bevorzugt.

Mergesort:

Mergesort wird hauptsächlich fur das Sortieren von Listen verwendet.

Wird auch fur das Sortieren von Dateien auf externen Speichermedien eingesetzt.
- Dabei wird aber eine iterative Version von Mergesort (Bottom-up-Mergesort) verwendet, bei der nur log n-mal eine
Datei sequentiell durchgegangen wird.

Question 13

Handshaking lemma für ungerichtete Graphen

Answer 13

Summe (deg(v)) = 2*|E|

Question 14

Adjazenzmatrix vs Adjazenyliste

Answer 14

Adjazenzmatrix:
Platzbedarf in Θ(n^2).
Uberprüfen, ob (u, v) eine Kante ist, hat Laufzeit : Θ(1).
Aufzählen aller Kanten hat eine Laufzeit von Θ(n^2)

Adjazenzliste:
Platzbedarf in Θ(m+n).
Uberprüfen, ob (u, v) eine Kante ist, hat Laufzeit : Θ(deg(u)).
Aufzählen aller Kanten hat eine Laufzeit von Θ(m+n)

Question 15

Lichte und Dichte Graphen:

Answer 15

Graphen sind dicht (dense) falls m = Θ(n^2).
Graphen sind licht (sparse) falls m = O(n)

Fur dichte Graphen sind beide Darstellungsformen
(Adjazenzmatrix oder Adjazenzlisten) vergleichbar.

Lichte Graphen Adjazenzlisten

Question 16

Breitensuche und Tiefensuche laufzeit

Answer 16

0(n+m)

Question 17

Gerichteter azyklischer Graph Lemma

Answer 17

Lemma: G ist ein DAG genau dann wenn jeder Teilgraph von G eine Quelle hat.
Wir nennen eine Knoten v ohne eingehende Kanten in einem gerichteten Graphen (i.e. deg−(v) = 0) Quelle.

Question 18

Topologische Sortierung Laufzeit:

Answer 18

O(n + m)

Question 19

Min Heap Laufzeiten(analog für max)

Answer 19

Insert(H,v): O(log n).
FindMin(H): O(1)
Delete(H,i): O(logn)
ExtractMin(H): Kombination von FindMin und Delete unddaher in O(log n)

Question 20

Dijkstra Laufzeit

Answer 20

Worst cases:

Liste O(n^2)
Heap O((n + m) log n) 
FibHeap O(m + n log n)

m - Anzahl Kanten n - Anzahl Knoten

Question 21

Interval Scheduling Laufzeit

Answer 21

Greedy: O(n*logn)

Question 22

Kantenschnittlemma:

Answer 22

Sei S eine beliebige Teilmenge von Knoten

und sei e die minimal gewichtete Kante mit genau einem Endknoten in S. Dann enth¨alt der MST die Kante e.

Question 23

Kreislemma:

Answer 23

Sei C ein beliebiger Kreis und sei f die maximal

gewichtete Kante in C. Dann enth¨alt der MST f nicht.

Question 24

Kruskal vs Prim

Answer 24

Kruskal:
O(m logn)

Prim:
O(m logn) mit Priority Queue
O(m + nlogn) mit Fib Heap

Anwendung in der Praxis:

Fur dichte Graphen ( m = Θ(n^2)) ist Prims Algorithmus
besser geeignet. потому что в крускале нужно будет много вычеркивать ненужных что увеличивает лауфцайт

Fur dünne(lichte) Graphen ( m = Θ(n)) ist Kruskals Algorithmus
besser geeignet.

Question 25

Inorder, PostOrder,Preorder

Answer 25

Inorder-Durchmusterung: Behandle rekursiv zunächst den linken Unterbaum, dann die Wurzel, dann den rechten Unterbaum. Preorder-Durchmusterung: Behandle rekursiv zunächst die Wurzel, dann den linken Unterbaum, danach den rechten Unterbaum. Postorder-Durchmusterung: Behandle rekursiv zunächst den linken Unterbaum, dann den rechten Unterbaum, danach die Wurzel.

Question 26

Successor und Predecessor

Answer 26

Successor: Nächster Knoten entsprechend der Inorder-Durchmusterungsreihenfolge oder null. Predecessor: Vorhergehender Knoten entsprechend der Inorder-Durchmusterungsreihenfolge oder null.

Question 27

AVL Baum laufzeit

Answer 27

Immer O(logn)

Question 28

B baum der Ordnung m

Answer 28

1. Alle Blätter haben gleiche Tiefe und sind leere Knoten. 2. Jeder Knoten hat bis zu m Kinder. 3. Jeder innere Knoten außer der Wurzel hat mindestens [m/2] Kinder. Die Wurzel hat mindestens 2 Kinder. 4. Jeder Knoten mit l Schlussel hat l + 1 Kinder.

Question 29

Lineares Sondieren

Answer 29

h(k, i) = (h'(k) + i) mod m | primären Häufung ist das Problem von liniares Sondieren

Question 30

Quadratisches Sondieren:

Answer 30

h(k, i) = (h'(k) + c1*i + c2*i^2) mod m | die sekundären Häufungen ist das Problem von Quadratischen Sondieren

Question 31

Double Hashing:

Answer 31

h(k, i) = (h1(k) + i*h2(k)) mod m.

Question 32

Verbesserung nach brent

Answer 32

``` j1 = (j + h2(k)) mod m j2 = (j + h2(k')) mod m ```

Question 33

Set:

Answer 33

Eine Collection, die keine duplizierten Elemente enth¨alt.

Question 34

List:

Answer 34

Eine geordnete Collection (mit duplizierte Elementen). | Elemente können über einen Index angesprochen werden (nicht immer effizient)

Question 35

Queue/Deque:

Answer 35

Verwalten von Warteschlangen. FIFO, Priorit¨atswarteschlangen. Einfugen und Löschen an beiden Enden bei Deque (“double ended queue”).

Question 36

ArrayList vs Linked List

Answer 36

ArrayList: *Indexzugriff auf Elemente ist uberall gleich schnell ( ¨O(1)). *Einfugen und Löschen ist am Listenende schnell und wird mit wachsender Entfernung vom Listenende langsamer (O(n)). LinkedList: *Indexzugriff auf Elemente ist an den Enden schnell und wird mit der Entfernung von den Enden langsamer (O(n)). *Einfugen und Löschen ohne Indexzugriff ist überall gleich schnell (O(1)).

Question 37

PriorityQueue

Answer 37

Einfugen eines Elements und Löschen des ersten Elements in einer Queue der Größe n sind in O(log n). Löschen eines beliebigen Elements aus einer Queue der Größe n ist in O(n) Lesen des ersten Elements in einer Queue ist in konstanter Zeit möglich (O(1)). Ist als Min-Heap implementiert.