/
dynamicprogramming.tex
191 lines (167 loc) · 6.75 KB
/
dynamicprogramming.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
%========== Dynamic Programming ==========%
\chapter{Dynamic Programming}
\label{ch:dynamicprogramming}
\textbf{Pensum} 15 \cite{clrs} \\\\
\textbf{Assignments} 15-2, 16-1 \\\\
\textbf{Algorithms} Rod-cutting, fibonacci \\\\
\textbf{Keywords} Time-memory trade-off, memoization, top-down / bottom-up
\vspace{1in}
\noindent There are two key characteristics that a problem must have for
dynamic programming to be a viable solution; optimal substructure and
overlapping subproblems.
\\\\
\noindent \textbf{Optimal Substructure}\\
% p. 379
We say that a problem exhibits optimal substructure, when an optimal solution
to the problem contains within it optimal solutions to subproblems. We build
a solution for a problem from optimal solutions to its subproblems.
\\\\
\noindent \textbf{Overlapping Subproblems}\\
% p. 384 - TODO: make this more concise
When a recursive algorithm revisits the same problem repeatedly, we say that
the optimization problem has \textit{overlapping subproblems}. That is, we
solve the same subproblems, rather than generating new subproblems. % In
% contrast to the divide and conquer technique, where we generate and solve new
% subproblems that are smaller instances of the same type of problem, in dynamic
% programming we solve each subproblem once, and then storing the solution in a
% table, where it can be looked up when needed in $\Theta(1)$ time.
\newpage
\section{Discovering Optimal Substructure}
% p. 379-380
\begin{enumerate}
\item Show that a solution to the problem consists of making a choice.
Making this choice leaves one or more subproblems to be solved.
\item Suppose that for a given problem there exists a choice which leads
to an optimal substructure. Do not concern yourself with how to determine this
choice, but assume it has been given to you.
\item Given this choice, determine which subproblems ensue and how to best
characterize the resulting space of subproblems.
\item Using a "cut-and-paste" technique, show that the solutions to the
subproblems must themselves be optimal. You can do so by supposing that each
subproblem is not optimal and then deriving a contradiction.
\end{enumerate}
\section{Methods of Approach}
There are usually two equivalent ways to implement a dynamic-programming
approach; top-down with memoization and bottom-up.
\subsection{Top-down with Memoization}
% taken directly from the CLRS book, good summary I think.
In this approach, we write the procedure recursively in a natural manner, but
modified to save the result of each subproblem. The procedure checks to see
if it has already solved this problem. If so, it returns a saved value, saving
further computation at this level; if not, the procedure computes the value in
the usual manner. We say that the recursive procedure has been
\textit{memoized}; it "remembers" what results it has computed previously.
The caveat of using the top-down approach is that we make time-memory
trade-off, so what we gain in performance is payed in memory usage instead.
\subsection{Bottom-up}
% taken directly from the CLRS book, good summary I think.
This approach typically depends on some natural notion of the "size" of a
subproblem, such that solving any particular subproblem depends only on
solving "smaller" subproblems.
We sort the subproblems by size and solve them in size order, smallest first.
When solving a particular subproblem, we have already solved all of the
smaller subproblems its solution depends upon, and we saved their solutions.
We solve each subproblem only once, and when we first see it, we have already
solved all of its prerequisite subproblems.
\newpage
\section{Longest Common Subsequence}
% p. 390-396, CLRS
In the longest common subsequence problem we are given two sequences $X =
\langle x_1, x_2, \dots, x_m \rangle$ and $Y = \langle y_1, y_2, \dots, y_n
\rangle$, and we wish to find a subsequence of both $X$ and $Y$ of maximum
length.
\subsection{Optimal Substructure}
The brute-force approach would require exponential time, since the number of
subsequences of $X$ is $2^m$, making it impractical for large inputs.
The LCS-problem exhibits the optimal substructure property, however, which is
shown in the following theorem. First, we define the \textit{i}th prefix by
$Z_i = \langle z_1, z_2, \dots, z_i \rangle$, and $Z_0$ is the empty sequence.
\begin{theorem} \cite[thm. 15.1, p. 392]{clrs} \\
\label{thm:lcs-optimal-substructure}
Let $X = \langle x_1, x_2, \dots, x_m \rangle$
and $Y = \langle y_1, y_2, \dots, y_n \rangle$
be sequences, and let $Z = \langle z_1, z_2, \dots, z_k \rangle$ be any
LCS of $X$ and $Y$.
\textnormal
{
\begin{enumerate}
\item If $x_m = y_m$, then $z_k = x_m = y_n$ and $Z_{k-1}$ is an
LCS of $X_{m-1}$ and $Y_{n-1}$.
\item If $x_m \neq y_n$, then $z_k \neq x_m$ implies that $Z$ is an
LCS of $X_{m-1}$ and $Y$.
\item If $x_m \neq y_n$, then $z_k \neq y_n$ implies that $Z$ is an
LCS of $X$ and $Y_{n-1}$.
\end{enumerate}
}
\end{theorem}
% proof ?
\subsection{Overlapping subproblems}
Theorem \ref{thm:lcs-optimal-substructure} gives us two recursive cases; one
of which leaves us one subproblem, and the other two subproblems, which shows
that the LCS problem has overlapping subproblems.
We define value (length of the subsequence) of the recursive cases by the
table entry $c[i,j]$. This gives us a way to express the recursion.
\begin{align}
c[i,j] =
\begin{cases}
0 & \mbox{if $i = 0$ or $j = 0$} \\
c[i - 1, j - 1] + 1 & \mbox{if $i, j > 0$ and $x_i = y_j$} \\
max(c[i, j-1], c[i-1, j]) & \mbox{if $i, j > 0$ and $x_i \neq y_j$}
\end{cases}
\end{align}
\newpage
\subsection{Bottom-up solution}
The algorithm computes a table that represents all possible solutions, and
by tracing backward we can print the longest common subsequence.
\\\\
\begin{algorithm}[H]
\caption{Longest common subsequence, bottom-up.}
\label{alg:lcs-bottom-up}
\SetKwInOut{In}{Input}
\SetKwInOut{Out}{Output}
\SetKwFunction{LCS}{LCS}
\In{Takes two sequences $X$ and $Y$.}
\Out{A longest common subsequence of $X$ and $Y$.}
\BlankLine
\LCS($X$, $Y$) \\
\Begin
{
% initialization
$m = X.length$ \\
$n = Y.length$ \\
Let $c[0 \dots m, 0 \dots n]$ be a new table \\
\For{$i = 1$ \KwTo $m$}
{
$c[i, 0] = 0$
}
\For{$j = 1$ \KwTo $n$}
{
$c[0, i] = 0$
}
\For{$i = 1$ \KwTo $m$}
{
\For{$j = 1$ \KwTo $n$}
{
\uIf{$x_i == y_i$}
{
$c[i, j] = c[i-1,j-1] + 1]$ \\
$b[i, j] ={\ }\nwarrow$
}
\uElseIf{$c[i-1, j] \geq c[i, j-1]$}
{
$c[i, j] = c[i-1, j]$ \\
$b[i, j] ={\ }\uparrow$
}
\Else
{
$c[i, j] = c[i, j-1]$ \\
$b[i, j] ={\ }\leftarrow$
}
}
}
\Return $b$ and $c$
}
\end{algorithm}
\subsection{Analysis}
Each table entry takes $\Theta(1)$ to compute, and we do so exactly once, as
follows from the nested loop on lines 12--25. The running-time is $\Theta(mn)$.