<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[10pt,a4paper]{article}

\usepackage[margin=2cm]{geometry}
\usepackage{multicol}

\usepackage{enumitem}
\setenumerate[1]{label=1.\arabic*.}
\setenumerate[2]{label=\textit{\alph*})}

\usepackage{hhline}

% textcomp package is not available everywhere, and we only need the Copyright symbol
% taken from http://tex.stackexchange.com/a/1677/23992
\DeclareTextCommandDefault{\textregistered}{\textcircled{\check@mathfonts\fontsize\sf@size\z@\math@fontsfalse\selectfont R}}

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

\parindent0pt

\title{Algoritmen en Datastructuren - assignment 3}
\author{Camil Staps\\\small{s4498062}}

\begin{document}

\maketitle
\thispagestyle{fancy}

\begin{multicols}{2}

\begin{enumerate}
    \item Let \texttt{s1}, \texttt{s2} be two stacks over \texttt{X} with their operations \texttt{push(x:X)}, \texttt{X pop()} and \texttt{Bool empty()}. Then we define a queue \texttt{q} over \texttt{X} with the operations:

        \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{python}
			def q.enqueue(X x):
			    s1.push(x)
			
			def q.dequeue():
			    while (not s1.empty()):
			        s2.push(s1.pop())
			    x = s2.pop()
			    while (not s2.empty()):
			        s1.push(s2.pop())
			    return x
			
			def q.empty():
			    return s1.empty()
        \end{minted}

        \texttt{s1} usually holds the data. \texttt{enqueue} is but a wrapper for its \texttt{push}, and similar for \texttt{empty}. To get FIFO behaviour, we use \texttt{s2} to temporarily store data in \texttt{dequeue}. 

        Obviously, \texttt{enqueue} and \texttt{empty} need constant time. The \texttt{dequeue} method is in $\pazocal O(n)$ where $n$ is the size of \texttt{s1} or \texttt{q}: every element needs to popped and pushed twice, which can be done in constant time.

    \item Using a circular buffer:
        
        \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{c}
			typedef struct dequeue {
			    size_t head;
			    size_t tail;
			    int* array;
			    size_t size;
			} dequeue;
			
			void enqueueFront(dequeue q, int e) {
			    q.array[q.head] = e;
			    q.head = (q.head - 1) % q.size;
			}
			
			void enqueueEnd(dequeue q, int e) {
			    q.array[q.tail] = e;
			    q.tail = (q.tail + 1) % q.size;
			}
			
			int dequeueFront(dequeue q) {
			    q.head = (q.head + 1) % q.size;
			    return q.array[q.head];
			}
			
			int dequeueEnd(dequeue q, int e) {
			    q.tail = (q.tail - 1) % q.size;
			    return q.array[q.tail];
			}
        \end{minted}

        Obviously, we can lose data with this when the array is full. For this should be checked in the \texttt{enqueue} methods, and if necessary more space should be allocated for \texttt{q.array}. I did not include that in the example since it's not the point and a straightforward addition.

    \item We could use doubly-linked circular unsorted lists, say \texttt{l1} and \texttt{l2}. Then simply remap:

        \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{c}
			int* union(int* l1, int* l2) {
			    int* h1 = l1.head;
			    int* h2 = l2.head;
			    l1.head = l1.head.prev.next = h2;
			    l2.head = l2.head.prev.next = h1;
			    return l1;
			}
        \end{minted}

    \item \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{c}
			List* reverse(List* list, int n) {
			    Item prev = list.head
			    Item cur = prev.next;
			    for (int i = 0; i &lt; n; i++) {
			        Item next = cur.next;
			        cur.next = prev;
			        prev = cur;
			        cur = next;
			    }
			}
        \end{minted}

    \item We could implement \texttt{allocate-object} as \texttt{push} and \texttt{free-object} as \texttt{pop}. This will always occupy one block of memory (i.e. never different blocks spread over the memory).

    \item \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{c}
			int max(int* list, int m) {
			    int max = INT_MIN;
			    for (int i = 0; i &lt; m; i++)
			        if (list[i] &gt; max)
			            max = list[i];
			    return max;
			}
        \end{minted}

        In the worst case we need to loop through the whole table, so this has a worst case complexity of $\pazocal O(n)$.

    \item See the table below. Insertions that don't interfere are handled in one column. Changes are marked in bold.
        
        \begin{minipage}{\linewidth}
            \centering
            \footnotesize
            \begin{tabular}{| r | l | l | l | l |}\hline
                   &amp; 12,44,13    &amp; 88,23,94       &amp; 11,39,20,16       &amp; 5             \\\hhline{|=|=|=|=|=|}
                0  &amp;             &amp;                &amp; \textbf{20}       &amp; 20            \\\hline
                1  &amp;             &amp;                &amp;                   &amp;               \\\hline
                2  &amp;             &amp;                &amp;                   &amp;               \\\hline
                3  &amp;             &amp;                &amp;                   &amp;               \\\hline
                4  &amp;             &amp;                &amp; \textbf{16}       &amp; \textbf{5},16 \\\hline
                5  &amp; \textbf{44} &amp; \textbf{88},44 &amp; \textbf{11},88,44 &amp; 11,88,44      \\\hline
                6  &amp;             &amp; \textbf{94}    &amp; \textbf{39},94    &amp; 39,94         \\\hline
                7  &amp; \textbf{12} &amp; \textbf{23},12 &amp; 23,12             &amp; 23,12         \\\hline
                8  &amp;             &amp;                &amp;                   &amp;               \\\hline
                9  &amp; \textbf{13} &amp; 13             &amp; 13                &amp; 13            \\\hline 
                10 &amp;             &amp;                &amp;                   &amp;               \\\hline
            \end{tabular}
        \end{minipage}
\end{enumerate}

\end{multicols}

\end{document}

</pre></body></html>