\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{BrKn}
\pdfinfo{
  /Title (cmpe-250-mt1.pdf)
  /Creator (Cheatography)
  /Author (BrKn)
  /Subject (CmpE 250 MT1 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}{A36264}
\definecolor{LightBackground}{HTML}{F9F5F5}
\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{CmpE 250 MT1 Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{BrKn} via \textcolor{DarkBackground}{\uline{cheatography.com/209033/cs/44937/}}}
\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}BrKn \\
  \uline{cheatography.com/brkn} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Not Yet Published.\\
   Updated 10th November, 2024.\\
   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*}{4}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Abstract Data Types (ADT)}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{List}}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Stack}}} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Queue}}} \tn 
% Row Count 3 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Data Abstraction:}} Separation of a data type's logical properties from its implementation. \newline -{\bf{Logical Properties}} \newline -{}-What are the possible values? What operations will be needed? \newline -{\bf{Implementation}} \newline -{}-How can this be done in Java, C++, or any other programming language? \newline  \newline {\bf{ADT}} is a set of objects together with a set of operations. A data type that does not describe or belong to any specific data, yet allows the specification of organization and manipulation of data.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.61794 cm} x{2.81506 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{List Operations}}  \tn
% Row 0
\SetRowColor{LightBackground}
Find & (First occurrence) \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Insert} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Remove} \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{FindKth} \tn 
% Row Count 4 (+ 1)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{MakeEmpty} \tn 
% Row Count 5 (+ 1)
% Row 5
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{PrintList} \tn 
% Row Count 6 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{List Implementations}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Simple Array} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Simple (Singly) Linked List} \tn 
% Row Count 2 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Stack - LIFO (Last In First Out) List Operations}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Push} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Pop} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Top (Peek)} \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{MakeEmpty} \tn 
% Row Count 4 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.6866 cm} x{2.7464 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Stack Implementations}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Array} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\seqsplit{LinkedList} & Operations take {\bf{constant}} time. Size can grow/shrink easily. \tn 
% Row Count 3 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Overflow}}: When element count in an array exceeds array size. \newline {\bf{Underflow}}: Pop from an empty stack. \newline  \newline {\bf{Evaluate infix expressions}}, 2 stacks algorithm (Dijkstra): \newline -{}-{\emph{Value}}: Push onto the value stack. \newline -{}-{\emph{Operator}}: Push onto the operator stack. \newline -{}-{\emph{Left parenthesis}}: Ignore. \newline -{}-{\emph{Right parenthesis}}: Pop operator and two values; push the result of applying that operator to those values onto the operand (value) stack.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Queue - First In Last Out List Operations}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Enqueue} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Dequeue} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{MakeEmpty} \tn 
% Row Count 3 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Queue Implementations}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Circular Array (Circular Queue)} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Linked List} \tn 
% Row Count 2 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\emph{Examples:}} \newline -Calls to a call center \newline -Jobs in the printer \newline -Network operations on routers \newline -CPU usage queues}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.13289 cm} x{2.30011 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Trees}}  \tn
% Row 0
\SetRowColor{LightBackground}
Tree & Collection of {\bf{nodes}} such that: \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
Root & Unless empty, trees have a {\bf{root}}. \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
Subtrees & Remaining nodes are partitioned into trees themselves, called {\bf{subtrees}}. Each subtree is connected by a {\bf{directed edge}} from the {\bf{root}}. \tn 
% Row Count 10 (+ 6)
% Row 3
\SetRowColor{white}
Degree & Number of {\bf{subtrees}} of a node. \tn 
% Row Count 12 (+ 2)
% Row 4
\SetRowColor{LightBackground}
Leaf / Terminal Node & Node with {\bf{degree}} 0. \tn 
% Row Count 14 (+ 2)
% Row 5
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Parent} \tn 
% Row Count 15 (+ 1)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Child} \tn 
% Row Count 16 (+ 1)
% Row 7
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Ancestors} \tn 
% Row Count 17 (+ 1)
% Row 8
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Path from node\textasciitilde{}1\textasciitilde{} to node\textasciitilde{}k\textasciitilde{}} \tn 
% Row Count 18 (+ 1)
% Row 9
\SetRowColor{white}
Depth & Length of the unique {\bf{path}} from {\bf{root}} to node. \tn 
% Row Count 20 (+ 2)
% Row 10
\SetRowColor{LightBackground}
Height & Length of the {\bf{longest}} {\emph{downward}} path from the node to a {\bf{leaf}}. \tn 
% Row Count 23 (+ 3)
% Row 11
\SetRowColor{white}
Height of a Tree & {\bf{Height}} of the {\bf{root}}. \tn 
% Row Count 25 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{For its implementation, a node can hold: \newline -Its first child. \newline -Its next sibling. \newline Thus siblings would be held as a {\bf{linked list}}. \newline Without parent/previous sibling information, each node holds only 2 references.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{0.89258 cm} x{2.54042 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Binary Tree}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Each node can have at most {\bf{2}} children.} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
{\bf{Full BT}} & When each node has 2 or 0 children. \tn 
% Row Count 3 (+ 2)
% Row 2
\SetRowColor{LightBackground}
{\bf{Perfect BT}} & It's full and each leaf has the {\bf{same depth}}. \tn 
% Row Count 5 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.61794 cm} x{2.81506 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Tree Traversal}}  \tn
% Row 0
\SetRowColor{LightBackground}
\seqsplit{Preorder} & Parent first. \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
 & Visit root. Traverse left subtree. Traverse right subtree. \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\seqsplit{Postorder} & Parent last. \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
 & Traverse left subtree. Traverse right subtree. Visit root. \tn 
