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

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

True False

Wir nennen eine Menge $S$ $(m, r)$-ausgerichtet, wenn $(\sum_{x \in S} x) \mod m = r$. Der DP-Übergang für $DP[i, r]$ = Anzahl der Teilmengen von $\{1..i\}$ mit Rest $r$ ist:

$DP[i, r] = DP[i-1, r] + DP[i-1, (r – i) \mod m]$ $DP[i, r] = DP[i-1, r] \cdot DP[i-1, (r – i) \mod m]$ $DP[i, r] = DP[i-1, (r + i) \mod m]$ $DP[i, r] = \max(DP[i-1, r], DP[i-1, (r – i) \mod m])$

Bei der Matrix-Kettenmultiplikation ist die optimale Klammerung eindeutig.

True False

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$

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