D&A – Tricky Bonus Questions

$$

XKCD Nr. 356: Nerd Sniping

Im folgenden ein paar besonders knifflige Aufgaben im Stil von D&A, welche den Assistenten im Verlaufe des Semesters über den Weg gelaufen sind.

Achtung: Die Aufgaben sind nicht nach Schwierigkeit geordnet, sondern thematisch!

Wenn du einige der Aufgaben gelöst hast, so sende sie uns ein an [e-mail]. Abgabeschluss ist der Tag der D&A-Prüfung. Wer die meisten Rätsel knackt, gewinnt mindestens einen Buchpreis (z.B. Datenstrukturen und Algorithmen von Widmayer, Ottmann oder Introduction to Algorithms von Cormen, Leierson, Rivest und Stein). Bei hervorragenden Einsendungen gerne auch mehr…

Viel Erfolg!

Asymptotische Notation

Aufgabe 1

Gib die Grössenordnung der folgenden Funktion (so knapp wie möglich) in

$\mathrm{\Theta }$-Notation an:

$$\sum _{i=1}^n\log \left(\frac{n}{i}\right)$$
Hinweis: Man schafft es auch ohne Stirling. Man muss aber nicht :-)

Aufgabe 2: Alternative Lösungen zu Aufgabe 1.2.f)

Wir zeigen, dass folgende Implikation gilt:

$$f_1,f_2\in \mathcal{O}(g)\Rightarrow f_1+f_2\in \mathcal{O}(g).$$

Dazu machen wir eine Fallunterscheidung:
Falls

$f_1\ge f_2$, dann gilt

$2\cdot f_1\ge f_1+f_2\in \mathcal{O}(f_1)\subseteq \mathcal{O}(g)$.
Für

$f_1\le f_2$, argumentieren wir analog.

Warum funktioniert dieser Beweis nicht?

Wir versuchen es noch einmal, diesmal präziser:
Wegen

$f_1,f_2\in \mathcal{O}(g)$ wissen wir, dass gilt

$$\begin{array}{r}\mathrm{\exists }{c}_1\in {\mathbb{R}}^{+},n_1\in \mathbb{N},\mathrm{\forall }n\ge n_1:f_1(n)\le c_1\cdot g(n),\\ \mathrm{\exists }{c}_2\in {\mathbb{R}}^{+},n_2\in \mathbb{N},\mathrm{\forall }n\ge n_2:f_2(n)\le c_2\cdot g(n).\end{array}$$

Ausserdem wächst ab einem bestimmten Punkt

$n_3$ eine der beiden Funktionen schneller, OBdA sei dies

$f_1$. Das heisst:

$$\mathrm{\exists }{n}_3\in \mathbb{N},\mathrm{\forall }n\ge n_3:f_2(n)\le f_1(n).$$

Setzen wir nun

$n_4:=max\{n_1,n_2,n_3\}$ und

$c_4:=2c_1$, so schliessen wir aus den obigen Aussagen, dass

$$\mathrm{\forall }n\ge n_4:f(n)=f_1(n)+f_2(n)\stackrel{n\ge n_3}{\le }2f_1(n)\stackrel{n\ge n_1}{\le }2c_1\cdot g(n)=c_4\cdot g(n),$$

und deshalb

$f(n)\in \mathcal{O}(g)$.

Stimmt dieser neue Beweis? Falls ja, wieso?
Falls nein, für welche Klasse von Funktionen gilt er?

Aufgabe 3

Zeigen oder widerlegen Sie:

$$\mathrm{\forall }f,g:(f\in \mathcal{O}(g))\vee (g\in \mathcal{O}(f))$$

Rekursionsgleichungen

Aufgabe 4

Analysiere folgendes Codestück in der

$\mathrm{\Theta }$-Notation. Was passiert, wenn das Semikolon in Zeile 5 gelöscht wird? Gib wiederum die Laufzeit an. (Du kannst annehmen, dass

$n$ eine Zweierpotenz ist.)

int f(n) {
	int c = 0;
	if (n == 1) return 1;
	for(int i = 0; i<n; i++)
		;
	c = f(n/2)+1;
	return c;
}

Aufgabe 5

Gegeben sei folgende Rekursionsgleichung (wobei angenommen werden darf, dass

$n$ eine Zweierpotenz ist):