% Row Count 8 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\seqsplit{Inorder} & Left-Parent-Right \tn 
% Row Count 9 (+ 1)
% Row 5
\SetRowColor{white}
 & Traverse left subtree. Visit root. Traverse right subtree \tn 
% Row Count 11 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Search Tree ADT - Binary Search Tree}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Provides {\bf{inorder}} traversal.} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Average}} case: {\bf{Depth}} of all nodes on average log(N)} \tn 
% Row Count 3 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Balanced}} BST maintains all operations at {\bf{h=O(logN)}} time} \tn 
% Row Count 5 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.0299 cm} x{2.4031 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{AVL (Adelson-Velskii and Landis) Tree}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{It's a BST.} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Height of the left subtree and the right subtree differ by {\bf{at most 1}}.} \tn 
% Row Count 3 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Empty tree has height {\bf{-1}}.} \tn 
% Row Count 4 (+ 1)
% Row 3
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Balancing After Insertion} \tn 
% Row Count 5 (+ 1)
% Row 4
\SetRowColor{LightBackground}
Left-Left & Single Right Rotation \tn 
% Row Count 6 (+ 1)
% Row 5
\SetRowColor{white}
Right-Right & Single Right Rotation \tn 
% Row Count 7 (+ 1)
% Row 6
\SetRowColor{LightBackground}
Left-Right & Double Left-Right Rotation \tn 
% Row Count 8 (+ 1)
% Row 7
\SetRowColor{white}
Right-Left & Double Right-Left Rotation \tn 
% Row Count 9 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{- \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline -}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.7165 cm} x{1.7165 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Algorithm Analysis}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\emph{Problem Solving: Life Cycle}}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Problem Definition}}}}} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
Functional Requirements & Calculate the mean of n numbers etc. {\bf{What}} should the program do? \tn 
% Row Count 6 (+ 4)
% Row 3
\SetRowColor{white}
Nonfunctional Requirements & Performance Requirements: How fast should it run? etc. {\bf{How}} should the program do? Can be considered as {\bf{Quality Attributes}} \tn 
% Row Count 13 (+ 7)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Algorithm Design}}}}} \tn 
% Row Count 14 (+ 1)
% Row 5
\SetRowColor{white}
Algorithm & A clearly specified set of instructions for the program to follow. \tn 
% Row Count 18 (+ 4)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Knuth's Characterization}} (5 properties as requirements for an algorithm)} \tn 
% Row Count 20 (+ 2)
% Row 7
\SetRowColor{white}
\textasciitilde{}{\bf{Input}} & 0 or more, {\bf{externally produced}} quantities \tn 
% Row Count 23 (+ 3)
% Row 8
\SetRowColor{LightBackground}
\textasciitilde{}{\bf{Output}} & 1 or more quantities \tn 
% Row Count 24 (+ 1)
% Row 9
\SetRowColor{white}
\textasciitilde{}{\bf{Definiteness}} & Clarity, precision of each instruction \tn 
% Row Count 26 (+ 2)
% Row 10
\SetRowColor{LightBackground}
\textasciitilde{}{\bf{Finiteness}} & The algorithm has to stop after a finite amount of steps \tn 
% Row Count 29 (+ 3)
% Row 11
\SetRowColor{white}
\textasciitilde{}{\bf{Effectiveness}} & Each instruction has to be basic enough and feasible \tn 
% Row Count 32 (+ 3)
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{x{1.7165 cm} x{1.7165 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Algorithm Analysis (cont)}}  \tn
% Row 12
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Algorithm Analysis}}}}} \tn 
% Row Count 1 (+ 1)
% Row 13
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Given an algorithm, will it satisfy the requirements?} \tn 
% Row Count 3 (+ 2)
% Row 14
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Given a number of algorithms to perform the same computation, which one is "best"?} \tn 
% Row Count 5 (+ 2)
% Row 15
\SetRowColor{white}
The analysis required to estimate the "resource use" of an algorithm & Space and Time Complexity \tn 
% Row Count 9 (+ 4)
% Row 16
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Implementation}}}}} \tn 
% Row Count 10 (+ 1)
% Row 17
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Testing}}}}} \tn 
% Row Count 11 (+ 1)
% Row 18
\SetRowColor{LightBackground}
{\bf{{\emph{Maintenance}}}} & Bug fixes, version management, new features etc. \tn 
% Row Count 14 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{0.99557 cm} x{2.43743 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Space Complexity}}  \tn
% Row 0
\SetRowColor{LightBackground}
Space Complexity & The amount of memory required by an algorithm to run to completion \tn 
% Row Count 3 (+ 3)
% Row 1
\SetRowColor{white}
Fixed Part & The size required to store certain data/variables, that is {\bf{independent of the size}} of the problem, eg. name of the input/output files, \tn 
% Row Count 8 (+ 5)
% Row 2
\SetRowColor{LightBackground}
Variable Part & Space needed by variables, whose size is {\bf{dependent on the size}} of the problem. \tn 
% Row Count 11 (+ 3)
% Row 3
\SetRowColor{white}
S(P)=c+S\textasciitilde{}p\textasciitilde{} & c = constant, S\textasciitilde{}p\textasciitilde{} = instance characteristics which depends on a particular instance \tn 
% Row Count 14 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.7165 cm} x{1.7165 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Pseudocode}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Control Flow}}}}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{if... then... {[}else...{]}} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{while... do...} \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{repeat... until...} \tn 
% Row Count 4 (+ 1)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{for... do...} \tn 
% Row Count 5 (+ 1)
% Row 5
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Indentation instead of braces} \tn 
% Row Count 6 (+ 1)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Method Declaration}}}}} \tn 
% Row Count 7 (+ 1)
% Row 7
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Algorithm Method (arg {[}, arg...{]})} \tn 
% Row Count 8 (+ 1)
% Row 8
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Input...} \tn 
% Row Count 9 (+ 1)
% Row 9
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Output} \tn 
% Row Count 10 (+ 1)
% Row 10
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Method Call}}}}} \tn 
% Row Count 11 (+ 1)
% Row 11
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{var.method(arg {[}, arg...{]})} \tn 
% Row Count 12 (+ 1)
% Row 12
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{MethodReturn Value}}}}} \tn 
% Row Count 13 (+ 1)
% Row 13
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{return expression} \tn 
% Row Count 14 (+ 1)
% Row 14
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{MethodExpressions}}}}} \tn 
% Row Count 15 (+ 1)
% Row 15
\SetRowColor{white}
← & Assignment ( = in code) \tn 
% Row Count 17 (+ 2)
% Row 16
\SetRowColor{LightBackground}
= & Equality Check (== in code) \tn 
% Row Count 19 (+ 2)
% Row 17
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Superscripts etc. mathematical formatting allowed} \tn 
% Row Count 20 (+ 1)
% Row 18
\SetRowColor{LightBackground}
{\bf{{\emph{Experimental Approach}}}} & Can't always use \tn 
% Row Count 22 (+ 2)
% Row 19
\SetRowColor{white}
{\bf{{\emph{Low Level Algorithm Analysis}}}} Using {\bf{Primitive Operations}} & {\bf{Make an addition = 1}} operation {\bf{Calling a method or returning from a method = 1}} operation {\bf{Index in an array = 1}} operation. {\bf{Comparison = 1 operation}}, etc. \tn 
% Row Count 31 (+ 9)
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{x{1.7165 cm} x{1.7165 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Pseudocode (cont)}}  \tn
% Row 20
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Method: Count the primitive operations to find O(f(n))} \tn 
% Row Count 2 (+ 2)
% Row 21
\SetRowColor{white}
{\bf{Growth rate}} of the running time T (n) is an {\bf{intrinsic property}} of an algorithm & Not dependent on hardware. \tn 
% Row Count 7 (+ 5)
% Row 22
\SetRowColor{LightBackground}
{\bf{Asymptotic Notation}} & Big-Oh, Big Omega, Big Theta, Little-Oh \tn 
% Row Count 9 (+ 2)
% Row 23
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Characterizing Algorithms As A Function Of Input Size}}}}} \tn 
% Row Count 11 (+ 2)
% Row 24
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Solving {\bf{Recursive}} Equations} \tn 
% Row Count 12 (+ 1)
% Row 25
\SetRowColor{white}
by {\bf{Repeated Substitution}} & \seqsplit{T(N)=T(N/2)+c=T(N/4)+c+c=}...=T(N/2\textasciicircum{}k\textasciicircum{})+kc, choose k = logN, \seqsplit{T(N)=T(1)+clogN=Θ(logN)} \tn 
% Row Count 17 (+ 5)
% Row 26
\SetRowColor{LightBackground}
by {\bf{Telescoping}} & T(N)=T(N/2)+c \tn 
% Row Count 18 (+ 1)
% Row 27
\SetRowColor{white}
 & T(N/2)=T(N/4)+c \tn 
