Start assignment 3

1 files changed, 133 insertions, 0 deletions

diff --git a/assignment3.tex b/assignment3.tex
new file mode 100644
index 0000000..29d6fae
--- /dev/null
+++ b/assignment3.tex
@@ -0,0 +1,133 @@
+\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 %todo
+
+    \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) {
+			    int i;
+			    Item prev = list.head
+			    Item cur = prev.next;
+			    for (i = 0; i < n; i++) {
+			        Item next = cur.next;
+			        cur.next = prev;
+			        prev = cur;
+			        cur = next;
+			    }
+			}
+        \end{minted}
+
+    \item %todo
+
+    \item \begin{minted}[linenos,xleftmargin=20pt,tabsize=0,fontsize=\footnotesize]{c}
+			int max(int* list, int m) {
+			    int i;
+			    int max = INT_MIN;
+			    for (i = 0; i < m; i++)
+			        if (list[i] > 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}{| l | l | l | l | l |}\hline
+                   & 12,44,13    & 88,23,94       & 11,39,20,16       & 5             \\\hhline{|=|=|=|=|=|}
+                0  &             &                & \textbf{20}       & 20            \\\hline
+                1  &             &                &                   &               \\\hline
+                2  &             &                &                   &               \\\hline
+                3  &             &                &                   &               \\\hline
+                4  &             &                & \textbf{16}       & \textbf{5},16 \\\hline
+                5  & \textbf{44} & \textbf{88},44 & \textbf{11},88,44 & 11,88,44      \\\hline
+                6  &             & \textbf{94}    & \textbf{39},94    & 39,94         \\\hline
+                7  & \textbf{12} & \textbf{23},12 & 23,12             & 23,12         \\\hline
+                8  &             &                &                   &               \\\hline
+                9  & \textbf{13} & 13             & 13                & 13            \\\hline 
+                10 &             &                &                   &               \\\hline
+            \end{tabular}
+        \end{minipage}
+\end{enumerate}
+
+\end{multicols}
+
+\end{document}
+