DAA HT23, Dynamic programming

Created: February 16, 2023 | About these notes | View in context | Study these flashcards

Flashcards

What two conditions characterises a problem that can be solved by dynamic programming?
  • The problem we wish to solve is the last in a list of subproblems
  • The solution of any subproblem can by constructed by the optimal solutions of smaller subproblems

What is “optimal substructure” in dynamic programming?

The property that the optimal solution of any subproblem can be constructed from the optimal solutions of smaller subproblems

Given positive integers $x _ 1 < \cdots < x _ n$ (representing the values of different coins) and a target value $u$, what is $C[u]$, the minimum number of coins needed to make value $u$, in terms of a recurrence?
\[C[u] = 1 + \min(C[u - x_i]: 1 \le i \le n, u \ge x_i)\]

Given a list of items with associated weights and values $[(w _ 1, v _ 1), \cdots, (w _ n, v _ n)]$, what recurrence characterises $K[w, j]$, the maximum value achievable with a knapsack of capacity $w$, choosing from items $1, \ldots, j$?
\[K[w, j] = \max(K[w - w_j, j-1] + v_j, K[w, j - 1])\]

What’s the first step when tackling a problem with dynamic programming?

Defining the recurrence using the problem’s optimal substructure.

In the context of edit distance between two strings, what counts as an edit?
  1. Insertion
  2. Deletion
  3. Substitution

What is an alignement of two words, in terms of edit distance?

An arrangement of the words on two lines, with the letters of one word on one line and the letters of the other word on the other line, possibly including blank characters.

Can you give an example alignement of the words “SNOWY” and “SUNNY”?

e.g.

\[\begin{matrix} \square \& S \& N \& O \& W \& \square \& Y \\\\ S \& U \& N \& \square \& \square \& N \& Y \end{matrix}\]

Define

\[E[i, j] = \text{edit distance between x[1..i] and y[1..j]}\]

where $\text x$ and $\text y$ are strings. What’s the optimal substructure here, i.e. what recurrence allows you to calculate $E[i, j]$ from a combination of smaller problems?
\[E[i, j] = \min(E[i-1, j] + 1, E[i, j - 1] + 1, E[i-1, j-1] + \delta(i, j))\]

where $\delta(i, j) = 0$ if $x[i] = y[j]$ and $1$ otherwise.

Using the recurrence

\[\begin{aligned} E[i, j] &= \text{edit distance between x[1..i] and y[1..j]} \\\\ &= \min(E[i-1, j] + 1, E[i, j - 1] + 1, E[i-1, j-1] + \delta(i, j)) \end{aligned}\]

where $\delta(i, j) = 0$ if $x[i] = y[j]$ and $1$ otherwise, compute the “edit table” for $\text{x = SNO}$ and $\text{y = SUN}$.
\[\begin{matrix} 0 \& 1 \& 2 \& 3 \\\\ 1 \& 0 \& 1 \& 2 \\\\ 2 \& 1 \& 1 \& 2 \\\\ 3 \& 2 \& 1 \& 2 \end{matrix}\]

How do divide-and-conquer and dynamic programming algorithms differ in terms of how much they cut down the problem?
  • Divide-and-conquer typically significantly cuts down the problem at each step
  • Dynamic programming only slightly reduces the problem at each step

How do divide-and-conquer and dynamic programming algorithms differ in terms of their application to optimisation?
  • Divide-and-conquer algorithms typically aren’t used for optimisation problems
  • Dynamic programming algorithms are

How do divide-and-conquer and dynamic programming problems differ in terms of how independent their subproblems are?
  • Divide-and-conquer problems typically have independent subproblems
  • Dynamic programming problems typically have overlapping subproblems

Implement an algorithm that solves the travelling salesperson problem in $O(n^2 2^n)$ time using dyanamic programming.

Todo.



Related posts