% Row Count 19 (+ 1)
% Row 28
\SetRowColor{LightBackground}
 & ... \tn 
% Row Count 20 (+ 1)
% Row 29
\SetRowColor{white}
 & \seqsplit{+\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_} (cancelling opposite terms) \tn 
% Row Count 23 (+ 3)
% Row 30
\SetRowColor{LightBackground}
 & \seqsplit{T(N)=T(1)+clogN=Θ(logN)} \tn 
% Row Count 25 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{- \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline -}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{2.26578 cm} x{1.16722 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Dictionary ADT}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{A collection of (key, value) pairs such that each key appears at most once} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
{\emph{Idea}}: Use the key as the {\bf{index}} information to reach the key & {\bf{Key-Value Mapping}} \tn 
% Row Count 5 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Dictionary Operations}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Find} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Insert} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Remove} \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Note: No operations that require {\bf{\textasciitilde{}\textasciitilde{}ordering information\textasciitilde{}\textasciitilde{}}}} \tn 
% Row Count 5 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Dictionary Implementations}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Lists} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Binary Search Trees} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Hash Tables} \tn 
% Row Count 3 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.7165 cm} x{1.7165 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Hash Table}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Collision Resolving}}}}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
Separate Chaining & (Open Hashing) \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
Open Addressing & (Closed Hashing - Probing Hash Tables) \tn 
% Row Count 4 (+ 2)
% Row 3
\SetRowColor{white}
-{}-Open Hashing & Collisions are stored outside of the table \tn 
% Row Count 7 (+ 3)
% Row 4
\SetRowColor{LightBackground}
-{}-Closed Hashing & Collisions are stored at another slot in the table \tn 
% Row Count 10 (+ 3)
% Row 5
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Separate Chaining}}} \tn 
% Row Count 11 (+ 1)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Each cell in the hash table is the {\bf{head}} of a {\bf{linked list}}} \tn 
% Row Count 13 (+ 2)
% Row 7
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Elements are stored in the hash-specified linked list} \tn 
% Row Count 15 (+ 2)
% Row 8
\SetRowColor{LightBackground}
Records in the linked list can be ordered by: & order of insertion, key value, frequency of access \tn 
% Row Count 18 (+ 3)
% Row 9
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{λ = Load Factor}}} \tn 
% Row Count 19 (+ 1)
% Row 10
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{λ ≈ n/TableSize} \tn 
% Row Count 20 (+ 1)
% Row 11
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{insert, find, remove take O(1+λ) on average} \tn 
% Row Count 21 (+ 1)
% Row 12
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Closed Hashing (Probing Hash Tables)}}} \tn 
% Row Count 22 (+ 1)
% Row 13
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{h\textasciitilde{}i\textasciitilde{}(x) = (hash(x) + f(i)) mod TableSize, f(0)=0} \tn 
% Row Count 23 (+ 1)
% Row 14
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{f = {\bf{Collision Resolution Strategy}}} \tn 
% Row Count 24 (+ 1)
% Row 15
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{-{}-Linear Probing} \tn 
% Row Count 25 (+ 1)
% Row 16
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{-{}-Quadratic Probing} \tn 
% Row Count 26 (+ 1)
% Row 17
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{-{}-Double Hashing} \tn 
% Row Count 27 (+ 1)
% Row 18
\SetRowColor{LightBackground}
{\bf{{\emph{Linear Probing}}}} & {\bf{f(i)=i}} (linear function of i) \tn 
% Row Count 29 (+ 2)
% Row 19
\SetRowColor{white}
Primary Clustering & n\textless{}TableSize guarantees finding a free cell \tn 
% Row Count 32 (+ 3)
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{x{1.7165 cm} x{1.7165 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Hash Table (cont)}}  \tn
% Row 20
\SetRowColor{LightBackground}
 & Insertion time can get long due to {\bf{blocks of occupied cells}} are formed \tn 
