\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{AlexHoratio (Horatio)}
\pdfinfo{
  /Title (wjec-a2-computing-unit-3-1-3-3.pdf)
  /Creator (Cheatography)
  /Author (AlexHoratio (Horatio))
  /Subject (WJEC A2 Computing Unit 3.1-\textgreater{}3.3 Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{A3A3A3}
\definecolor{LightBackground}{HTML}{F3F3F3}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{WJEC A2 Computing Unit 3.1-\textgreater{}3.3 Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{AlexHoratio (Horatio)} via \textcolor{DarkBackground}{\uline{cheatography.com/21127/cs/16024/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}AlexHoratio (Horatio) \\
  \uline{cheatography.com/horatio} \\
        \uline{\seqsplit{alexhoratiogamedev}.blogspot.com}
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 7th June, 2018.\\
   Updated 7th June, 2018.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{3}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Records}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Made up of multiple {\bf{fields}}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Each {\bf{field}} consists of a single data type} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Each record is processed as a single item} \tn 
% Row Count 3 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Binary Trees}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Binary trees}} are tree entities wherein each element has no more than two children.} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Pre-Order Traversal}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}1. {\bf{Root}} \{\{nl\}\} 2. {\bf{Left}} \{\{nl\}\} 3. {\bf{Right}}} \tn 
% Row Count 5 (+ 3)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{In-Order Traversal}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}1. {\bf{Left}} \{\{nl\}\} 2. {\bf{Root}} \{\{nl\}\} 3. {\bf{Right}}} \tn 
% Row Count 8 (+ 3)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{Post-Order Traversal}}} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}1. {\bf{Left}} \{\{nl\}\} 2. {\bf{Right}} \{\{nl\}\} 3. {\bf{Root}}} \tn 
% Row Count 11 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{De Morgan's Law}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{De Morgan's law states that {\bf{NOT(A OR B)}} is the same as {\bf{NOT(A) AND NOT(B)}}.} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Also, {\bf{NOT(A AND B)}} is the same as {\bf{NOT(A) OR NOT(B)}}.} \tn 
% Row Count 4 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Recursion}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{A {\bf{recursive}} function is a function that calls itself repeatedly until a certain condition is met, at which point it "collapses" and returns a result.} \tn 
% Row Count 4 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.54287 cm} x{3.43413 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Data Validatio}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Presence Check}} & This check ensures that {\emph{something}} has been entered. \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\bf{Range Check}} & Ensures that data is within a given range. \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
{\bf{Type Check}} & Checks to make sure the data is of the correct type(i.e Integer, String, Float) \tn 
% Row Count 7 (+ 3)
% Row 3
\SetRowColor{white}
{\bf{Format Check}} & Ensures that the data follows a particular format (for use with Post Codes) \tn 
% Row Count 10 (+ 3)
% Row 4
\SetRowColor{LightBackground}
{\bf{List Check}} & Ensures that data is one of a given list of options, for example "M", "F" or "X" for a gender check \tn 
% Row Count 14 (+ 4)
% Row 5
\SetRowColor{white}
{\bf{Length Check}} & Make sure that the data is of the correct length(in terms of characters, digits or elements) \tn 
% Row Count 18 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Dijkstra's Pathfinding Algorithm}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{1}}. Start from the first vertex, named {\bf{A}}.} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{2}}. Work out the weight from the A to each other connected node, in this case {\bf{B}} and {\bf{C}}. Add these costs to a list and order the list from lowest cost to highest.} \tn 
% Row Count 5 (+ 4)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{3}}. "Move" to the node that has the lowest cost in the list.} \tn 
% Row Count 7 (+ 2)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{4}}. Calculate the cost to move from A to any nodes adjacent to the currently visited node, and add these costs to the list.} \tn 
% Row Count 10 (+ 3)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{5}}. Ignore longer routes(for instance, going from A to B to C rather than A to C)} \tn 
% Row Count 12 (+ 2)
% Row 5
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{{\bf{6}}. Repeat steps 2-\textgreater{}5 until you arrive at your destination.} \tn 
% Row Count 14 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Stacks}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Stacks are {\bf{LIFO}}({\bf{L}}ast {\bf{I}}n, {\bf{F}}irst {\bf{O}}ut), so items can be {\bf{pushed}} or {\bf{popped}} from the top of the stack} \tn 
% Row Count 3 (+ 3)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Stacks may be used for: \{\{nl\}\} {\bf{1.}} Storing return addresses \{\{nl\}\} {\bf{2.}} Storing intermediate steps in arithmetic operations \{\{nl\}\} {\bf{3.}} Interrupts} \tn 
% Row Count 7 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Hash Tables}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{A {\bf{hash table}} is composed of both a {\bf{table of data}} and a {\bf{key}}. The key is a smaller file which identifies the location of a specific piece of data in the much larger table.} \tn 
% Row Count 4 (+ 4)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{A hashing calculation is performed on each piece of data before it is placed into the table. The location it is placed at is determined via the result of the hash.} \tn 
% Row Count 8 (+ 4)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{If there is a hash collision, one of two things will happen:} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}1. {\bf{Chaining}} - This is where a list is created in the memory location where a collision has occurred and each element that is stored there becomes an element in that list. \{\{nl\}\} 2. {\bf{Rehashing}} - This involves running another hashing algorithm on the result of the first hash to obtain a new memory location.} \tn 
% Row Count 17 (+ 9)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{1.84149 cm} x{3.13551 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Data Verification}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Screen Verification}} & This is a visual check to ensure that no errors have been made. For instance, sending the data back to the source to check over it. \tn 
% Row Count 6 (+ 6)
% Row 1
\SetRowColor{white}
{\bf{Double-Keying}} & This is where data is entered twice to confirm i.e passwords or e-mail addresses. \tn 
% Row Count 10 (+ 4)
% Row 2
\SetRowColor{LightBackground}
{\bf{Check Digit}} & This can be used for numerical data like credit card numbers or ISBNs, where one digit is the result of a mathematic calculation performed on the others. \tn 
% Row Count 17 (+ 7)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Lossy Compression}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Some of the data is "{\bf{lost}}" during compression} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Lossy data types include {\bf{JPEG}}, {\bf{MPEG}} or {\bf{MP3}}} \tn 
% Row Count 3 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Queues}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Queues are {\bf{FIFO}}({\bf{F}}irst {\bf{I}}n, {\bf{F}}irst {\bf{O}}ut).} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{These would be used for \{\{nl\}\} {\bf{1.}} Holding tasks for the computer to run \{\{nl\}\} {\bf{2.}} A keypress buffer \{\{nl\}\} {\bf{3.}} Spooling output to a disk while waiting for a printer} \tn 
% Row Count 6 (+ 4)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Graphs}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Graphs can relate any number of element to any other number of elements.} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{A {\bf{Weighted Graph}} is where there is a value on each edge which represents the "cost" of traversing it.} \tn 
% Row Count 5 (+ 3)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Graphs can either be {\bf{directed}} or {\bf{undirected}}.} \tn 
\mymulticolumn{1}{x{5.377cm}}{\hspace*{6 px}\rule{2px}{6px}\hspace*{6 px}1. A {\bf{directed}} graph is a graph wherein there is a one-way relationship between each node. \{\{nl\}\} 2. An {\bf{undirected}} graph is a graph wherein the relationship is bidirectional between each node.} \tn 
% Row Count 12 (+ 7)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.18988 cm} x{2.78712 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Data Flow Diagrams}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{What it looks like}} & {\bf{What it is}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
Weird Double-Square Lookin Thing & External Entity \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
Rounded Square & Process \tn 
% Row Count 5 (+ 1)
% Row 3
\SetRowColor{white}
Rectangle Missing the Right Edge & Data Storage \tn 
% Row Count 7 (+ 2)
% Row 4
\SetRowColor{LightBackground}
Arrow & Represents the flow of data(should be labelled) \tn 
% Row Count 10 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.4885 cm} x{2.4885 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Big-O Notation}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{Constant Time}} \{\{nl\}\} {\bf{O(1)}} & No matter how much data you give this algorithm, it will always execute in the same amount of time. \tn 
% Row Count 5 (+ 5)
% Row 1
\SetRowColor{white}
{\bf{Linear Time}} \{\{nl\}\} {\bf{O(n)}} & The time taken for the algorithm to run is directly proportional to the size of the input data. \tn 
% Row Count 10 (+ 5)
% Row 2
\SetRowColor{LightBackground}
{\bf{Polynomial Time}} \{\{nl\}\} {\bf{O(n\textasciicircum{}2\textasciicircum{})}} & The time taken increases proportional to the square(or cube, or any other power greater than one) of the input size. \tn 
% Row Count 16 (+ 6)
% Row 3
\SetRowColor{white}
{\bf{Exponential Time}} \{\{nl\}\} {\bf{O(2\textasciicircum{}n\textasciicircum{})}} & The time taken will double with every additional unit(or triple, etc- the 2 can be any number greater than one) of input data. \tn 
% Row Count 23 (+ 7)
% Row 4
\SetRowColor{LightBackground}
{\bf{Logarithmic Time}} \{\{nl\}\} {\bf{O(Log(n))}} & The time taken increases logarithmically, so the rate of increasing time with respect to input size actually decreases. \tn 
% Row Count 29 (+ 6)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Lossless Compression}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{No data is lost in the process, and the entire original file can be reconstructed.} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Another type of lossless compression is via {\bf{Dictionary Encoding}}, where the most frequent elements of data are removed and instead replaced with a "token" that points to the piece of data somewhere else in the file to prevent needless data duplication.} \tn 
% Row Count 8 (+ 6)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Also in {\bf{Huffman Coding}}, the most frequent elements of data are given the shortest token to maximize compression.} \tn 
% Row Count 11 (+ 3)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{One type of lossless compression is known as {\bf{Run Length Encoding}}, where strings of the same data(e.g, "BBBBBBBB") are replaced with the number of times to place the data in a row when decompressing it.(8B)} \tn 
% Row Count 16 (+ 5)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}