DAA HT23, Dynamic programming
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?
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$?
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?
- Insertion
- Deletion
- 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?
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}$.
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
Suppose two burgulars have knapsacks of weight $W _ 1$ and $W _ 2$ respectively, and are attempting to rob a house containing $n$ items of weight and value $(w _ i, v _ i)$ respectively. What recurrence can you use to solve this problem with dynamic programming?:: Define $K[i, x, y]$ to be the maximum possible value attainable using items $\{1, \ldots, i\}$. Then
\[K[i, x, y] = \max\left(K[i-1, x, y], K[i-1, x-w_i, y] + v_i, K[i-1, x, y-w_i] + v_i \right)\]where $K[i-1, x-w _ i, y]$ or $K[i-1, x, y-w _ i]$ is included if $x-w _ i$ or $y-w _ i$ is positive.
Describe the table and pseudocode you’d use to solve the problem of whether there exists a Hamiltonian path in a graph.:: Let $H[v, S]$ represent whether there exists a path in the graph that visits every node in $S$ and ends at vertex $v$. Then
\[H[v, \\{v\\}] = \text{true}\]for each vertex $v$. Then iterate over each subset $S$ (this can be done by considering bit masks), and then iterate over each vertex $v$. If vertex $v$ is in $S$, then consider all vertices $u$ in the graph. If $H[u, S-\{v\}]$ and $u, v$ are adjacent, then mark $H[v, S]$ as true and break out of the loop. Then finally check if there’s any entries of $H[v, S]$ that are true where $S$ is the set of all vertices, and if so there exists a Hamiltonian circuit.
A maximum independent set of nodes in a tree is a largest set of nodes in which no nodes are connected. What recurrence could you define in order to find the size of the maximum independent set in linear time?:: Let $M[v]$ represent the largest maximum indpeendent set of the tree rooted at $v$. Then
\[M[v] = \max\left(\sum_{v'\text{ child}\\,} M[v'], 1 + \sum_{v'' \text{ grandchild}\\,} M[v''] \right)\]and each leaf node can be initialised to 1.
What is the “principle of optimality” in dynamic programming?
The solution to a problem is a function of optimal solutions to some of its subproblems.
For solving the travelling salesperson in $O(n^2 2^n)$, what subproblems, recurrence and base case do you use, and how do you find the length of the shortest cycle?:: Consider every subset $S \subseteq \{1, \ldots, n\}$ containing 1, and for every element $j \in S, j \ne 1$ find the shortest path that starts from 1 and ends in $j$, and passes only once through all the other nodes in $S$. Define $C[S, j]$ to be the length of the path. Then the recurrence is
\[C[S, j] = \min \\{C[S-\\{j\\}, i] + d_{ij} : i \in S - \\{1, j\\}\\}\]with the base case
\[C[\\{1\\}, 1] = 0\]Then the optimal solution is obtained by adding the node 1 to the end of the shortest path, so it becomes a cycle and taking the minimum over all entries with full subsets.
Programs
Implement a program that, given a list of positive integers $x _ 1 < \cdots < x _ n$ representing the values of different coins, and a target value $u$, finds the minimum number of coins needed to make a given value.
::
Todo.
Implement a program that, given a list of items with associated weights and associated values, finds the most valuable combination of items that doesn’t exceed capacity.
::
Todo.
Implement a program that finds the longest increasing subsequence in an array.
::
Todo.
Implement an algorithm that solves the travelling salesperson problem in $O(n^2 2^n)$ time using dyanamic programming.
::
Todo.