uni

commit 0702754025c275da624db57cf13758357a5b03ac
parent f6c5fc80565bda0026ec572928102f49cf82015d
Author: thing1 <thing1@seacrossedlovers.xyz>
Date:   Tue, 19 May 2026 11:58:48 +0100

updated crib

Diffstat:
M
CS10720/crib/crib.tex
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++----

1 file changed, 51 insertions(+), 4 deletions(-)
diff --git a/CS10720/crib/crib.tex b/CS10720/crib/crib.tex
@@ -1,4 +1,4 @@
-\documentclass[a4paper,10pt,twocolumn]{article}
+\documentclass[a4paper,11pt,twocolumn]{article}
 \usepackage[a4paper, total={6in, 8in}]{geometry}
 \usepackage[table]{xcolor}
 \usepackage{titling}
@@ -15,7 +15,6 @@
 \begin{document}
 \section{Question 1}
 \subsection{Part 1}
-Numbers
 
 \subsubsection{signed magnitude}
 Very simple, has sign bit at start, causes 2 versions of 0 (-0, 0)
@@ -82,6 +81,18 @@ Leading 1 is dropped from mantissa, (number is always 1.10101... so we shorten t
 	\item $ +0 == -0 $ is always \textbf{true}
 \end{itemize}
 
+\subsubsection{Special values}
+\begin{tabular}{| c | c | c | c |}
+	\hline
+	\textbf{Sign} & \textbf{Expo} & \textbf{Rest} & \textbf{Means} \\ \hline
+	0 & all 1's & 0 & $ + \infty $ \\ \hline
+	1 & all 1's & 0 & $ - \infty $ \\ \hline
+	any & all 1's & anything but 0 & NaN \\ \hline
+	0 & all 0's & 0 & $ + 0 $ \\ \hline
+	1 & all 0's & 0 & $ - 0 $ \\ \hline
+	any & all 0's & anything but 0 & Subnormal value  \\ \hline
+\end{tabular}
+
 \subsection{Part 3}
 Multiply the matrix, rows by columns, must have the same number of rows as columns
 
@@ -116,7 +127,7 @@ If an algorithum for \textit{p} (given that \textit{p} reduces to \textit{q}) ex
 \subsection{Part 1}
 \begin{tabular}{| c | c | c | c |}
 	\hline
-	\textbf{Algo} & \textbf{Best} & \textbf{Worst} & \textbf{mem} \\ \hline
+	\textbf{Algo} & \textbf{Best} & \textbf{Worst} & \textbf{Mem} \\ \hline
 	ins (left) & $ O(n ^ 2) $ & $ O(n ^ 2) $ & 1 \\ \hline
 	ins (right) & $ O(n) $ & $ O(n ^ 2) $ & 1 \\ \hline
 	ins (binary) & $ O(n \log(n)) $ & $ O(n ^ 2) $ & 1  \\ \hline
@@ -135,5 +146,41 @@ If an algorithum for \textit{p} (given that \textit{p} reduces to \textit{q}) ex
 	$ p =  o(q) $ & $ p < q $\\ \hline
 \end{tabular}
 \subsection{Part 3}
-Write some code dumb dumb
+\subsubsection{Heap sort}
+
+The heap must follow the rule, that the parent is larger than both of its children
+
+To find the left child of a node in a heap, use $ 2 i + 1 $
+
+To find the right child of a node in a heap, use $ 2 i + 2 $
+
+To find a node's parent use $ (j - 1) / 2 $
+
+To sort a max heap, do the following
+\begin{itemize}
+	\item Swap the first and last node (root of the tree and right most leaf)
+	\item Ignore the last node
+	\item Re-heap the array
+	\item Repeat
+\end{itemize}
+
+To perform re-heap, do the following from the root node
+\begin{itemize}
+	\item Find the largest child
+	\item Check if its a leaf
+	\item 
+		If it is
+		\begin{itemize}
+				\item Replace it with the root node
+				\item Move it into the position of its parent
+				\item Move elements up until the tree is filled
+		\end{itemize}
+	\item If it isn't, repeat from the selected node
+\end{itemize}
+
+To create the heap, call re-heap on the second half of the nodes, we only need to act on the second half of the list, as re-heaping the leafs, will fix their parents
+
+\subsubsection{Quick sort}
+The only strange thing here is the if statement in quicksort, it forces the program to sort the smaller half first, this causes a lower recursion depth
+
 \end{document}