\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}

