Quiz on Dynamic Programming and Algorithm Design

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

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

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

Sie haben ein Array $A$ und wollen es in 3 Teilmengen $A_1, A_2, A_3$ partitionieren, um $\max(\sum A_1, \sum A_2, \sum A_3)$ zu minimieren. Der DP-Zustand ist $M[i, s, t]$: Ist es möglich, das Präfix $A[1..i]$ so zu partitionieren, dass $\sum A_1 = s$ und $\sum A_2 = t$? Wie lautet der Übergang?

$M[i, s, t] = M[i-1, s-A[i], t] \lor M[i-1, s, t-A[i]] \lor M[i-1, s, t]$ $M[i, s, t] = M[i-1, s+A[i], t] \land M[i-1, s, t+A[i]]$ $M[i, s, t] = M[i-1, s, t] \land M[i-1, s-A[i], t-A[i]]$ $M[i, s, t] = M[i-1, s-A[i], t-A[i]]$

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

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