\documentclass{article}
\usepackage{amsmath}
\usepackage{program}
\usepackage{algorithmicx}
\usepackage{algorithm}
\usepackage{minted}
\usepackage{fancyvrb}

%\usepackage[margin=1in]{geometry}
%\usepackage{amsthm}
%\usepackage{parskip}
%\usepackage{amssymb}
\usepackage{fancyhdr}
%\usepackage{enumerate}
%\usepackage[bookmarksnumbered]{hyperref}
%\usepackage[english]{babel}
%\usepackage{dashrule}


%\newcommand{\R}{\mathbb{R}}
%\newcommand{\Z}{\mathbb{Z}}
%\newcommand{\N}{\mathbb{N}}
%\newcommand{\Q}{\mathbb{Q}}
%\newcommand{\C}{\mathbb{C}}
%\renewcommand{\P}{\mathbb{P}}
%\newcommand{\F}{\mathbb{F}}
%\newcommand{\D}{\mathbb{D}}
%\newcommand{\half}{\frac{1}{2}}

\usepackage{ textcomp }

%\newcommand{\A}{\mathcal{A}}
%\renewcommand{\H}{\mathcal{H}}
%\newcommand{\1}{\mathbb{1}}
%\newcommand{\teq}[1]{\stackrel{#1}{=}}
%\newtheorem{lemma}{Lemma}
%\newtheorem{theorem}[lemma]{Theorem}
%\newtheorem{definition}[lemma]{Definition}

\pagestyle{fancy}

\fancyhead[L]{Hand-in Assignment 1 (Algoritmiek)}
\fancyhead[R]{Thomas van Maaren (9825827)}


\begin{document}
\textbf{Exercise 1}

\begin{enumerate}
	\item \textit{What is your top-choice for this problem? (1)}

		The top-choice is the position of the last space.
	\item What is your subproblem for the top-choice you described above? (1)
		
		Let $y=y_1y_2\dots y_n$ be a string that we want to decode. A
		subproblem of
		this would be to decode $y_1y_{2}\dots y_{m}$ for any $1\leq m\leq n$.
	\item Write the subproblem for your top-choice as a recurrence relation. (2)

		If $\text{maxQuality}(y_1y_2\dots y_n)$ is the highest quality we can
		get from the sequence of letters $y_ry_2\dots y_n$ we see that
		$$\text{maxQuality}(y_1y_2\dots y_n)$$ $$ = \max\left(q(y_1y_2\dots y_m),\max_{2\leq m\leq n} \left(q(y_my_{m+1}\dots y_{n}) + \text{maxQuality}(y_1y_2\dots y_{m-1})\right)\right)$$
	\item Prove the optimality principle for your subproblem for the corresponding top-choice.(3)
		
		Consider a sequence of indices $S=\{i_1,\dots,i_k\}$ that gives us
		the choice of spaces that has the highest quality. Say $i_k=m$. Then
		$S\backslash \{i_k\} = \{i_1,\dots,i_{k-1}\}$ is a solution for the
		subproblem with $y_1\dots y_{m-1}$.
		Let $T=\{j_1,\dots,j_{k'}\}$ be an optimal solution of the subproblem
		$y'=y_1y_{2}\dots y_{m-1}$. We know that 
		
		\begin{align}&q(y_1y_2\dots y_{j_1-1})+q(y_{j_1}y_{j_1+1}\dots y_{j_2-1})+
			\dots+q(y_{j_{k'}}y_{j_{k'}+1}\dots y_{i_{k}-1}) \geq\label{ineq1}\\
			&q(y_1y_2\dots y_{i_1-1})+q(y_{i_1}y_{i_1+1}\dots y_{i_2-1})+
			\dots+q(y_{i_{k-1}}y_{j_{k-1}+1}\dots y_{i_{k}-1})\label{ineq2}
		\end{align}
		Because $S\backslash \{i_k\}$ is a solution. Note that 
		$S' = \{j_1,\dots,j_{k'},i_k\}$ is also a possible splitting
		of $y_1\dots y_n$. Because of \eqref{ineq1} and \eqref{ineq2} we see that

		\begin{align}&q(y_1y_2\dots y_{j_1-1})+
			\dots+q(y_{j_{k'}}y_{j_{k'}+1}\dots y_{i_{k}-1}) 
			+q(y_{j_{k}}y_{j_{k}+1}\dots y_n) 
			\geq\\
			&q(y_1y_2\dots y_{i_1-1})+
			\dots+q(y_{i_{k-1}}y_{j_{k-1}+1}\dots y_{i_{k}-1})
			+q(y_{i_{k}}y_{j_{k}+1}\dots y_{i_{n}})
		\end{align}
		Thus $S'$ has a higher or equal quality than $S$ and therefore
		it is again an optimal solution.
		
	\item Write a pseudocode for your algorithm and analyze its runtime. (3)

		If $y_1y_2\dots y_n$ is the string the following algorithm will give us the optimal
the space indices.


\begin{Verbatim}[numbers=left,xleftmargin=5mm]
    //O(n^2)
    for(m=1,...,n){ 
        //O(1)
        max[m] = q(y_1...y_m)
        //O(1)
        amount[m] =0
        //O(n)
	//If m=1 it will loop zero times
        for(l=2,...,m){
            //O(1)
            if(max[m] < q(y_l...y_m) + max[l-1]){
                //O(1)
                max[m] = q(y_l...y_m) + max[l-1]
                //O(1)
                amount[m] = 1+amount[l-1]
            }
        }
    }
    //O(1)
    k = amount[n]
    //O(1)
    previous_index = n
    //O(n)
    for(m=n,...,1){
        //O(1)
        if(max[m] + q(y_{m+1}...y_previous_index) == max[previous_index]){
            //O(1)
            i_k = m
            //O(1)
            k= k-1
            //O(1)
            previous_index = m
    }
    return(i_1...i_k)
\end{Verbatim}
%\begin{algorithm}
%\begin{algorithmic}
%\Function{Spaces}{$y_1y_2,\dots,y_n$}
%\For {$m = 1,\dots,n$}
%	\State $\text{max}_m \gets q(y_1\dots y_m)$
%	\State $\text{amount}_m \gets 0$
%	\For {$l=2,\dots,m$}
%		\If {$\text{max}_m < q(y_l,\dots,y_m) + \text{max}_{l-1}$}
%			\State $\text{max}_m \gets q(y_l,\dots,y_m) + \text{max}_{l-1}$
%			\State $\text{amount}_m \gets 1+\text{amount}_{l-1}$
%		\EndIf
%	\EndFor
%\EndFor
%\State $k \gets \text{amount}_n$
%\State $p \gets \text{max}_m$
%lastindex = n
%for m = n,...,1
%	if(k-q(y_m,...,y_lastindex) == max_m
%		i_k = m
%		k-=1
%		lastindex = m 
%		p = max_m
%

%\EndFor
%
%\EndFunction
%\end{algorithmic}
%\end{algorithm}

We shall now analyze the runtime. Because $q$ takes O(1) time it should be clear
that lines 9-15 take O(1) time. Because the for-loop in line 8 repeats $m-1\leq n$ time
we see that 8-16 takes O(n) time. We see that 3-7 take constant time, so because $O(1)+O(n) = O(n)$ we see that 3-16 take $O(n)$ time. We see that the for loop in line 2 repeats
$n$ times, so 1-17 take $O(n^2)$ time.

We see that 24-31 takes constant time and is repeated $n$ times, so 23-32 is O(n) time.
Because $O(n)+O(n^2) = O(n^2)$ we see that the time complexity is $O(n^2)$. This is a lot
better than going through all possibilities which had a time complexity of $O(2^n)$

\end{enumerate}

\end{document}