% Row Count 4 (+ 4)
% Row 21
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\emph{Primary Clustering}} : Any key that hashes into the cluster -even if the keys map to different values- will require several attempts to resolve collusion and then it will be added to the cluster.} \tn 
% Row Count 8 (+ 4)
% Row 22
\SetRowColor{LightBackground}
Worst Case : find, insert & O(n) \tn 
% Row Count 10 (+ 2)
% Row 23
\SetRowColor{white}
Deletion requires {\bf{Lazy Deletion}} to not mess up the table & After many deletions may {\bf{reorganize}} the table \tn 
% Row Count 13 (+ 3)
% Row 24
\SetRowColor{LightBackground}
{\bf{{\emph{Quadratic Probing}}}} & {\bf{f(i)=i\textasciicircum{}2\textasciicircum{}}} (quadratic function of i) \tn 
% Row Count 15 (+ 2)
% Row 25
\SetRowColor{white}
 & Eliminates {\bf{primary clustering}} \tn 
% Row Count 17 (+ 2)
% Row 26
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Unless if {\bf{TableSize prime}} and {\bf{λ\textless{}1/2}}, cannot guarantee finding empty cell} \tn 
% Row Count 19 (+ 2)
% Row 27
\SetRowColor{white}
{\bf{Secondary Clustering}} & Elements that hash to the same position {\bf{probe}} to the same alternative cells, clustering there \tn 
% Row Count 24 (+ 5)
% Row 28
\SetRowColor{LightBackground}
{\bf{{\emph{Double Hashing}}}} & f(i)=i·hash\textasciitilde{}2\textasciitilde{}(x) (includes another hash function) \tn 
% Row Count 27 (+ 3)
% Row 29
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Example: hash\textasciitilde{}2\textasciitilde{}(x)=R - (x mod R), where R is a prime \textless{} TableSize} \tn 
% Row Count 29 (+ 2)
% Row 30
\SetRowColor{LightBackground}
{\bf{Rehashing}} & When λ too big, make bigger TableSize and {\bf{rehash}} everything. Takes O(n) but happens rarely.. \tn 
% Row Count 34 (+ 5)
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{x{1.7165 cm} x{1.7165 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Hash Table (cont)}}  \tn
% Row 31
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{ALL}}}} {\bf{Closed Hashing}} cannot work with {\bf{λ = 1}}} \tn 
% Row Count 2 (+ 2)
% Row 32
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{-{}-{\bf{Quadratic probing}} can fail if {\bf{λ \textgreater{} 0.5}}} \tn 
% Row Count 3 (+ 1)
% Row 33
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{-{}-{\bf{Linear probing}} and {\bf{Double hashing}} are slow if {\bf{λ \textgreater{} 0.5}}} \tn 
% Row Count 5 (+ 2)
% Row 34
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Open Hashing}} becomes slow once {\bf{λ \textgreater{} 2}}} \tn 
% Row Count 6 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Quadratic Probing Proof: \newline - \newline - \newline - \newline - \newline - \newline - \newline - \newline -}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.40753 cm} x{2.02547 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Cuckoo Hashing}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{2 hash tables} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
Only insert at the 1st table & Move the value in the 1st table if collision \tn 
% Row Count 3 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{May cause cycles but if λ\textless{}0.5, cycle probability low. Still possible, so specify maximum iteration count after which you rehash.}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{0.92691 cm} x{2.50609 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Time Complexity}}  \tn
% Row 0
\SetRowColor{LightBackground}
O(f(N)) = T(N) & T(N) ≤ cf(N) when N ≥ n0. {\bf{Upper-bound}} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
Ω(g(N)) = T(N) & T(N) ≥ cf(N) when N ≥ n0. {\bf{Lower-bound}} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
Θ(h(N)) = T(N) & T (N) = O(h(N)) and T (N) = Ω(h(N)) {\bf{Tight-bound (Exact)}} \tn 
% Row Count 7 (+ 3)
% Row 3
\SetRowColor{white}
o(p(N)) = T(N) & T(N) \textless{} cp(N) {\bf{Strict Upper-bound}} \tn 
% Row Count 9 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{f(N) is o(g(N)) if it's O(g(N)) but not Θ(g(N))} \tn 
% Row Count 10 (+ 1)
% Row 5
\SetRowColor{white}
O(1) & constant \tn 
% Row Count 11 (+ 1)
% Row 6
\SetRowColor{LightBackground}
O(logN) & logarithmic \tn 
% Row Count 12 (+ 1)
% Row 7
\SetRowColor{white}
O(log\textasciicircum{}2\textasciicircum{}N) & log-squared \tn 
% Row Count 13 (+ 1)
% Row 8
\SetRowColor{LightBackground}
O(N) & linear \tn 
% Row Count 14 (+ 1)
% Row 9
\SetRowColor{white}
O(N\textasciicircum{}2\textasciicircum{}) & quadratic \tn 
% Row Count 15 (+ 1)
% Row 10
\SetRowColor{LightBackground}
O(N\textasciicircum{}3\textasciicircum{}) & cubic \tn 
% Row Count 16 (+ 1)
% Row 11
\SetRowColor{white}
O(2\textasciicircum{}N\textasciicircum{}) & exponential \tn 
% Row Count 17 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{f(n)≤O(g(n)) is the wrong usage. You need to say f(n) {\bf{is (=) }} O(g(n))}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Priority Queues (Heaps)}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{For applications that require a sorted (but not fully sorted) order of procession of keys.} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Jobs sent to a printer, Simulation Environments (Discrete Event Simulators)} \tn 
% Row Count 4 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{p{0.3433 cm} p{0.3433 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Priority Queue Operations}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{insert} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{deleteMin} \tn 
% Row Count 2 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.3732 cm} x{2.0598 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Priority Queue Implementations}}  \tn
% Row 0
\SetRowColor{LightBackground}
Simple (Singly) Linked List & Insert O(1), deleteMin O(n) \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
Sorted Linked List & Insert O(n), deleteMin O(1) \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
Binary Search Tree (BST) & {\bf{Θ(logn) average}} for insert and deleteMin \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
Binary Heap & Can implement as a {\bf{single array}}, doesn't require {\bf{\textasciitilde{}\textasciitilde{}links\textasciitilde{}\textasciitilde{}}}, {\bf{O(logn) worst-case}} for insert and deleteMin \tn 
% Row Count 11 (+ 5)
% Row 4
\SetRowColor{LightBackground}
d-Heaps & Parents can have {\bf{d}} children \tn 
% Row Count 13 (+ 2)
% Row 5
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Leftist Heaps} \tn 
% Row Count 14 (+ 1)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Skew Heaps} \tn 
% Row Count 15 (+ 1)
% Row 7
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Binomial Queues} \tn 
% Row Count 16 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.68217 cm} x{1.75083 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Binary Heap}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\emph{Classic}} method for {\bf{priority queues}}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
Simply called {\bf{Heap}} & (Different from heap in {\bf{\textasciitilde{}\textasciitilde{}dynamic memory allocation\textasciitilde{}\textasciitilde{}}}) \tn 
% Row Count 4 (+ 3)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Structure Property}}}}} \tn 
% Row Count 5 (+ 1)
% Row 3
\SetRowColor{white}
{\bf{Heap}} is a {\bf{complete binary tree}} & {\bf{Complete binary tree}} is a BT filled completely, except maybe for the {\bf{bottom row}}, which is filled from {\bf{left-to-right}} \tn 
% Row Count 12 (+ 7)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{{\bf{Array implementation:}}} \tn 
% Row Count 13 (+ 1)
% Row 5
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{For any element in position {\bf{i}}:} \tn 
% Row Count 14 (+ 1)
% Row 6
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{-{}-{\bf{Left child}} is in position {\bf{2i}}} \tn 
% Row Count 15 (+ 1)
% Row 7
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{-{}-{\bf{Right child}} is in position {\bf{2i+1}} (after left child)} \tn 
% Row Count 17 (+ 2)
% Row 8
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{-{}-{\bf{Parent}} in position {\bf{⌊i/2⌋}}} \tn 
% Row Count 18 (+ 1)
% Row 9
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{{\bf{{\emph{Order Property}}}}} \tn 
% Row Count 19 (+ 1)
% Row 10
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Every {\bf{{\emph{parent}}}} is {\bf{smaller than or equal to}} its children, so {\bf{findMin}} is {\bf{O(1)}}} \tn 
% Row Count 21 (+ 2)
% Row 11
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{A {\bf{Max Heap}} is the reverse, allowing constant access to the max element} \tn 
% Row Count 23 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.44186 cm} x{1.99114 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Binary Heap Methods}}  \tn
% Row 0
\SetRowColor{LightBackground}
{\bf{insert}} & Insert element in {\bf{position 0}}. Find its possible position, make an empty node, then {\bf{percolate up}} until the {\bf{new element}} can be put into the empty position. \tn 
% Row Count 8 (+ 8)
% Row 1
\SetRowColor{white}
Worst case runtime is O(logn) & Average runtime is {\bf{constant}} \tn 
% Row Count 10 (+ 2)
% Row 2
\SetRowColor{LightBackground}
{\bf{deleteMin}} & Delete/make root empty,  put the {\bf{last element}} into array {\bf{position 0}}, {\bf{percolate down}} until the {\bf{last element}} can be put into the empty position. \tn 
% Row Count 17 (+ 7)
% Row 3
\SetRowColor{white}
Worst case runtime is O(logn) & Average runtime is also O(logn) since an element at the bottom is likely to still go down to the bottom. \tn 
% Row Count 22 (+ 5)
% Row 4
\SetRowColor{LightBackground}
{\bf{{\emph{Building a Heap}}}} & {\bf{Iterating insertion}}: O(NlogN) worst case. O(N) on average. \tn 
% Row Count 25 (+ 3)
% Row 5
\SetRowColor{white}
{\bf{buildHeap}} & First fill the leafs. \textasciitilde{}Half of the tree is filled already. Then, as you place the next elements, the subtrees will all be valid heaps - do {\bf{percolate down}}. Thus O(logHeight) operations for each node. \tn 
% Row Count 34 (+ 9)
\end{tabularx}
\par\addvspace{1.3em}

