commit f6c5fc80565bda0026ec572928102f49cf82015d
parent 784e34da8d2b08c15b96c564f1f78e00add9652e
Author: thing1 <thing1@seacrossedlovers.xyz>
Date: Sun, 17 May 2026 17:44:09 +0100
updated crib sheet
Diffstat:
1 file changed, 47 insertions(+), 1 deletion(-)
diff --git a/CS10720/crib/crib.tex b/CS10720/crib/crib.tex
@@ -10,6 +10,8 @@
\titleformat{\subsection} {\small} {\thesubsection: } {0em} {}[]
\titleformat{\subsubsection} {\small} {\thesubsubsection: } {0em} {} []
+\setlength{\parindent}{0pt}
+
\begin{document}
\section{Question 1}
\subsection{Part 1}
@@ -81,13 +83,57 @@ Leading 1 is dropped from mantissa, (number is always 1.10101... so we shorten t
\end{itemize}
\subsection{Part 3}
-multiply the matrix \textit{\textbf{BUH}}
+Multiply the matrix, rows by columns, must have the same number of rows as columns
+
+Size of matrix is given (row, column), not what you'd expect
\section{Question 2}
\subsection{Part 1}
+The halting problem is the idea that a program cant decide when a separate program is going to finish. This is because the program will need to run the separate program to check, and if the separate program never finishes, then the first program wont stop either.
+
+We will often use a proof by contradiction here, where we assume the halting problem is computable, and then establish it isn't.
\subsection{Part 2}
+A problem (mathamaticly) is a set of finite inputs from a finite alphabet, that in a finite number of states, will produce a finite number of outputs, from a finite alphabet
+
+\subsubsection{classes}
+Problems can be classed in the following order
+
+\begin{itemize}
+ \item all problems
+ \item computational problems --- arbitray inputs and outputs (finite alphabets)
+ \item optimisation problems --- arbitray input, an exact correct output
+ \item decision problems --- yes/no output
+\end{itemize}
+
+these types of problems, are all subsets of eachother, so a optimisation problem is a computational problem, which is a problem
+
\subsection{Part 3}
+If problem \textit{p} can be solved using problem \textit{q}, as part of its implementation, then problem \textit{p} \textbf{reduces} to problem \textit{q}
+
+This implies that problem \textit{p} is not much harder than problem \textit{q}
+
+If an algorithum for \textit{p} (given that \textit{p} reduces to \textit{q}) exists then an algorithum for \textit{q} can also not exist
\section{Question 3}
\subsection{Part 1}
+\begin{tabular}{| c | c | c | c |}
+ \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
+ merge & $ O(n \log(n)) $ & $ O(n \log(n)) $ & $ \log(n) $ \\ \hline
+ heap & $ O(n \log(n)) $ & $ O(n \log(n)) $ & 1 \\ \hline
+ quick & $ O(n \log(n)) $ & $ O(n^2) $ & 1 \\ \hline
+\end{tabular}
\subsection{Part 2}
+\begin{tabular}{| c | c |}
+ \hline
+ \textbf{symbol} & \textbf{meaning} \\ \hline
+ $ p = \Theta(q) $ & $ p = q $\\ \hline
+ $ p = \Omega(q) $ & $ p \ge q $\\ \hline
+ $ p = O(q) $ & $ p \le q $\\ \hline
+ $ p = \omega(q) $ & $ p > q $\\ \hline
+ $ p = o(q) $ & $ p < q $\\ \hline
+\end{tabular}
\subsection{Part 3}
+Write some code dumb dumb
\end{document}
