\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{tskmster07}
\pdfinfo{
  /Title (cs570.pdf)
  /Creator (Cheatography)
  /Author (tskmster07)
  /Subject (cs570 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{cs570 Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{tskmster07} via \textcolor{DarkBackground}{\uline{cheatography.com/194777/cs/40679/}}}
\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}tskmster07 \\
  \uline{cheatography.com/tskmster07} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 6th October, 2023.\\
   Updated 6th October, 2023.\\
   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}{Runtime Complexity}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{5.377cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/tskmster07_1696613846_runtime_complexity.png}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{Formally: there exist constants c and n0 such that for all \newline sufficiently large n: f(n) ≤ c . g(n) \newline c,n0 n : n ≥ n0, f(n) ≤ c . g(n)}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Master theorem}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{T(n) = a·T(n/b) + f(n), a≥1 and b\textgreater{}1 \newline % Row Count 1 (+ 1)
let c  = log\_b a \newline % Row Count 2 (+ 1)
Case 1: (only leaves) if f(n) = O(n\textasciicircum{}c-e\textasciicircum{}), then T(n) = Theta(n\textasciicircum{}c\textasciicircum{}) for some e\textgreater{}0 \newline % Row Count 4 (+ 2)
Case 2: (all nodes) if f(n) = theta(n\textasciicircum{}c\textasciicircum{} log\textasciicircum{}k\textasciicircum{} n) , k≥0 , T(n) = theta(n\textasciicircum{}c\textasciicircum{} log\textasciicircum{}k+1\textasciicircum{}n) \newline % Row Count 6 (+ 2)
Case 3: (only internal nodes) if f(n) = omega(n\textasciicircum{}c+e\textasciicircum{}), then T(n) = theta(f(n)) for some e\textgreater{}0% Row Count 8 (+ 2)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Kruskals Algorithm}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Sort all edges by their weights \newline % Row Count 1 (+ 1)
Loop: \newline % Row Count 2 (+ 1)
- Choose the minimum weight edge and join correspondent vertices (subject to cycles). \newline % Row Count 4 (+ 2)
- Go to the next edge. \newline % Row Count 5 (+ 1)
- Continue to grow the forest until all vertices are connected \newline % Row Count 7 (+ 2)
Runtime Complexity: \newline % Row Count 8 (+ 1)
Sorting edges – O(E log E) \newline % Row Count 9 (+ 1)
Cycle detection – O(V) for each edge \newline % Row Count 10 (+ 1)
Total: O(V * E + E * log E)% Row Count 11 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Depth-First-Search (DFS)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{It starts at a selected node and explores as far as possible along each branch before backtracking. DFS uses a stack for backtracking% Row Count 3 (+ 3)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Breadth-First-Search (BFS)}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{It starts at a selected node and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. BFS uses a FIFO queue for bookkeeping% Row Count 4 (+ 4)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Amortized Analysis}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Aggregate method: The amortized cost of an operation is given by 𝑇(𝑛) / 𝑛 \newline % Row Count 2 (+ 2)
Accounting Method: We assign different charges to each operation; some operations may charge more or less than they actually cost.% Row Count 5 (+ 3)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Topological Sort}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{1. Select a vertex that has zero in-degree. \{\{nl\}\} 2. Add the vertex to the output. \{\{nl\}\} 3. Delete this vertex and all its outgoing edges. \{\{nl\}\} 4. Repeat% Row Count 4 (+ 4)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Coin Change}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{opt{[}k,x{]} = min(opt{[}k-1,x{]} , opt{[}k,x - dk{]} + 1) \newline % Row Count 1 (+ 1)
Base : opt{[}1,x{]} = x, opt{[}k,0{]} = 0% Row Count 2 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{01 knapsack}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{opt{[}k,x{]} = max(vk + opt{[}k-1, x - wk{]}, opt{[}k-1,x{]} \newline % Row Count 1 (+ 1)
base: opt{[}0,x{]} = 0, opt{[}k,0{]} = 0 \newline % Row Count 2 (+ 1)
opt{[}k,x{]} = opt{[}k-1,x{]} if wk \textgreater{} x% Row Count 3 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Djikstra's Algorithm}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{When algorithm proceeds, all vertices are divided into two groups \newline % Row Count 2 (+ 2)
- vertices whose shortest path from the source is known \newline % Row Count 4 (+ 2)
- vertices whose shortest path from the source is NOT discovered yet. \newline % Row Count 6 (+ 2)
Move vertices one at a time from the undiscovered set of vertices to the known set of the shortest distances, based on the shortest distance from the source. \newline % Row Count 10 (+ 4)
Runtime: O(V.log V + E.log V)% Row Count 11 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Heap}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{5.377cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/tskmster07_1696620020_heap_complexity.png}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Karatsuba}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{a × b = (x1·10\textasciicircum{}n/2\textasciicircum{} + x0) · (y1·10\textasciicircum{}n/2\textasciicircum{} + y0)% Row Count 1 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Strassen Algorithm}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{p{5.377cm}}{\vspace{1px}\centerline{\includegraphics[width=5.1cm]{/web/www.cheatography.com/public/uploads/tskmster07_1696623494_Screenshot 2023-10-06 131715.png}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Prim's Algorithm}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{1) Start with an arbitrary vertex as a sub-tree C. \newline % Row Count 2 (+ 2)
2) Expand C by adding a vertex having the minimum weight edge of the graph having exactly one end point in C. \newline % Row Count 5 (+ 3)
3) Update distances from C to adjacent vertices. \newline % Row Count 6 (+ 1)
4) Continue to grow the tree until C gets all vertices. \newline % Row Count 8 (+ 2)
Runtime:  \newline % Row Count 9 (+ 1)
binary heap : O(V.log V + E. log V) \newline % Row Count 10 (+ 1)
Fibonacci heap: O(V. log V + 1) (ac)% Row Count 11 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Greedy Algorithm}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{It is used to solve optimization problems \newline % Row Count 1 (+ 1)
It makes a local optimal choice at each step \newline % Row Count 2 (+ 1)
Earlier decisions are never undone \newline % Row Count 3 (+ 1)
Does not always yield the optimal solution% Row Count 4 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Longest Common Subsequence}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{LCS{[}i,j{]} = (1 + LCS{[}i-1,j-1{]}) if s{[}i{]} = s{[}j{]} \newline % Row Count 1 (+ 1)
LCS{[}i,j{]} = (max(lcs{[}i-1,j{]} , max{[}i,j-1{]}) if s{[}i{]} != s{[}j{]} \newline % Row Count 3 (+ 2)
base case: lcs{[}i,0{]} = lcs{[}0,j{]} = 0% Row Count 4 (+ 1)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


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

\end{document}