\documentclass{article}
\usepackage{program}
%\usepackage[margin=1in]{geometry}
%\usepackage{amsmath}
%\usepackage{amsthm}
%\usepackage{parskip}
%\usepackage{amssymb}
%\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}



\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-1}$ for any $2\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_{2\leq m\leq n} q(y_1y_2\dots y_{m-1}) + \text{maxQuality}(y_my_{m+1}\dots y_n)$$
		The base case is when $n=1$. Then $\text{maxQuality}(y_1) = q(y_1)$.
	\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_m\dots y_n$.
		Let $T=\{j_1,\dots,j_{k'}\}$ be an optimal solution of the subproblem
		$y'=y_my_{m+1}\dots y_n$. We know that 
		
		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$. 

		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{algorithm}
%\caption{Algorithm for finding the space indices that give the highest quality}\label{alg:cap}
%\begin{algorithmic}
%\While{$N \neq 0$}
%\If{$N$ is even}
%    \State $X \gets X \times X$
%    \State $N \gets \frac{N}{2}$  \Comment{This is a comment}
%\ElsIf{$N$ is odd}
%    \State $y \gets y \times X$
%    \State $N \gets N - 1$
%\EndIf
%\EndWhile
%\end{algorithmic}
%\end{algorithm}
%\begin{program}
%\mbox{A fast exponentiation procedure:}
%\BEGIN \\ %
%  \FOR i:=1 \TO 10 \STEP 1 \DO
%     |expt|(2,i); \\ |newline|() \OD %
%\rcomment{This text will be set flush to the right margin}
%\WHERE
%\PROC |expt|(x,n) \BODY
%          z:=1;
%          \DO \IF n=0 \THEN \EXIT \FI;
%             \DO \IF |odd|(n) \THEN \EXIT \FI;
%\COMMENT{This is a comment statement};
%                n:=n/2; x:=x*x \OD;
%             \{ n>0 \};
%             n:=n-1; z:=z*x \OD;
%          |print|(z) \ENDPROC
%\END
%\end{program}


%\begin{algorithm}
%  \caption{Example with a for loop}
%  \begin{algorithmic}
%    \For{$i = 1$ to $10$}
%      \State $i$ is now equal to \the\value{i}
%    \EndFor
%  \end{algorithmic}
%\end{algorithm}

\end{enumerate}

\end{document}