\vfill
\columnbreak
\begin{tabularx}{3.833cm}{x{1.44186 cm} x{1.99114 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Binary Heap Methods (cont)}}  \tn
% Row 6
\SetRowColor{LightBackground}
 & There are {\bf{more high depth nodes}} than {\bf{high height nodes}} in a heap thus buildHeap is a faster method, {\bf{O(N) worst case}} \tn 
% Row Count 6 (+ 6)
% Row 7
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Sum of all {\bf{heights}}:} \tn 
% Row Count 7 (+ 1)
% Row 8
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{S = logN + 2(logN - 1) + ... + 2\textasciicircum{}k\textasciicircum{}(logN - k), k=logN} \tn 
% Row Count 9 (+ 2)
% Row 9
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{2S = 2logN + ... + 2\textasciicircum{}k+1\textasciicircum{}(logN - k)} \tn 
% Row Count 10 (+ 1)
% Row 10
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{2S-S = 2+2\textasciicircum{}2\textasciicircum{}+...+2\textasciicircum{}k\textasciicircum{} - logN since k=logN thus 2\textasciicircum{}k+1\textasciicircum{}(logN-k)=0} \tn 
% Row Count 12 (+ 2)
% Row 11
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{S = 2\textasciicircum{}k+1\textasciicircum{}-2-logN} \tn 
% Row Count 13 (+ 1)
% Row 12
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{S = 2N - logN - 2 thus O(N)} \tn 
% Row Count 14 (+ 1)
% Row 13
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Sum of all depths:} \tn 
% Row Count 15 (+ 1)
% Row 14
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{S = 0 + 2·1 + 2\textasciicircum{}2\textasciicircum{}·2 + ... + 2\textasciicircum{}logN - 1\textasciicircum{}·(log\textasciicircum{}N\textasciicircum{} - 1)} \tn 
% Row Count 17 (+ 2)
% Row 15
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{S = NlogN-2N+2 thus O(NlogN)} \tn 
% Row Count 18 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{3.833cm}{x{1.47619 cm} x{1.95681 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{3.833cm}}{\bf\textcolor{white}{Priority Queue Applications}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{3.833cm}}{Operating System Design} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{Some Graph Algorithms} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
Selection and Sorting Problems & Given a list of N elements, and an integer k, the selection problem is to find the kth smallest element. \tn 
% Row Count 7 (+ 5)
% Row 3
\SetRowColor{white}
 & Take N elements, apply buildHeap, do deleteMin k times. \tn 
% Row Count 10 (+ 3)
% Row 4
\SetRowColor{LightBackground}
 & If k=N, we get a sorted list. This is heapSort which is O(NlogN) \tn 
% Row Count 13 (+ 3)
% Row 5
\SetRowColor{white}
\mymulticolumn{2}{x{3.833cm}}{} \tn 
% Row Count 13 (+ 0)
% Row 6
\SetRowColor{LightBackground}
Discrete Event Simulation & Instead of experimenting, put all events to happen in a queue. Advance clock to the next event each {\bf{tick}}. Events are stored in a heap to find the next one easily. \tn 
% Row Count 21 (+ 8)
% Row 7
\SetRowColor{white}
-{}-{\bf{Tick}} & A quantum unit \tn 
% Row Count 22 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}


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

\end{document}