PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2

SOSE 2023
PROF. DR. AMIN COJA-OGHLAN

• Bearbeitungszeit 90 Min.
• Alle Aufgaben haben gleiches Gewicht.
• Tragen Sie alle Antworten in die vorgesehenen Felder ein.
• Keine Aufzeichnungen erlaubt.
• Keine Hilfsmittel außer unbeschriebenem Papier und Stift erlaubt.

Vorname:
Nachname:
Matrikelnummer:

Bewertung
Aufgabe 1 Aufgabe 2 Aufgabe 3 Aufgabe 4 Aufgabe 5 Aufgabe 6 Σ Note

1
2 PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2 SOSE 2023 PROF. DR. AMIN COJA-OGHLAN

AUFGABE 1
Kreuzen Sie alle zutrefenden Aussagen in jeder Zeile an.

f (n) g(n) f (n) = O(g(n)) f (n) = o(g(n)) f (n) = Θ(g(n)) f (n) = Ω(g(n))

1
(n2 − 2n)2 100 n
4
− 5n3 ✓ ✓ ✓
3n √1 nggT(39,21)


a) 3n−3 2
Pn 1
Pn n


b) i=1 i log(log( i=0 i (2e)i (−e)n−i ))

c) e−n sin( n−1

n2 )
R √n
d) log(n!) 1
log(x)dx

3n
= 12 n · (3n − 1) · (3n − 2).


a) Da der ggT(21, 39) = 3, ist f (n) = 3n−3
1
· (3n − 1) · (3n − 2)
2n 1 9n3 − 9n2 + 2n 1
lim 1 = √ lim =√ 9
n→∞ √ n3 2 n→∞ n3 2
2
Pn
b) Mit den binomischen Lehrsatz gilt g(n) = log(log( i=0 ni (2e)i (−e)n−i )) = log(log(en )) = log(n)


Pn 1
und es gilt f (n) = i=1 i = Hn nach der VL:

Hn
0 < lim <∞
n→∞ log(n)
c) Mit l’Hospital folgt:
e−n n3 e−n
lim n−1 = lim =0
n→∞ sin( 2 ) n→∞ (n − 2) cos( n−1
n n2 )

Der Term cos( n−1

n2 ) geht für n → inf gegen 1 und der Zähler geht exponentiell schnell gegen 0. DEr
Nenner wächst nur linear√und daher geht der Quotient gegen 0.
R n
d) Durch Integration von 1 log(x)dx erhält man:
√
n
1√
Z
log(x)dx = n(log(n) − 2) + 1
1 2
√
also ist der führende Term hier n log(n) Mit Striling bekommen wir für den Ausdruck für n → ∞:
√ n √ √
log(n!) = log( 2πn( )n ) = log( 2πn) + n · log(n) − n · log(e) = log( 2πn) + n · log(n) − n
e
Für n → ∞ ist der dominierende Term n log(n), also gilt:

n log(n) √
lim √ = lim n = ∞
n→∞ n log(n) n→∞

f (n) g(n) f (n) = O(g(n)) f (n) = o(g(n)) f (n) = Θ(g(n)) f (n) = Ω(g(n))

1
(n2 − 2n)2 100 n
4
− 5n3 ✓ ✓ ✓
3n √1 nggT(39,21)


a) 3n−3 2
✓ ✓ ✓
Pn Pn n

i n−i
b) i=1 log(log( i=0 i (2e) (−e) )) ✓ ✓ ✓

c) e−n sin( n−1

n2 ) ✓ ✓
R √n
d) log(n!) 1
log(x)dx ✓
 PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2 SOSE 2023 PROF. DR. AMIN COJA-OGHLAN 3

AUFGABE 2
Finden Sie die kleinsten Zahlen v, w, x, y ∈ N, sodass gilt:

788 ≡ v mod 89
44
5 ≡w mod 43
55 · x ≡ 1 mod 89
144 · y ≡ 1 mod 233

Antwort:
a.) v = 1 b.) w = 25 c.) x = 34 d.) y = 89

• 88 = 26 + 24 + 23
• k = 6, ℓ6 = ℓ4 = ℓ3 = 1, ℓ5 = ℓ2 = ℓ1 = ℓ0 = 0
• y0 ≡ 7 mod 89, y1 ≡ 72 ≡ 49 mod 89, y2 ≡ 492 ≡ 87 mod 89, y3 ≡ 872 ≡ 4 mod 89, y4 ≡
42 ≡ 16 mod 89, y5 ≡ 162 ≡ 78 mod 89, y6 ≡ 782 ≡ 32 mod 89
• Folge der z-Werte:

z0 = 1·y0l0 = 70 = 1, 1·y1l1 = 1, 1·y2l2 = 1, 1·y3l3 = 4, 4·y4l4 = 4·161 = 64, 64·y5l5 = 64, 64·y6l6 = 64·32 mod 89 = 1

