LN4 Dynamic programming problems:

Question 1

What is the subset sum problem?

Answer 1

Given a set of integers and a target sum
𝑊
W, the subset sum problem seeks a subset of integers that sum exactly to
𝑊
W or confirms no such subset exists.

Question 2

How does DP solve the subset sum problem?

Answer 2

DP uses a Boolean function P(j, w), where P(j, w) = 1 if a subset of the first j items sums to w; otherwise, P(j, w) = 0.

Question 3

What is the recurrence relation for the subset sum problem in DP?

Answer 3

P(j, w) = P(j - 1, w) or P(j - 1, w - w_j) if w >= w_j; otherwise, P(j, w) = P(j - 1, w).

Question 4

What is the 0/1 knapsack problem?

Answer 4

The knapsack problem is a DP problem where we aim to maximize value in a knapsack of limited capacity, choosing from a set of items each with a weight and value.

Question 5

How is the knapsack problem solved using DP?

Answer 5

Define OPT(j, w) as the maximum value from the first j items that doesn’t exceed capacity w, with OPT(j, w) = max(OPT(j - 1, w), OPT(j - 1, w - w_j) + v_j) when w >= w_j.

Question 6

What is the base condition for the 0/1 knapsack DP function?

Answer 6

OPT(0, w) = 0 for all w, representing that with zero items, no value can be obtained.

Question 7

What modification allows solving the knapsack problem where multiple copies of each item are allowed?

Answer 7

Change the recurrence to OPT(j, w) = max(OPT(j - 1, w), OPT(j, w - w_j) + v_j) for allowing repeated items.

Question 8

Why does the modified formula work for unlimited copies in the knapsack problem?

Answer 8

OPT(j, w) now considers using the current item multiple times by including it in the same recursive step, making repeated inclusion possible.

Question 9

How does the generalized subset sum differ from the exact subset sum problem?

Answer 9

If no subset exactly sums to W, the generalized subset sum problem finds the subset with the largest possible sum below W.

Question 10

What is the recurrence relation for the generalized subset sum problem?

Answer 10

OPT(j, w) = max(OPT(j - 1, w), OPT(j - 1, w - w_j) + w_j), ensuring we get the maximum possible sum not exceeding w.

Question 11

What is a segmentation problem in DP?

Answer 11

It is a problem where a sequence is divided into segments to maximize or minimize the total score based on a function evaluating each segment.

Question 12

What is the DP recurrence for segmentation?

Answer 12

OPT(j) = min{OPT(i - 1) + e_{ij}}, where e_{ij} is the penalty of the segment (x_i, …, x_j).

Question 13

What is the sequence comparison problem?

Answer 13

It involves transforming one string into another with the minimum number of edit operations, such as insertions, deletions, or substitutions.

Question 14

How does DP solve the sequence comparison problem?

Answer 14

DP defines an alignment cost and recursively calculates the minimum edits by matching, inserting, or deleting characters as needed.

Question 15

Why is the sequence comparison important in fields like bioinformatics?

Answer 15

It is used to align and compare DNA or protein sequences, estimate evolutionary distances, and detect mutations or variations.

Question 16

Give an example where a subset-sum could be applied in real life.

Answer 16

Subset sum can be used in finance to determine combinations of cash denominations to reach a specific amount without overpaying.

Question 17

How can dynamic programming help in approximate text matching?

Answer 17

DP can align keywords with text, allowing slight variations due to misspellings or grammatical differences for efficient information retrieval.

Question 18

What’s an example of a segmentation problem in data analysis?

Answer 18

Partitioning data sequences into nearly linear segments with minimal deviation helps in understanding trends and patterns in time-series analysis.