$$T(n)=\{\begin{array}{ll}2T\left(\frac{n}{2}\right)+\log n& \text{falls }n>1,\\ 1& \text{falls }n=1.\end{array}$$
Finde eine geschlossene Form für die Gleichung.

Induktion

Aufgabe 6

Beweisen Sie mit vollständiger Induktion die in Aufgabe 5 gefundene geschlossene Form für die Rekursion

$T(n)=2T\left(\frac{n}{2}\right)+\log n$.

Aufgabe 7

Auf einer Wiese steht – von 3 hungrigen Löwen umringt – ein einsames, aber magisches Schaf. Falls einer der Löwen das Schaf frisst, so wird er selbst zu einem (wiederum magischen) Schaf und kann von den verbleibenden Löwen gefressen werden.
Wird das Schaf gefressen? Wie sieht die Situation bei vier Löwen aus? Wie bei einer allgemeinen Anzahl

$n$ von Löwen? Beweisen Sie Ihre Vermutung mit Induktion.

Aufgabe 8

Ein Piratenschiff mit

$n$ Piraten

$p_1,p_2,\dots ,p_n$ hat vor kurzem eine Truhe mit

$100$ Goldtalern gestohlen. Nun möchten sie das Gold aufteilen. Die Piraten folgen dabei dem Recht des Stärkeren, gepaart mit einem Minimalverständnis von Demokratie:

1. Zuerst macht der grimmigste Pirat
   $p_n$ einen Vorschlag, welcher Pirate wieviele Goldstücke erhalten soll.
2. Dann wird darüber abgestimmt (jeder Pirat, inklusive
   $p_n$, hat eine Stimme). Stimmt mindestens die Hälfte für den Vorschlag, so wird das Gold verteilt. Wird der Vorschlag hingegen abgelehnt, so wird
   $p_n$ über Bord geworden und der nächstschlimmere Pirat
   $p_{n-1}$ macht den nächsten Vorschlag.

Alle Piraten haben grossen Spass daran, jemanden über Bord zu werfen. Noch wichtiger ist es ihnen hingegen, selber möglichst viel Gold zu erhalten. Falls beispielsweise ein Pirat

$p_i$ in zwei Vorschlägen

$P$ und

$Q$ gleich viel Gold erhält, aber nur in

$Q$ ein anderer Pirat

$p_j$ über die Planke gehen muss, so bevorzugt

$p_i$ hämisch die Variante

$Q$. Die wichtigste Maxime für

$p_i$ ist hingegen, selber am Leben zu bleiben.
Welchen Vorschlag sollte der mächtigste Pirat

$p_n$ machen, falls
a)

$n=3$,
b)

$n=100$ ?
c) Kann

$p_n$ überleben, falls

$n\ge 200$?

Datenstrukturen

Aufgabe 9

Wir betrachten zwei Min-Heaps, implizit gegeben als Arrays

$A$ und

$B$ der Grösse

$n$ respektive

$m$. Wir nehmen an, dass jedes Element von

$A$ kleiner ist als jedes Element von

$B$ (formaler:

$\mathrm{\forall }i,j:A[i]<B[j]$). Sei nun

$C$ der Array der Grösse

$n+m$, welcher sich ergibt, wenn wir

$B$ an

$A$ anhängen (das heisst

$C$ ist gegeben durch

$C[i]=A[i]$, falls

$i\le n$, und

$C[i]=B[i-n]$ sonst).
Ist

$C$ wiederum ein Min-Heap? Beweisen oder widerlegen Sie.

Aufgabe 10

Gegeben

$n$, die Anzahl Elemente in einem Heap (ein Binärbaum mit dem letzten Level von links nach rechts aufgefüllt). Betrachten wir nun den eindeutigen Weg vom letzten Blatt (das auf dem untersten Level ganz rechts) zur Wurzel. Dieser Weg besteht aus

$\lfloor {\log }_2(n)\rfloor$ vielen Schritten, jeder davon ist aus der Sicht des jeweiligen Vaterknoten ein Schritt nach links oder nach rechts. Nun wollen wir in konstanter Zeit wissen, ob der

$i$-te dieser Schritte ein Links-Schritt oder ein Rechts-Schritt ist.

Ein Beispiel: Für

$n=11$ ist der Weg an die Wurzel rechts, rechts, links. Für

$i=1$, wäre die gewünschte Antwort also: "rechts".

Dynamische Programmierung

Aufgabe 11

In Aufgabe 7.2 haben wir ein DP gesehen, um das längste Palindrom in einem Text zu finden. Dabei hatten wir eine Tabelle

$T[][]$, die in Zelle

$T[i][j]$ angibt, ob der Substring von

$i$ bis

$j$ ein Palindrom ist (genau dann ist

$T[i][j]=true$).

Sei diese Tabelle nun bereits aufgefüllt gegeben. Die Lösung in Aufgabe 7.2.b) findet in der Tabelle ein längstes Palindrom in Zeit

$\mathcal{O}(n^2)$. Findest du eine subquadratische Lösung, das heisst, eine Lösung mit nur
a)

$\mathcal{O}(n\log n)$ Zugriffen auf die Tabelle,
b)

$\mathcal{O}(n)$ Zugriffen auf die Tabelle?

Aufgabe 12

Zweifach Offline: Wir schauen uns eine Offline-Version des Dino-Spiels des Chrome-Browsers an (Tipp: Versetze dein Mobiltelefon oder Laptop in den Flugmodus, rufe eine Seite in Chrome auf und drücke auf den Dino).
In unserem Dino-Spiel soll ein T-Rex von links nach rechts über eine Ebene rennen und dabei alle Kakteen, die sich ihm in den Weg stellen, überspringen. Wir möchten wissen, ob dies überhaupt möglich ist.

