\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{lavas}
\pdfinfo{
  /Title (algo.pdf)
  /Creator (Cheatography)
  /Author (lavas)
  /Subject (Algo 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{Algo Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{lavas} via \textcolor{DarkBackground}{\uline{cheatography.com/27670/cs/8074/}}}
\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}lavas \\
  \uline{cheatography.com/lavas} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Published 3rd May, 2016.\\
   Updated 12th May, 2016.\\
   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}{BFS}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Takes a root node and sets the distance to 0 and puts it in a queue(FIFO), while every other node is set to infinity. Iteratively explores the neighbors of the dequeued node and adds them to queue and updates their distance. O(V+E)% Row Count 5 (+ 5)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{p{0.4977 cm} p{0.4977 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{DFS}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{} \tn 
% Row Count 0 (+ 0)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{Initialize each node as unvisited and no time of arrival or departure. From an established root node recursively visit a vertex of the node, noting the time of arrival and finish. Set the node as visited when setting the finishing time. O(V+E) \newline  \newline Decomposing a directed graph into its strongly connected components \newline Determining articulation points, bridges \& biconnected components of an undirected graph}  \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}{DFS Parenthesis Theorem}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{In any DFS of a graph G = (V, E), for any two vertices u and v, exactly one of the followings holds: \newline % Row Count 3 (+ 3)
1. The interval {[}d{[}u{]}, f{[}u{]}{]} and {[}d{[}v{]}, f{[}v{]}{]} are entirely disjoint \newline % Row Count 5 (+ 2)
2. The interval {[}d{[}u{]}, f{[}u{]}{]} is contained entirely within the interval {[}d{[}v{]}, f{[}v{]}{]}, and u is a descendant of v in the depth-first tree \newline % Row Count 8 (+ 3)
3. The interval {[}d{[}v{]}, f{[}v{]}{]} is contained entirely within the interval {[}d{[}u{]}, f{[}u{]}{]}, and v is a descendant of u in the depth-first tree% Row Count 11 (+ 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}{Classification of Edges}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{DFS can be used to classify edges of G: \newline % Row Count 1 (+ 1)
1. Tree edges: edges in the depth-first forest G .  Edge (u, v) is a tree edge if v was first discovered by exploring edge (u, v). \newline % Row Count 4 (+ 3)
2. Back edges: edges (u, v) connecting a vertex u to an ancestor v in a depth-first tree.  Self-loops are considered to be back edges. \newline % Row Count 7 (+ 3)
3. Forward edges: nontree edges (u, v) connecting a vertex u to a descendant v in a depth-first tree.  \newline % Row Count 10 (+ 3)
4. Cross edges: all other edges.  \newline % Row Count 11 (+ 1)
Modify DFS so that each edge (u, v) can be classified by the color of the vertex v that is reachable when the edge is first explored: \newline % Row Count 14 (+ 3)
1.  WHITE indicates a tree edge \newline % Row Count 15 (+ 1)
2.  GRAY indicates a back edge \newline % Row Count 16 (+ 1)
3.  BLACK indicates a forward or cross edges% Row Count 17 (+ 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}{Topological Sort}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{1.  Call DFS(G) to compute finishing time f{[}v{]} for each vertex \newline % Row Count 2 (+ 2)
2.  As each vertex is finished, insert it onto the front of linked list \newline % Row Count 4 (+ 2)
3. Return the linked list of vertices \newline % Row Count 5 (+ 1)
O(V+E)% Row Count 6 (+ 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}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Greedy algorithms are typically used to solve optimization problems \& normally consist of \newline % Row Count 2 (+ 2)
Set of candidates \newline % Row Count 3 (+ 1)
Set of candidates that have already been used \newline % Row Count 4 (+ 1)
Function that checks whether a particular set of candidates provides a solution to the problem \newline % Row Count 6 (+ 2)
Function that checks if a set of candidates is feasible \newline % Row Count 8 (+ 2)
Selection function indicating at any time which is the most promising candidate not yet used \newline % Row Count 10 (+ 2)
Objective function giving the value of a solution; this is the function we are trying to optimize% Row Count 12 (+ 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}{Kruskal's MST Algorithm}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{A \textless{}- 0			// initially A is empty \newline for each vertex v  V{[}G{]}          // line 2-3 takes O(V) time \newline      do Create-Set(v)		// create set for each vertex \newline sort the edges of E by nondecreasing weight w  \newline for edge  E, in order by nondecreasing weight  \newline      do if Find-Set(u) != Find-Set(v) // u\&v on different trees \newline            then  A \textless{}- A U \{(u,v)\} \newline                          Union(u,v) \newline  return A \newline  \newline Create-Set(u):  create a set containing u. \newline Find-Set(u):  Find the set that contains u. \newline Union(u, v):  Merge the sets containing u and v. \newline O(E*log(E))} \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}{Dynamic Programming}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Similar to divide-and-conquer, it breaks problems down into smaller problems that are solved recursively.   \newline % Row Count 3 (+ 3)
In contrast, DP is applicable when the sub-problems are not independent, i.e. when sub-problems share sub-sub-problems.  It solves every sub-sub-problem just once and save the results in a table to avoid duplicated computation.% Row Count 8 (+ 5)
} \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}{Applicability to Optimization Problems}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Optimal sub-structure (principle of optimality):  for the global problem to be solved optimally, each sub-problem should be solved optimally.  This is often violated due to sub-problem overlaps.  Often by being "less optimal" on one problem, we may make a big savings on another sub-problem. \newline % Row Count 6 (+ 6)
Small number of sub-problems:  Many NP-hard problems can be formulated as DP problems, but these formulations are not efficient, because the number of sub-problems is exponentially large.  Ideally, the number of sub-problems should be at most a polynomial number% Row Count 12 (+ 6)
} \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}{LP Overview}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Decision variables - mathematical symbols representing levels of activity of a firm. \newline % Row Count 2 (+ 2)
Objective function - a linear mathematical relationship describing an objective of the firm, in terms of decision variables - this function is to be maximized or minimized. \newline % Row Count 6 (+ 4)
Constraints – requirements or restrictions placed on the firm by the operating environment, stated in linear relationships of the decision variables. \newline % Row Count 10 (+ 4)
Parameters - numerical coefficients and constants used in the objective function and constraints.% Row Count 12 (+ 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}{Selection}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Divide the n elements of input array into n/5 groups of 5 elements each and at most one group made up of the remaining (n mod 5) elements. \newline % Row Count 3 (+ 3)
Find the median of each group by insertion sort \& take its middle element (smaller of 2 if even number input). \newline % Row Count 6 (+ 3)
Use Select recursively to find the median x of the n/5 medians found in step 2. \newline % Row Count 8 (+ 2)
Partition the input array around the median-of-medians x using a modified Partition.  Let k be the number of elements on the low side and n-k on the high side. \newline % Row Count 12 (+ 4)
Use Select recursively to find the ith smallest element on the low side if i  k , or the (i-k)th smallest element on the high side if i \textgreater{} k% Row Count 15 (+ 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}{P}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{P is a complexity class that represents the set of all decision problems that can be solved in polynomial time. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time. \newline % Row Count 5 (+ 5)
Given a graph connected G, can its vertices be coloured using two colours so that no edge is monochromatic? \newline % Row Count 8 (+ 3)
Algorithm: start with an arbitrary vertex, color it red and all of its neighbours blue and continue. Stop when you run out of vertices or you are forced to make an edge have both of its endpoints be the same color.% Row Count 13 (+ 5)
} \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}{NP}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. \newline % Row Count 4 (+ 4)
This means that if someone gives us an instance of the problem and a certificate to the answer being yes, we can check that it is correct in polynomial time.% Row Count 8 (+ 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}{NP Complete}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time. \newline % Row Count 4 (+ 4)
Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X, if there is a polynomial time algorithm f to transform instances y of Y to instances x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes. \newline % Row Count 11 (+ 7)
It can be shown that every NP problem can be reduced to 3-SAT. The proof of this is technical and requires use of the technical definition of NP (based on non-deterministic Turing machines). This is known as Cook's theorem. \newline % Row Count 16 (+ 5)
What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time.% Row Count 20 (+ 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}{NP-Hard}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Intuitively, these are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems. \newline % Row Count 4 (+ 4)
The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time. \newline % Row Count 7 (+ 3)
But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time. \newline % Row Count 14 (+ 7)
The halting problem is an NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one. As another example, any NP-complete problem is NP-hard.% Row Count 20 (+ 6)
} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


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

\end{document}