1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
\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}
|