Gegeben sind:

1. $D$, die Länge der Ebene,
2. $j$, die Sprungweite des T-Rex,
3. $n$ Kakteen, gegeben durch ein Array der Grösse
   $n$, welches die Positionen (
   $x$-Koordinaten, bereits aufsteigend sortiert) aller Kakteen enthält.

Unser Dino startet bei Postion

$x=0$ und muss sich bei jedem ganzzahligen

$x$ entscheiden, ob er zum Feld

$x+1$ weiterrennen möchte, oder abspringen will. In diesem Falle landet er auf Feld

$x+j$. Beachte, dass unser T-Rex aufgrund der parabolischen Flugbahn mindestens 3 Felder vor einem Kaktus abspringen und ebensoviele Felder von einem Kaktus entfernt landen muss. Steht also auf Feld

$x$ ein Kaktus, so sollte der T-Rex die Felder

$x-2,x-1,x,x+1$ und

$x+2$ vermeiden.

Gib einen möglichst schnellen Algorithmus nach dem Prinzip der dynamischen Programmierung an, welcher bestimmt, ob der Dino das Feld

$D$ erreichen kann.

Aufgabe 13

Sei

$T[n]$ die Anzahl verschiedener Min-Heaps, welche aus allen Schlüsseln

$1,2,\dots ,n$ gebildet werden können. Beispielsweise ist

$T[4]=3$ (die drei Min-Heaps sind

$1234$,

$1243$ und

$1324$),

$T[5]=8$ und

$T[6]=20$.
Schreibe ein Dynamische Programm, um die Werte

$T[1],T[2],\dots ,T[25]$ zu berechnen. (Falls du die Lösung einreichen möchtest, so notiere die Lösung als Linien-separierte Liste der Werte.)

Graphenalgorithmen

Aufgabe 14

Löse die Programmieraufgabe 8.4 in konstanter Zeit. Also: Gegeben natürliche Zahlen

$n$ und

$m$ und ein zusammenhängender, ungerichteter Graph als Adjazenzlisten mit

$n$ Knoten und

$m$ Kanten (schon im Speicher eingelesen), entscheide in konstanter Zeit, ob der Graph zyklenfrei ist.

Aufgabe 15

Diamantendiebstahl in Planarplanet: In Planarplanet, einem Planeten von der Form einer Scheibe, wird im Algoland ein wertvoller Diamant gestohlen. Die internationale Polizeiabteilung Interpol weiss aus zuverlässigen Quellen, dass sich der Diamantenhehler in Legoland, einem weiteren Land auf Planarplanet befindet.
Interpol möchte nun verhindern, dass der Diamant bis zum Käufer gelangen kann. Deshalb soll die kleinste Anzahl Länder gefunden werden, in welchen die Polizei alarmiert werden soll, sodass keine Route von Algoland nach Legoland existiert, welche nicht durch eines dieser Länder führt.

Zwei Länder sind benachbart, falls sie eine gemeinsame Grenze haben, und von jedem Land aus kann man genau in alle Nachbarländer reisen. Keines der Länder hat eine Exklave (das heisst jedes Land ist einfach zusammenhängend).
Gib einen möglichst schnellen Algorithmus an, um zu bestimmen, in welchen Ländern Interpol die Polizei alarmieren soll. Es sollen möglichst wenig Länder alarmiert werden.

Aufgabe 16

Interborder, die internationale Vereinigung aller Grenzwachen, hat ebenfalls vom Diamantenraub aus Aufgabe 15 erfahren. Am liebsten würden die Grenzwachen die Diebe selber schnappen. Landesgrenzen zu bewachen ist allerdings kostspielig, für jeden Kilometer Grenze braucht es 10 Beamte.

Für jedes Paar von benachbarten Ländern ist die Länge der gemeinsamen Grenze bekannt. Gesucht ist nun eine zu bewachende Teilmenge der Grenzen, sodass (i) jede Route von Algoland nach Legoland mindestens eine bewachte Grenze überquert und (ii) möglichst wenige Beamte im Einsatz sein müssen. (Haben die Länder A und B, sowie B und C je eine gemeinsame Grenze, so können wir beide Grenzen von B bewachen, nur eine, oder auch gar keine.)

1. Gib an, wie Interborder die zu bewachenden Grenzen finden kann. Wie lässt sich aus deinem Ansatz die Anzahl benötigter Grenzwächter ablesen?
2. Gegeben eine gewünschte bewachte Teilmenge der Grenzen, gibt es eine Möglichkeit, jede bewachte Grenze zwischen zwei Ländern von genau einem der beiden Länder bewachen zu lassen, sodass jedes Land nur die Grenze zu höchstens einem Nachbarland bewachen muss?

Geometrie

Aufgabe 17

Gegeben

$n$ Punkte in der Ebene, finde dasjenige Punktepaar, für welches die Gerade durch die beiden Punkte möglichst grosse Steigung hat.