diff options
| -rw-r--r-- | assignment10.tex | 113 |
1 files changed, 113 insertions, 0 deletions
diff --git a/assignment10.tex b/assignment10.tex new file mode 100644 index 0000000..96f138e --- /dev/null +++ b/assignment10.tex @@ -0,0 +1,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} + |