• ⇒v=1

• 44 = 25 + 23 + 22
• k = 5, ℓ5 = ℓ3 = ℓ2 = 1, ℓ4 = ℓ1 = ℓ0 = 0
• y0 ≡ 5 mod 43, y1 ≡ 52 ≡ 25 mod 44, y2 ≡ 252 ≡ 23 mod 43, y3 ≡ 232 ≡ 13 mod 43, y4 ≡
132 ≡ 40 mod 43, y5 ≡ 402 ≡ 9 mod 43
• Folge der z-Werte:

z0 = 1·y0l0 = 50 = 1, 1·y1l1 = 1, 1·y2l2 = 23, 23·y3l3 = 23·13 = 41, 41·y4l4 = 41·640 = 41, 41·y5l5 = 41·9 = 25

• ⇒ w = 25

89 = 1 · 55 + 34
55 = 1 · 34 + 21
34 = 1 · 21 + 13
21 = 1 · 13 + 8
13 = 1 · 8 + 5
8=1·5+3
5=1·3+2
3=1·2+1
2=2·1+0
4 PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2 SOSE 2023 PROF. DR. AMIN COJA-OGHLAN

Rückrechnen liefert:
1=1·1+0·2
1 = −1 · 2 + 1 · 3
1 = 2 · 3 + −1 · 5
1 = −3 · 5 + 2 · 8
1 = 5 · 8 + −3 · 13
1 = −8 · 13 + 5 · 21
1 = 13 · 21 + −8 · 34
1 = −21 · 34 + 13 · 55
1 = 34 · 55 + −21 · 89

⇒ x = 34

233 = 1 · 144 + 89
144 = 1 · 89 + 55
89 = 1 · 55 + 34
55 = 1 · 34 + 21
34 = 1 · 21 + 13
21 = 1 · 13 + 8
13 = 1 · 8 + 5
8=1·5+3
5=1·3+2
3=1·2+1
2=2·1+0

Rückrechnen liefert:
1=1·1+0·2
1 = −1 · 2 + 1 · 3
1 = 2 · 3 + −1 · 5
1 = −3 · 5 + 2 · 8
1 = 5 · 8 + −3 · 13
1 = −8 · 13 + 5 · 21
1 = 13 · 21 + −8 · 34
1 = −21 · 34 + 13 · 55
1 = 34 · 55 + −21 · 89
1 = −55 · 89 + 34 · 144
1 = 89 · 144 + −55 · 233

⇒ v = 89

AUFGABE 3
Bestimmen Sie für den nachfolgenden Graphen G die folgenden Werte:
 PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2 SOSE 2023 PROF. DR. AMIN COJA-OGHLAN 5

Antwort:
a.) α(G) = 7 b.) ω(G) = 2 c.) χ(G) =4 d.) ∆(G) = 4

∆(G) = 4, da jeder Knoten den Grad 4 besitzt. Ee existiert kein K3 in G, daraus folgt ω(G) = 2. Durch
brute force erhält man α(G) = 7. Wir wissen ∆(G) + 1 ≥ χ(G) ≥ ω(G). Deshalb gilt hier 5 ≥ χ(G) ≥ 2
|V |
Da |V | = 21 gilt und α(G) = 7 und χ(G) ≥ ⌈ α(G) ⌉, gilt hier χ(G) ≥ ⌈ 21
7 ⌉ = 3. Also muss 3, 4, 5
probiert werden. Es gilt χ(G) = 4. Eine maximale stabile Menge kann wie folgt aussehen:
6 PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2 SOSE 2023 PROF. DR. AMIN COJA-OGHLAN

AUFGABE 4

8 6

8 4 13 2

9 4

3
 PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2 SOSE 2023 PROF. DR. AMIN COJA-OGHLAN 7

Führen Sie den BHK Algorithmus aus um die kürzeste TSP-Tour des Graphen zu finden. Wählen Sie den
Knoten 1 als Startknoten. Füllen Sie dazu die folgende Tabelle mit den jeweiligen Werten für T (u, U ) aus.
Geben Sie am Ende die Länge der optimalen TSP-Tour sowie dessen Weg aus.
N u U
∅
2
0
3
4
{2} {3} {4}
2 x
1
3 x
4 x
{2, 3} {2, 4} {3, 4}
2 x x
2
3 x x
4 x x
Länge der optimalen TSP-Tour

Pfad der optimalen TSP-Tour

N u U
∅
2 6
0
3 8
4 8
{2} {3} {4}
2 x 8+ 4 = 12 8+ 13 = 21
1
3 6 + 4 = 10 x 8 + 9 = 17
4 6 + 13 = 19 8+ 9 = 17 x
{2, 3} {2, 4} {3, 4}
2 x x 8 + 9 + 4 = 21
2
3 x 8+ 13 + 4 = 25 x
4 6 + 4 + 9 = 19 x x

