Quiz on Dynamic Programming and Algorithm Design

Das 0/1-Knapsack-Problem kann mit dynamischer Programmierung in $O(nW)$ Zeit gelöst werden, wobei $n$ die Anzahl der Objekte und $W$ die Kapazität ist.

True False

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

Für das Vertex Cover Problem auf einem Baum $T$ ist die DP-Rekurrenz $M[i] = \min(A[i], B[i])$, wobei $A[i]$ die Cover-Größe einschließlich Knoten $i$ und $B[i]$ ohne Knoten $i$ ist. Was ist $B[i]$?

$B[i] = \sum_{j \in \text{Kinder}} M[j]$ $B[i] = \sum_{j \in \text{Kinder}} A[j]$ $B[i] = \sum_{j \in \text{Kinder}} B[j]$ $B[i] = 1 + \sum_{j \in \text{Kinder}} M[j]$

Die längste gemeinsame Teilfolge (LCS) zweier Strings der Länge $n$ und $m$ kann in $O(nm)$ Zeit berechnet werden.

True False

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]$

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