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