crib.tex (7629B)
1 \documentclass[a4paper,11pt,twocolumn]{article} 2 \usepackage[a4paper, total={6in, 8in}]{geometry} 3 \usepackage[table]{xcolor} 4 \usepackage{titling} 5 \usepackage{titlesec} 6 7 \geometry{a4paper,left=5mm,right=5mm,top=5mm,bottom=5mm} 8 9 \titleformat{\section} {\small} {\thesection: } {0em} {}[] 10 \titleformat{\subsection} {\small} {\thesubsection: } {0em} {}[] 11 \titleformat{\subsubsection} {\small} {\thesubsubsection: } {0em} {} [] 12 13 \setlength{\parindent}{0pt} 14 15 \begin{document} 16 \section{Question 1} 17 \subsection{Part 1} 18 19 \subsubsection{signed magnitude} 20 Very simple, has sign bit at start, causes 2 versions of 0 (-0, 0) 21 22 \begin{tabular}{| c | c | c | c | c | c | c | c |} 23 \hline 24 1 \cellcolor{red!40}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}\\ 25 \hline 26 \end{tabular} 27 28 \subsubsection{1's complement} 29 \textbf{MSB} is the complement of what you'd expect minus 1 ($ 128 \rightarrow -12 $ for 8 bit), also has double 0 30 31 \begin{tabular}{| c | c | c | c | c | c | c | c |} 32 \hline 33 1 \cellcolor{green!40}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}\\ 34 \hline 35 \end{tabular} 36 37 \subsubsection{2's complement} 38 \textbf{MSB} is the complement of what you'd expect ($ 128 \rightarrow -128 $ for 8 bit), and add 1 to the final number to avoid double 0 39 40 \begin{tabular}{| c | c | c | c | c | c | c | c |} 41 \hline 42 1 \cellcolor{green!40}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}\\ 43 \hline 44 \end{tabular} 45 46 \subsubsection{Excess} 47 Standard binary, with a shift (bias), subtracted from the number ( $ b=8, 1111 \rightarrow 7 $, $ 1111 $ is normally $ 15 $, but $ 15 - 8 = 7 $), no double 0 48 49 \begin{tabular}{| c | c | c | c | c | c | c | c |} 50 \hline 51 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}\\ 52 \hline 53 \end{tabular} 54 55 \subsubsection{Convertions} 56 57 \begin{tabular}{| c | c | c |} 58 \hline 59 \textbf{From} & \textbf{To} & \textbf{How} \\ \hline 60 1's & 2's & just add 1 \\ \hline 61 2's & 1's & just sub 1 \\ \hline 62 other & other & convert to dec, then back \\ \hline 63 \end{tabular} 64 65 \subsection{Part 2} 66 \subsubsection{IEEE 754} 67 16 bits, 1 sign bit, 5 bit exponent (excess), 10 bit mantissa (standard). 68 Leading 1 is dropped from mantissa, (number is always 1.10101... so we shorten to .10101) 69 70 \begin{tabular}{| c | c | c | c | c | c | c | c | c | c | c | c | c | c | c | c |} 71 \hline 72 1 \cellcolor{red!40}& 1 \cellcolor{green!30}& 1 \cellcolor{green!30}& 1 \cellcolor{green!30}& 1 \cellcolor{green!30}& 1 \cellcolor{green!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}& 1 \cellcolor{blue!30}\\ 73 \hline 74 \end{tabular} 75 76 \subsubsection{Comparison} 77 \begin{itemize} 78 \item NaN can't be compared, all operations involving it are \textbf{false} 79 \item $ + \infty $ is always \textbf{bigger} than any number 80 \item $ - \infty $ is always \textbf{smaller} than any number 81 \item $ +0 == -0 $ is always \textbf{true} 82 \end{itemize} 83 84 \subsubsection{Special values} 85 \begin{tabular}{| c | c | c | c |} 86 \hline 87 \textbf{Sign} & \textbf{Expo} & \textbf{Rest} & \textbf{Means} \\ \hline 88 0 & all 1's & 0 & $ + \infty $ \\ \hline 89 1 & all 1's & 0 & $ - \infty $ \\ \hline 90 any & all 1's & anything but 0 & NaN \\ \hline 91 0 & all 0's & 0 & $ + 0 $ \\ \hline 92 1 & all 0's & 0 & $ - 0 $ \\ \hline 93 any & all 0's & anything but 0 & Subnormal value \\ \hline 94 \end{tabular} 95 96 \subsection{Part 3} 97 Multiply the matrix, rows by columns, must have the same number of rows as columns 98 99 Size of matrix is given (row, column), not what you'd expect 100 \section{Question 2} 101 \subsection{Part 1} 102 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. 103 104 We will often use a proof by contradiction here, where we assume the halting problem is computable, and then establish it isn't. 105 \subsection{Part 2} 106 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 107 108 \subsubsection{classes} 109 Problems can be classed in the following order 110 111 \begin{itemize} 112 \item all problems 113 \item computational problems --- arbitray inputs and outputs (finite alphabets) 114 \item optimisation problems --- arbitray input, an exact correct output 115 \item decision problems --- yes/no output 116 \end{itemize} 117 118 these types of problems, are all subsets of eachother, so a optimisation problem is a computational problem, which is a problem 119 120 \subsection{Part 3} 121 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} 122 123 This implies that problem \textit{p} is not much harder than problem \textit{q} 124 125 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 126 \section{Question 3} 127 \subsection{Part 1} 128 \begin{tabular}{| c | c | c | c |} 129 \hline 130 \textbf{Algo} & \textbf{Best} & \textbf{Worst} & \textbf{Mem} \\ \hline 131 ins (left) & $ O(n ^ 2) $ & $ O(n ^ 2) $ & 1 \\ \hline 132 ins (right) & $ O(n) $ & $ O(n ^ 2) $ & 1 \\ \hline 133 ins (binary) & $ O(n \log(n)) $ & $ O(n ^ 2) $ & 1 \\ \hline 134 merge & $ O(n \log(n)) $ & $ O(n \log(n)) $ & $ \log(n) $ \\ \hline 135 heap & $ O(n \log(n)) $ & $ O(n \log(n)) $ & 1 \\ \hline 136 quick & $ O(n \log(n)) $ & $ O(n^2) $ & 1 \\ \hline 137 \end{tabular} 138 \subsection{Part 2} 139 \begin{tabular}{| c | c |} 140 \hline 141 \textbf{symbol} & \textbf{meaning} \\ \hline 142 $ p = \Theta(q) $ & $ p = q $\\ \hline 143 $ p = \Omega(q) $ & $ p \ge q $\\ \hline 144 $ p = O(q) $ & $ p \le q $\\ \hline 145 $ p = \omega(q) $ & $ p > q $\\ \hline 146 $ p = o(q) $ & $ p < q $\\ \hline 147 \end{tabular} 148 \subsection{Part 3} 149 \subsubsection{Heap sort} 150 151 The heap must follow the rule, that the parent is larger than both of its children 152 153 To find the left child of a node in a heap, use $ 2 i + 1 $ 154 155 To find the right child of a node in a heap, use $ 2 i + 2 $ 156 157 To find a node's parent use $ (j - 1) / 2 $ 158 159 To sort a max heap, do the following 160 \begin{itemize} 161 \item Swap the first and last node (root of the tree and right most leaf) 162 \item Ignore the last node 163 \item Re-heap the array 164 \item Repeat 165 \end{itemize} 166 167 To perform re-heap, do the following from the root node 168 \begin{itemize} 169 \item Find the largest child 170 \item Check if its a leaf 171 \item 172 If it is 173 \begin{itemize} 174 \item Replace it with the root node 175 \item Move it into the position of its parent 176 \item Move elements up until the tree is filled 177 \end{itemize} 178 \item If it isn't, repeat from the selected node 179 \end{itemize} 180 181 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 182 183 \subsubsection{Quick sort} 184 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 185 186 \end{document}