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