Home
Writing
ETH

Quiz on Dynamic Programming and Algorithm Design

Gegeben Array $A$, wir wollen die Länge der längsten Teilfolge, bei der $a_k = a_{k-1} + a_{k-2}$ (Fibonacci-Eigenschaft). Was sind die Dimensionen der DP-Tabelle?

$n$ $n \times n$ $n \times \max(A)$ $n \times n \times n$

Der Zustand $L[i, j]$ ist die Länge der längsten Fibonacci-Teilfolge, die mit den Indizes $i$ und $j$ endet ($i < j$). Um sie zu berechnen, suchen wir nach $k < i$, wobei $A[k] + A[i] = A[j]$.

Bei der Matrix-Kettenmultiplikation ist die optimale Klammerung eindeutig.

True False

Es können mehrere optimale Klammerungen mit derselben minimalen Anzahl von Multiplikationen existieren.

Ein Array ist 'summy', wenn jedes Element $a_i$ (außer dem ersten) die Summe einer Teilmenge der vorhergehenden Elemente ist. Der DP-Zustand $DP[i][k]$ prüft, ob die Summe $k$ mit einer Teilmenge der ersten $i$ Elemente gebildet werden kann.

True False

Um zu prüfen, ob $A$ summy ist: Für jedes $i$, prüfen wir, ob $DP[i-1][a_i]$ True ist, d.h. ob $a_i$ als Summe einer Teilmenge der vorherigen Elemente darstellbar ist.

Gegeben Array $A$, Zielsumme $C$ und Ziel-Quadratsumme $D$. Bestimmen Sie, ob eine Teilmenge existiert, die beides erfüllt. Was ist der DP-Zustand?

$DP[i, c]$ $DP[i, c, d]$ $DP[c, d]$ $DP[i]$

Der DP-Zustand $DP[i, c, d]$ ist ein Boolean: Ist es möglich, eine Teilmenge aus den ersten $i$ Elementen mit Summe $c$ und Quadratsumme $d$ zu wählen? Größe: $n \times C \times D$.

Für das Problem 'Gibt es zwei disjunkte Teilmengen $I_1, I_2$ mit $\sum_{i \in I_1} a_i = \sum_{j \in I_2} a_j$?' kann man mit DP prüfen, ob zwei verschiedene Teilmengen denselben Wert ergeben.

True False

Man berechnet $DP[i][m]$ = Anzahl der Teilmengen der ersten $i$ Elemente, die sich zu $m$ summieren. Wenn für irgendein $m$ gilt $DP[n][m] \ge 2$, existieren zwei verschiedene Teilmengen mit gleicher Summe.

Quiz on Dynamic Programming and Algorithm Design

Recent posts

Lecture Notes

Quizzes

New Siri needs that Steve Jobs touch

Conversations don’t flow linearly, so LLM interfaces shouldn’t either

LaTeX Collection