\documentclass[10pt,a4paper]{article}

\usepackage[margin=2cm,top=1cm]{geometry}

\def\assignment{11}

\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 \begin{enumerate}
            \item $19$.
            \item $2$.
            \item AE, EF, BF, FG, GH, CG, DG.
        \end{enumerate}

    \item See \autoref{tab:11.2}.

        \begin{table}[h]
            \centering
            \begin{tabular}{l | l | l | l}
                Added & Priority queue & Predecessors       & Keys \\\hline
                a     & e, b, c        & --                 & c:7, b:5, e:2 \\\hline
                e     & b, c, d        & e:a                & c:4, b:3, d:5 \\\hline
                b     & c, d           & e:a, b:e           & c:4, d:5 \\\hline
                c     & d              & e:a, b:e, c:e      & d:5 \\\hline
                d     & --             & e:a, b:e, c:e, d:c & --
            \end{tabular}
            \caption{Running Prim's algorithm}
            \label{tab:11.2}
        \end{table}

    \item Sort jobs ascending by finish time. For every activity:

        \begin{itemize}
            \item If it can be placed in any existing hall, do this.
            \item If not, add a new hall with just that activity.
        \end{itemize}

        This is a simple extension to the greedy algorithm seen in the lecture, it is correct by the same argument by contradiction.

        Sorting takes $\pazocal O(n\log n)$, iterating the array $\pazocal O(n)$, so this algorithm uses $\pazocal O(n\log n)$.

    \item \begin{enumerate}
            \item Define $m(i,w)$ as the maximum value we can reach with a maximum weight of $w$ and only using items $1$ to $i$. We can compute it using the following recurrence:

                \begin{equation*}
                    m(i,w) = \begin{cases}
                        0 & \text{if $i=0$} \\
                        m(i-1, w) & \text{if $w_i>w$} \\
                        \max(m(i-1, w), m(i-1,w-w_i) + v_i) & \text{otherwise}
                    \end{cases}
                \end{equation*}

                In the first case we cannot use any item, so obviously the maximum value is $0$. In the second case, item $w_i$ is heavier than the maximum weight, so the only possibility is to not use it. Therefore this case reduces to $m(i-1,w)$. In the last case we both consider the possibility of using item $i$ and of not using it.

                The solution to the problem is then $m(n,W)$. We can use a $n\times W$ matrix to store $m(i,w)$ for all $0\le i\le n, 0\le w\le W$. If we fill it starting with $i=0$, in all three cases we can use values we already computed. Computing the maximum of two numbers takes constant time, so the complexity of this algorithm is the complexity of filling the matrix, which is $\pazocal O(nW)$.

            \item Assume we already have our table with values of $m$. We can read it from $m(n,W)$ to the top left, and trace back what recurrence we used. Only when $m(i,w)=m(i-1,w-w_i)+v_i$ was applied, we need to output $i$.

                \begin{minted}[linenos,tabsize=0,xleftmargin=20pt,fontsize=\footnotesize]{python}
					i, j = n, W
					while m[i][j] != 0:
					    if m[i-1][j] == m[i][j]:
					        i = i - 1
					    else:
					        print(i - 1)
					        i = i - 1
					        j = j - w[i]
                \end{minted}

                In every step we decrease $i$, so this takes $\pazocal O(n)$.

        \end{enumerate}

    \item \begin{enumerate}
            \item Start with the set of intervals $I=\emptyset$. While $S$ is non-empty:
                \begin{enumerate}[ref=\roman*]
                    \item Extract the smallest $x_i$ from $S$.
                    \item Add $[x_i,x_i+1]$ to $I$. \label{11-5-a-choice}
                    \item Remove all $x_j$ with $x_j \in [x_i,x_i+1]$ from $S$.
                \end{enumerate}
                Return $I$.

            \item \begin{proof}
                    Suppose the algorithm was not correct. Then in step \ref{11-5-a-choice} we could have chosen a different interval containing $x_i$, all the $x_j$ from the next step \emph{and} at least one other $x_j'$. However, any other option for an interval would have a lower lower bound and a lower upper bound. Therefore, $x_j'<x_i$. However, since $x_i$ is minimal, this $x_j'$ cannot exist. Therefore, our choice of $[x_i,x_i+1]$ is optimal.
                \end{proof}

                The greedy choice is to take the interval which contains $x_i$ and as many as possible other values.

                I don't get the question about the optimal substructure, it's a term I only know from dynamic programming which doesn't apply here.
        \end{enumerate}

\end{enumerate}

\end{document}