Finish assignment 3

1 files changed, 36 insertions, 7 deletions

diff --git a/assignment3.tex b/assignment3.tex
index 29d6fae..ffaa2af 100644
--- a/assignment3.tex
+++ b/assignment3.tex
@@ -62,7 +62,38 @@
 
         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 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:
 
@@ -78,10 +109,9 @@
 
     \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++) {
+			    for (int i = 0; i < n; i++) {
 			        Item next = cur.next;
 			        cur.next = prev;
 			        prev = cur;
@@ -90,13 +120,12 @@
 			}
         \end{minted}
 
-    \item %todo
+    \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 i;
 			    int max = INT_MIN;
-			    for (i = 0; i < m; i++)
+			    for (int i = 0; i < m; i++)
 			        if (list[i] > max)
 			            max = list[i];
 			    return max;
@@ -110,7 +139,7 @@
         \begin{minipage}{\linewidth}
             \centering
             \footnotesize
-            \begin{tabular}{| l | l | l | l | l |}\hline
+            \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