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
|
\documentclass[10pt,a4paper]{article}
\usepackage[margin=2cm,top=1cm]{geometry}
\usepackage{multicol}
\def\assignment{10}
\usepackage{enumitem}
\setenumerate[1]{label=\assignment.\arabic*.}
\setenumerate[2]{label=\textit{\alph*})}
\usepackage{fancyhdr}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\fancyhead{}
\fancyfoot[C]{Copyright {\textcopyright} 2015 Camil Staps}
\pagestyle{fancy}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
\usepackage{tikz}
\usepackage{array}
\usepackage{caption}
\usepackage[hidelinks]{hyperref}
\usepackage{url}
\usepackage{minted}
\parindent0pt
\title{Algoritmen en Datastructuren - assignment \assignment}
\author{Camil Staps\\\small{s4498062}}
\begin{document}
\maketitle
\thispagestyle{fancy}
\begin{enumerate}
\item If job $i$ is not contained in the set of optimal jobs, we know that $V[i]=V[i-1]$. However, if it \emph{is} contained in that set, that equality does not hold. There is however a small edge case when $v[i]=0$, in which case the job should always be included in the solution even though the above equality holds. Therefore, \textsc{Print-Jobs} is given by:
\begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{python}
def print_jobs(V, j):
for i in [j,j-1,...,1]:
if v[i] == 0 or V[i] != V[i-1]:
print(i)
\end{minted}
We walk through the array once, so this takes linear time.
\item We walk through the $c$ matrix from the bottom right to the top left. If for a cell $(j,i)$ we have $y[j]=x[i]$, we can go to $(j-1,i-1)$ and print $y[j]$, because the character there is in the LCS. If not, we can go either to $(j-1,i)$ or $(j,i-1)$ which would have the same value as $(j,i)$. This way, we print the number of characters that is in the bottom right of the $c$ table (the length of the LCS), and as argued above, all characters printed are in the LCS. Therefore, the algorithm is correct.
\begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{python}
def print_lcs(X, Y, c, i, j):
if c[i][j] == 0:
return
if X[i] == Y[j]:
print(X[i])
print_lcs(X, Y, c, i-1, j-1)
elif c[i][j-1] == c[i][j]:
print_lcs(X, Y, c, i, j-1)
elif c[i-1][j] == c[i][j]: # True
print_lcs(X, Y, c, i-1, j)
\end{minted}
We walk only upwards and leftwards through the $c$ matrix which is $m$ by $n$, so this takes $\pazocal O(m+n)$ time.
\item \begin{enumerate}
\item Let's walk through the matrix from $(i,j)$ to $(0,0)$. On every step we go either up or left. Then the simple recursion follows:
\begin{equation}
\label{eq:10.3}
P[i,j,k] = \begin{cases}
0 & \text{if $i=0$ or $j=0$ or $k<0$} \\
P\left[i-1,j,k-M[i,j]\right] + P\left[i,j-1,k-M[i,j]\right] & \text{otherwise}
\end{cases}
\end{equation}
\item Use a three-dimensional array to store $P[i,j,k]$ for all $0\le i\le m$, $0\le j\le n$, $0\le k\le C$. Iterate over $k$ in increasing order and then over $i$ and $j$ in increasing-sum order, so that the second case of \autoref{eq:10.3} always uses already computed values. Finally return $P[m,n,C]$.
Both cases of \autoref{eq:10.3} are executed in constant time because we only use already computed values in the second case. We only use the equation $(n+1)(m+1)(C+1)$ times, so this takes $\pazocal O(nmC)$ time.
\end{enumerate}
\item \begin{enumerate}
\item This is just the LCS problem with $Y=X^R$. So, as on the slide titled `Computing length of LCS':
\begin{equation*}
L[i,j] = \begin{cases}
0 & \text{if $i=0$ or $j=0$} \\
L[i+1,j-1] + 1 & \text{if $i,j>0$ and $s_i=s_j$} \\
\max(L[i,j-1], L[i+1,j]) & \text{otherwise}
\end{cases}
\end{equation*}
\item We discussed the LCS algorithm in the lecture, I'm assuming it is given by \texttt{c}.
\begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{python}
def longest_palindrome_subsequence(s):
l = list(s)
return c(s, s[::-1])
\end{minted}
The \texttt{c} algorithm depends on the bottom-up computation of itself with lower parameters, which is in this case equivalent to depending on the bottom-up computation of $L[i,j]$.
\texttt{c} runs in $\pazocal O(mn)$ as discussed, but here $m=n$, so that is $\pazocal O(n^2)$.
\end{enumerate}
\end{enumerate}
\end{document}
|