Wir suchen das Minimum der Touren:

min{19 + 8 = 27, 25 + 8 = 33, 21 + 6 = 27}

Länge der optimalen TSP-Tour 27

Pfad der optimalen TSP-Tour 1 → 2 → 3 → 4 → 1 oder 1 → 4 → 3 → 2 → 1

AUFGABE 5
Berechnen Sie die Größenordnung der Rekurrenzen.
8 PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2 SOSE 2023 PROF. DR. AMIN COJA-OGHLAN

√ √
a) T (n) = nT ( n) + n
n
b) T (n) = 16T ( 4 ) + n!
c)
(√ √
2T ( n2 ) + n, n>1
T (n) =
1, n=1
d)
(
T (n − 1) + 2(n−1), ∀n > 1
T (n) =
10, n = 1

Antwort:
√
a.) Θ( n log log n ) b.) Θ( n! ) c.) Θ( n log n ) d.) O( n2 )

Solution:
√ √
a) T (n) = nT ( n) + n
√
Let n = 2p , then n = 2p/2 and p = log n. Substituting in above equation, we get:
T (2p ) = 2p/2 T (2p/2 ) + 2p
p p/2
Dividing it by 2p we get, T (2
2p
)
= T (2
2p/2
)
+1
p
T (2 )
Now let, m(p) = 2p , then above equation can be written as, m(p) = m(p/2) + 1
Now, if we apply Master’s Theorem here with a = 1, b = 2 and k = 0, we get the solution as
T (n) = Θ(n log log n)
b) T (n) = 16T ( n4 ) + n!
Here, a = 16, b = 4 then log4 16 = 2 and f (n) = n!. After applying master’s theorem we get
logb a < f (n). So, T (n) = Θ(n!) √
c) Apply Master’s√ Theorem with a = 2, b = 2, and k = 0
So, T (n) = Θ( n log n)
d)
T (n) = T (n − 1) + 2(n − 1)
T (n) = (T (n − 2) + 2(n − 2)) + 2(n − 1)
T (n) = ((T (n − 3) + 2(n − 3)) + 2(n − 2)) + 2(n − 1)
T (n) = 2(T (1) + (n − 1) − (n − 2)) + · · · + 2(n − 3) + 2(n − 2) + 2(n − 1)
T (n) = 2(n − 1) + 2(n − 1) − 2 + 2(n − 1) − 4 + 2(n − 1) − 6 + · · · + 10
T (n) = 2[(n − 1)(n − 1)] − [(n − 1) · (n − 1) + (n − 1)]
T (n) = (n − 1)(n − 1) − (n − 1)
2
∴ T (n + 1) = O(n )

AUFGABE 6
a) In einem komplettem Min-Heap werden die Zahlen 1, 2, 3 . . . 1023 in beliebiger Reihenfolge ein-
gefügt. Bestimmen Sie die maximale Tiefe des Wertes 9 (wobei die Wurzel Tiefe 0 hat):

•8

Solution: To make a complete binary min-heap with all integers in [1,1023] exactly once, we
need to make a path with root as 1. So, the maximum depth at which integer 9 can appear is
(9 − 1) = 8 as the depth of the root is 0.
PROBEKLAUSUR DATENSTRUKTUREN ALGORITHMEN UND PROGRAMMIERUNG 2 SOSE 2023 PROF. DR. AMIN COJA-OGHLAN 9

b) Bestimmten Sie die minimale Tiefe der Zahl 9 in der selben Situation wie a):

•1

Der Min-Heap braucht die 1 als Wurzel um alle Zahlen zu speichern, danach kann die 2 und die
9 eingefügt werden.
Der Min-Heap wird aufsteigend mit den Zahlen 1-1023 gefüllt und die 9 erscheint in der Höhe
3, wegen 23 + 1 = 9
c) Betrachten Sie Quicksort auf einem Array mit n verschiedenen Elementen, die zufällig permutiert
sind. Wie groß ist die Wahrscheinlichkeit, dass ein Vergleich zwischen dem kleinsten und dem
größten Element des Arrays stattfindet?

1
• Θ( )
n

1
Solution: The total no. of comparisons for both largest and smallest element are n−1 respec-
tively. (Assume the array is in descending order) So, for the largest element, it should be compared
with other (n − 1) elements, and similarly for smallest element. So, the probability that no com-
2
parisons will be made between the smallest and largest element of the array is n−1 .
d) Betrachte ein Array (1, n, 2, n − 1, . . . , n, 1) der Länge 2n. Was ist die asymptotische Laufzeit des
Arrays bei Quicksort?

• Θ(n2 )