algorithms.lyx

#LyX 2.1 created this file. For more info see http://www.lyx.org/
\lyxformat 474
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{clrscode3e}
\usepackage{listings}
\lstset{
language=Java,
frame=single,
tabsize=2
}
\end_preamble
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_math auto
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement H
\paperfontsize default
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks true
\pdf_pdfborder true
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\papersize default
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 0
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 1in
\topmargin 1in
\rightmargin 1in
\bottommargin 1in
\secnumdepth 3
\tocdepth 1
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Algorithms and Data Structures
\begin_inset Foot
status collapsed

\begin_layout Plain Layout

\series bold
Disclaimer
\series default
: These notes have been prepared with the 
\series bold
only
\series default
 purpose to help me pass the Computer Science qualifiying exam at the University
 of Illinois at Chicago.
 They are distributed as they are (including errors, typos, omissions, etc.)
 to help other students pass this exam (and possibly relieving them from
 part of the pain associated with such a process).
 I take 
\series bold
no responsibility
\series default
 for the material contained in these notes (which means that you can't sue
 me if you don't pass the qual!) Moreover, this pdf version is distributed
 together with the original LaTeX (and LyX) sources hoping that someone
 else will improve and correct them.
 I mean in absolute no way to violate copyrights and/or take credit stealing
 the work of others.
 The ideas contained in these pages are 
\series bold
not mine
\series default
 but I've just aggregated information scattered all over the internet.
 This work is licensed under a Creative Commons Attribution-NonCommercial-ShareA
like 3.0 Unported License.
\end_layout

\end_inset


\end_layout

\begin_layout Subsection*
Strongly suggested book
\end_layout

\begin_layout Standard
Before you even start reading this notes, do yourself a favor and go buy
 the 
\begin_inset Quotes eld
\end_inset

bible of algorithms
\begin_inset Quotes erd
\end_inset

 a.k.a.
 
\emph on
Introduction to Algorithms, Third Edition
\emph default
 by Cormen, Laiserson, Rivest, Stein.
 (
\begin_inset CommandInset href
LatexCommand href
name "http://mitpress.mit.edu/algorithms/"
target "http://mitpress.mit.edu/algorithms/"

\end_inset

) It is very complete and clear.
 Also, thanks to the authors for the beautiful 
\family typewriter
clrscode3e
\family default
 package that has been used to write the pseudocode of all the algorithms
 in these notes.
\end_layout

\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Standard

\series bold
Important!!! 
\series default
Whenever talking about arrays we assume the index to ALWAYS start at 1 and
 NOT 0.
\end_layout

\begin_layout Section
Analysis of algorithms
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Chapters 2, 3, 4
\end_layout

\end_inset


\end_layout

\begin_layout Itemize

\series bold
Loop invariants
\series default
 are useful to demonstrate the correctness of an algorithm.
 We need to show they hold during the three execution phases of an algorithm:
 
\emph on
Initialization
\emph default
, 
\emph on
Maintenance
\emph default
 and 
\emph on
Termination
\emph default
.
 They work similarly to math induction.
\end_layout

\begin_layout Itemize
Goal is to compute the 
\emph on
running time
\emph default
 of an algorithm (on a particular input!).
 
\end_layout

\begin_layout Itemize
Various types of analysis are possible (which running time are we considering?):
 worst, best, average.
 These depend on which input we are considering.
\end_layout

\begin_deeper
\begin_layout Itemize
Best case is rarely (never) used because it provides no useful information.
 
\end_layout

\begin_layout Itemize
Average case is difficult to guess sometime.
 
\end_layout

\begin_layout Itemize
Worst case gives an upper-bound for EVERY input, it occurs fairly often
 and often matches the average case.
\end_layout

\end_deeper
\begin_layout Itemize
Instead of computing just the running time we are interested in the 
\emph on
order of growth
\emph default
 of the running time.
 (asymptotic analysis) 
\end_layout

\begin_layout Subsection
Asymptotic notation
\end_layout

\begin_layout Standard
Asymptotic notation applies to functions: we describe the running time of
 algorithms as a function of the input size 
\begin_inset Formula $n$
\end_inset

 and we then apply the asymptotic notation to such a function.
 
\end_layout

\begin_layout Paragraph
\begin_inset Formula $\mathbf{\Theta}$
\end_inset

-notation
\end_layout

\begin_layout Standard
For a given function 
\begin_inset Formula $g(n)$
\end_inset

, we denote 
\begin_inset Formula $\Theta(g(n))$
\end_inset

 the set of functions 
\begin_inset Formula 
\begin{eqnarray*}
\Theta(g(n)) & = & \{(f(n):\text{ there exist positive constants c_{1},c_{2} and n_{0} such that}\\
 &  & 0\leq c_{1}g(n)\leq f(n)\leq c_{2}g(n)\text{ for all }n\geq n_{0}\}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
We write 
\begin_inset Formula $f(n)=\Theta(g(n))$
\end_inset

 to indicate 
\begin_inset Formula $f(n)\in\Theta(g(n))$
\end_inset

 and say that 
\begin_inset Formula $g(n)$
\end_inset

 is an 
\emph on
asymptotic tight bound
\emph default
 for 
\begin_inset Formula $f(n)$
\end_inset

.
\end_layout

\begin_layout Paragraph
\begin_inset Formula $\mathbf{O}$
\end_inset

-notation
\end_layout

\begin_layout Standard
For a given function 
\begin_inset Formula $g(n)$
\end_inset

, we denote 
\begin_inset Formula $O(g(n))$
\end_inset

 the set of functions 
\begin_inset Formula 
\begin{eqnarray*}
O(g(n)) & = & \{(f(n):\text{ there exist positive constants \ensuremath{c}and n_{0} such that}\\
 &  & 0\leq f(n)\leq cg(n)\, for\, all\, n\geq n_{0}\}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
We write 
\begin_inset Formula $f(n)=O(g(n))$
\end_inset

 to indicate 
\begin_inset Formula $f(n)\in O(g(n))$
\end_inset

 and say that 
\begin_inset Formula $g(n)$
\end_inset

 is an 
\emph on
asymptotic upper bound
\emph default
 for 
\begin_inset Formula $f(n)$
\end_inset

.
\end_layout

\begin_layout Standard
This notation is important because when we use 
\begin_inset Formula $O$
\end_inset

-notation to describe the worst-case running time of an algorithm we have
 a bound on the running time of the algorithm on 
\emph on
every input
\emph default
.
 When we say 
\begin_inset Quotes eld
\end_inset

the running time of an algorithm is 
\begin_inset Formula $O(g(n))$
\end_inset


\begin_inset Quotes erd
\end_inset

, we mean that there is a function 
\begin_inset Formula $f(n)$
\end_inset

 that is in 
\begin_inset Formula $O(g(n))$
\end_inset

 such that, no matter what particular input size 
\begin_inset Formula $n$
\end_inset

 is chosen, the running time on that particular input is bounded from above
 by the value 
\begin_inset Formula $f(n)$
\end_inset

.
\end_layout

\begin_layout Paragraph
\begin_inset Formula $\mathbf{\Omega}$
\end_inset

-notation
\end_layout

\begin_layout Standard
For a given function 
\begin_inset Formula $g(n)$
\end_inset

, we denote 
\begin_inset Formula $\Omega(g(n))$
\end_inset

 the set of functions 
\begin_inset Formula 
\begin{eqnarray*}
\Omega(g(n)) & = & \{(f(n):\text{ there exist positive constants \ensuremath{c}and n_{0} such that}\\
 &  & 0\leq cg(n)\leq f(n)\, for\, all\, n\geq n_{0}\}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
We write 
\begin_inset Formula $f(n)=\Omega(g(n))$
\end_inset

 to indicate 
\begin_inset Formula $f(n)\in\Omega(g(n))$
\end_inset

 and say that 
\begin_inset Formula $g(n)$
\end_inset

 is an 
\emph on
asymptotic lower bound
\emph default
 for 
\begin_inset Formula $f(n)$
\end_inset

.
\end_layout

\begin_layout Standard
When we say 
\begin_inset Quotes eld
\end_inset

the running time of an algorithm is 
\begin_inset Formula $\Omega(g(n))$
\end_inset


\begin_inset Quotes erd
\end_inset

, we mean that no matter what particular input of size 
\begin_inset Formula $n$
\end_inset

 is chosen for each value of 
\begin_inset Formula $n$
\end_inset

, the running time on that input is at least a constant times 
\begin_inset Formula $g(n)$
\end_inset

, for sufficiently large 
\begin_inset Formula $n$
\end_inset

.
 Equivalently we are giving a lower bound on the best-case running time
 of an algorithm.
\end_layout

\begin_layout Subsubsection
Observations
\end_layout

\begin_layout Itemize
Note that in the definitions of all the previous asymptotic notations we
 assumed that every function is 
\emph on
asymptotically nonnegative
\emph default
 which means that all functions are nonnegative whenever 
\begin_inset Formula $n$
\end_inset

 is sufficiently large.
\end_layout

\begin_layout Itemize
Note that it is important that we have some choices for the constants.
 Therefore if we find just one choice for the constants that is enough to
 apply the proper notation.
 Conversely if we need to show that the notation is not true we need to
 show that there is NO choice for the constants.
\end_layout

\begin_layout Itemize
In polynomials we can generally discard lower order terms when performing
 asymptotic analysis because they are insignificant for large 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Itemize
For any two functions 
\begin_inset Formula $f(n)$
\end_inset

 and 
\begin_inset Formula $g(n)$
\end_inset

, we have 
\begin_inset Formula 
\[
f(n)=\Theta(g(n))\iff f(n)=O(g(n))\, and\, f(n)=\Omega(g(n))
\]

\end_inset


\end_layout

\begin_layout Itemize
Transitivity, reflexivity and symmetry in 
\begin_inset Formula $\Theta$
\end_inset

-notation and transpose symmetry in 
\begin_inset Formula $\Omega$
\end_inset

-notation and 
\begin_inset Formula $O$
\end_inset

-notation, apply to asymptotic comparison.
\end_layout

\begin_layout Paragraph
\begin_inset Formula $\mathbf{o}$
\end_inset

-notation
\end_layout

\begin_layout Standard
For a given function 
\begin_inset Formula $g(n)$
\end_inset

, we denote 
\begin_inset Formula $o(g(n))$
\end_inset

 the set of functions 
\begin_inset Formula 
\begin{eqnarray*}
o(g(n)) & = & \{(f(n)\,:\,\forall c>0,\,\exists n_{0}>0:\\
 &  & 0\leq f(n)<cg(n)\text{ for all }n\geq n_{0}\}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
We write 
\begin_inset Formula $f(n)=o(g(n))$
\end_inset

 to indicate 
\begin_inset Formula $f(n)\in o(g(n))$
\end_inset

 and say that 
\begin_inset Formula $f(n)$
\end_inset

 is 
\emph on
asymptotically smaller 
\emph default
than 
\begin_inset Formula $g(n)$
\end_inset

.
 
\end_layout

\begin_layout Standard
Intuitively the function 
\begin_inset Formula $f(n)$
\end_inset

 becomes insignificant relative to 
\begin_inset Formula $g(n)$
\end_inset

 as 
\begin_inset Formula $n$
\end_inset

 approaches infinity; that is, 
\begin_inset Formula 
\[
\underset{n\rightarrow\infty}{\lim}\frac{f(n)}{g(n)}=0
\]

\end_inset


\end_layout

\begin_layout Paragraph

\series medium
\begin_inset Formula $\mathbf{\omega}$
\end_inset


\series default
-notation
\end_layout

\begin_layout Standard
For a given function 
\begin_inset Formula $g(n)$
\end_inset

, we denote 
\begin_inset Formula $\omega(g(n))$
\end_inset

 the set of functions 
\begin_inset Formula 
\begin{eqnarray*}
\omega(g(n)) & = & \{(f(n)\,:\,\forall c>0,\,\exists n_{0}>0:\\
 &  & 0\leq cg(n)<f(n)\text{ for all }n\geq n_{0}\}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
We write 
\begin_inset Formula $f(n)=\omega(g(n))$
\end_inset

 to indicate 
\begin_inset Formula $f(n)\in\omega(g(n))$
\end_inset

 and say that 
\begin_inset Formula $f(n)$
\end_inset

 is 
\emph on
asymptotically larger 
\emph default
than 
\begin_inset Formula $g(n)$
\end_inset

.
\end_layout

\begin_layout Standard
We can also write 
\begin_inset Formula $f(n)=\omega(g(n))\iff g(n)=o(f(n))$
\end_inset

.
\end_layout

\begin_layout Standard
The relation 
\begin_inset Formula $f(n)=\omega(g(n))$
\end_inset

 implies that
\begin_inset Formula 
\[
\underset{n\rightarrow\infty}{\lim}\frac{f(n)}{g(n)}=\infty
\]

\end_inset


\end_layout

\begin_layout Standard
if the limit exists.
\end_layout

\begin_layout Subsubsection
Amortized analysis
\end_layout

\begin_layout Standard
Amortized analysis considers the entire sequence of operations of the program.
 It is based on the idea that, while certain operations may be extremely
 costly in resources, they cannot occur at a high enough frequency to weigh
 down the entire program because the number of less costly operations will
 far outnumber the costly ones in the long run, "paying back" the program
 over a number of iterations.
\end_layout

\begin_layout Subsection
Common functions (refresher)
\end_layout

\begin_layout Subsubsection
Monotonicity
\end_layout

\begin_layout Standard
A function 
\begin_inset Formula $f(n)$
\end_inset

 is 
\emph on
monotonically increasing
\emph default
 if 
\begin_inset Formula $m\leq n$
\end_inset

 implies 
\begin_inset Formula $f(m)\leq f(n)$
\end_inset

.
 Similarly, it is 
\emph on
monotonically decreasing
\emph default
 if 
\begin_inset Formula $m\leq n$
\end_inset

 implies 
\begin_inset Formula $f(m)\geq f(n)$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Floors and ceilings
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
x-1<\lfloor x\rfloor\leq x\leq\lceil x\rceil<x+1
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\lceil n/2\rceil+\lfloor n/2\rfloor=n
\]

\end_inset


\end_layout

\begin_layout Subsubsection
Exponentials
\end_layout

\begin_layout Itemize
\begin_inset Formula $a^{-1}=\frac{1}{a}$
\end_inset


\end_layout

\begin_layout Itemize
For all 
\begin_inset Formula $n$
\end_inset

 and all 
\begin_inset Formula $a\geq1$
\end_inset

 the function 
\begin_inset Formula $a^{n}$
\end_inset

 is monotonically increasing in 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Itemize
For all real constants 
\begin_inset Formula $a>1$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

, 
\begin_inset Formula $n^{b}=o(a^{n})$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Logarithms
\end_layout

\begin_layout Itemize
Remember that 
\begin_inset Formula $\log_{a}b=c$
\end_inset

 means 
\begin_inset Formula $a^{c}=b$
\end_inset

.
\end_layout

\begin_layout Itemize
When we write 
\begin_inset Formula $\log n$
\end_inset

 we mean 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $\log_{2}n$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Formula $\ln n=\log_{e}n$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $a=b^{\log_{b}a}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $a^{\log_{b}n}=n^{\log_{b}a}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\log_{b}a=\frac{\log_{c}a}{\log_{c}b}$
\end_inset


\end_layout

\begin_layout Itemize
\begin_inset Formula $\log_{b}a=\frac{1}{lob_{a}b}$
\end_inset


\end_layout

\begin_layout Itemize
If the base is strictly greater than one then 
\begin_inset Formula $\log_{b}a$
\end_inset

 is strictly increasing.
\end_layout

\begin_layout Standard
Note how:
\begin_inset Formula 
\[
log_{b}a\,\begin{cases}
>1 & \text{if }a>b\\
=1 & \text{if }a=b\\
<1 & \text{if }a<b
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
We say that a function 
\begin_inset Formula $f(n)$
\end_inset

 is polylogarithmically bounded if 
\begin_inset Formula $f(n)=O(\lg^{k}n)$
\end_inset

 for some constant 
\begin_inset Formula $k$
\end_inset

.
 For any constant 
\begin_inset Formula $a>0$
\end_inset

, 
\begin_inset Formula $\lg^{b}n=o(n^{a})$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Iterated logarithm
\end_layout

\begin_layout Standard
The iterated logarithm is a very slowly growing function that it is defined
 as 
\begin_inset Formula 
\[
\lg^{*}n=\min\{i\geq0:\lg^{(i)}n\leq1\}
\]

\end_inset


\end_layout

\begin_layout Standard
that is the smallest number of times we have to iteratively apply the function
 
\begin_inset Formula $\lg$
\end_inset

 to 
\begin_inset Formula $n$
\end_inset

 in order to obtain a value smaller or equal than 1.
\end_layout

\begin_layout Subsubsection
Factorials
\end_layout

\begin_layout Standard
A weak upperbound on the factorial function is 
\begin_inset Formula $n!\leq n^{n}$
\end_inset

, since each of the n terms in the factorial product is at most 
\begin_inset Formula $n$
\end_inset

,
\end_layout

\begin_layout Standard
Stirling's approximation:
\begin_inset Formula 
\[
n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}\left(1+\Theta\left(\frac{1}{n}\right)\right)
\]

\end_inset


\end_layout

\begin_layout Subsubsection
Ackermann function
\end_layout

\begin_layout Standard
For integers 
\begin_inset Formula $k\geq0$
\end_inset

 and 
\begin_inset Formula $j\geq1$
\end_inset

, we define the function 
\begin_inset Formula $A_{k}(j)$
\end_inset

 as
\begin_inset Formula 
\[
A_{k}(j)=\begin{cases}
j+1 & \text{if }k=0\\
A_{k-1}^{(j+1)}(j) & \text{if }k\geq1
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
where the expression 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $A_{k-1}^{(j+1)}(j)$
\end_inset

 uses the same functional iteration notation of the iterated logarithms.
 Specifically, 
\begin_inset Formula $A_{k-1}^{(0)}(j)=j$
\end_inset

 and 
\begin_inset Formula $A_{k-1}^{(i)}(j)=A_{k}\left(A_{k-1}^{(i-1)}(j)\right)$
\end_inset

 for 
\begin_inset Formula $i\geq1$
\end_inset

.
 We refer to the parameter 
\begin_inset Formula $k$
\end_inset

 as the level of the function 
\begin_inset Formula $A$
\end_inset

.
\end_layout

\begin_layout Standard
Ackermann function value grows rapidly, even for small inputs.
 
\end_layout

\begin_layout Subsubsection
Inverse Ackermann function 
\end_layout

\begin_layout Standard
We define the inverse of the function 
\begin_inset Formula $A_{k}(n)$
\end_inset

, for integer 
\begin_inset Formula $n\geq0$
\end_inset

, by
\begin_inset Formula 
\[
\alpha(n)=\min\{k:A_{k}(1)\geq n\}
\]

\end_inset


\end_layout

\begin_layout Standard
In words, 
\begin_inset Formula $\alpha(n)$
\end_inset

 is the lowest level 
\begin_inset Formula $k$
\end_inset

 for which 
\begin_inset Formula $A_{k}(1)$
\end_inset

 is at least 
\begin_inset Formula $n$
\end_inset

.
 We can see that
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\alpha(n)=\begin{cases}
0 & \text{for }0\leq n\leq2\\
1 & \text{for }n=3\\
2 & \text{for }4\leq n\leq7\\
3 & \text{for }8\leq n\leq2027\\
4 & \text{for }2027\leq n\leq A_{4}(1)
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
which means that 
\begin_inset Formula $\alpha(n)\leq4$
\end_inset

 for all practical purposes.
 (which means it can be treated as a constant)
\end_layout

\begin_layout Subsection
Recursive (Divide-and-Conquer) algorithms analysis
\end_layout

\begin_layout Standard
In Divide-and-Conquer algorithms, we solve a problem recursively, applying
 three steps at each level of the recursion:
\end_layout

\begin_layout Description
Divide the problem into a number of subproblems that are smaller instances
 of the same problem.
\end_layout

\begin_layout Description
Conquer the subproblems by solving them recursively.
 If the subproblem sizes are small enough just solve the subproblems in
 a straightforward way.
\end_layout

\begin_layout Description
Combine the solutions to the subproblems into the solution for the original
 problem.
\end_layout

\begin_layout Subsubsection
Master method (Master Theorem of recursion)
\end_layout

\begin_layout Standard
Provides a 
\begin_inset Quotes eld
\end_inset

canned
\begin_inset Quotes erd
\end_inset

 method for solving recurrences of the form 
\begin_inset Formula $T(n)=aT(n/b)+f(n)$
\end_inset

.
 
\end_layout

\begin_layout Paragraph
Theorem
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $a,b\in\mathbb{N}:a\geq1,b>1$
\end_inset

 be constant and 
\begin_inset Formula $f(n)$
\end_inset

 be a function and let 
\begin_inset Formula $T(n)$
\end_inset

 be defined on the nonnegative integers by the recurrence
\begin_inset Formula 
\[
T(n)=aT(n/b)+f(n)
\]

\end_inset


\end_layout

\begin_layout Standard
where we interpret 
\begin_inset Formula $n/b$
\end_inset

 to mean either 
\begin_inset Formula $\left\lfloor n/b\right\rfloor $
\end_inset

 or 
\begin_inset Formula $\left\lceil n/b\right\rceil $
\end_inset

.
 Then 
\begin_inset Formula $T(n)$
\end_inset

 has the following asymptotic bounds:
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $f(n)=O(n^{\log_{b}a-\epsilon})$
\end_inset

 for some constant 
\begin_inset Formula $\epsilon>0$
\end_inset

, then 
\begin_inset Formula $T(n)=\Theta(n^{\log_{b}a})$
\end_inset

.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $f(n)=\Theta(n^{\log_{b}a})$
\end_inset

 then 
\begin_inset Formula $T(n)=\Theta(n^{\log_{b}a}\log n)$
\end_inset

.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $f(n)=\Omega(n^{\log_{b}a+\epsilon})$
\end_inset

 for some constant 
\begin_inset Formula $\epsilon>0$
\end_inset

 and if 
\begin_inset Formula $af(n/b)\leq cf(n)$
\end_inset

 for some constant 
\begin_inset Formula $c<1$
\end_inset

 and all sufficiently large 
\begin_inset Formula $n$
\end_inset

, then 
\begin_inset Formula $T(n)=\Theta(f(n))$
\end_inset

.
\end_layout

\begin_layout Paragraph
Meaning
\end_layout

\begin_layout Standard
Intuitively, we can see 
\begin_inset Formula $a$
\end_inset

 as the number of subproblems, 
\begin_inset Formula $n/b$
\end_inset

 as the size of each subproblem and 
\begin_inset Formula $f(n)$
\end_inset

 as the time needed to divide and combine the results of the subproblems.
 
\end_layout

\begin_layout Standard
In each of the three cases, we compare the function 
\begin_inset Formula $f(n)$
\end_inset

 to the function 
\begin_inset Formula $n^{\log_{b}a}$
\end_inset

: intuitively, the larger of the two functions determines the solution to
 the recurrence.
\end_layout

\begin_layout Enumerate
In this case 
\begin_inset Formula $n^{\log_{b}a}$
\end_inset

 is the largest, therefore 
\begin_inset Formula $T(n)=\Theta(n^{\log_{b}a})$
\end_inset

.
\end_layout

\begin_layout Enumerate
In this case functions are comparable, therefore 
\begin_inset Formula $T(n)=\Theta(n^{\log_{b}a}\log n)=\Theta(f(n)\log n)$
\end_inset

.
\end_layout

\begin_layout Enumerate
In this case
\begin_inset Formula $f(n)$
\end_inset

 is the largest, therefore 
\begin_inset Formula $T(n)=\Theta(f(n))$
\end_inset

.
\end_layout

\begin_layout Standard
Note that, in order for the master theorem to hold, 
\begin_inset Formula $f(n)$
\end_inset

 needs to be polynomially smaller (bigger) than 
\begin_inset Formula $n^{\log_{b}a}$
\end_inset

.
 That is, 
\begin_inset Formula $f(n)$
\end_inset

 must be asymptotically smaller (bigger) by a factor 
\begin_inset Formula $n^{\epsilon}$
\end_inset

 for some constant 
\begin_inset Formula $\epsilon>0$
\end_inset

.
\end_layout

\begin_layout Paragraph
Simplified version
\end_layout

\begin_layout Standard
Assuming 
\begin_inset Formula $f(n)=cn^{k}$
\end_inset

 and 
\begin_inset Formula $T(1)=c$
\end_inset

 we obtain: 
\begin_inset Formula 
\[
T(n)=aT(n/b)+cn^{k}=\begin{cases}
\Theta(n^{\log_{a}b}) & if\, a>b^{k}\\
\Theta(n^{k}\log n) & if\, a=b^{k}\\
\Theta(n^{k}) & if\, a<b^{k}
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
where 
\begin_inset Formula $k$
\end_inset

 is the 
\begin_inset Quotes eld
\end_inset

order
\begin_inset Quotes erd
\end_inset

 of the combination and we can see 
\begin_inset Formula $n=b^{m}$
\end_inset

 where 
\begin_inset Formula $m$
\end_inset

 are the steps in the recursion.
 We can obtain a very particular case when 
\begin_inset Formula $k=1$
\end_inset

 that is, the time required to combine the results is linear.
\end_layout

\begin_layout Subsubsection
Recursion-tree method
\end_layout

\begin_layout Standard
When the master theorem can't be applied, we apply the recursion-tree method
 to generate a good guess for a solution to a recurrence which can then
 be verified using induction.
 The process can be described with the following steps:
\end_layout

\begin_layout Enumerate
Convert the recurrence into a tree whose nodes represent the costs incurred
 at various levels of the recursion.
 Leaves are the subproblems while the cost for dividing and combining is
 annotated on the side of the tree.
\end_layout

\begin_layout Enumerate
Find a closed formula to describe the problem size based on the level of
 the recursion-tree 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Enumerate
Calculate the height of the tree 
\begin_inset Formula $k$
\end_inset

 using (2) and knowing that, at the deepest level, the problem size is 
\begin_inset Formula $1$
\end_inset

 (or 
\begin_inset Formula $2$
\end_inset

, or whatever else).
\end_layout

\begin_layout Enumerate
Find a closed formula to describe the number of subproblems at each level
 of the tree based on the level of the recursion-tree 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Enumerate
Find a closed formula to describe the cost for dividing and combining at
 each level of the tree based on the level of the recursion-tree 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Enumerate
Find the cost at each level of the tree by multiplying (4) by (5).
\end_layout

\begin_layout Enumerate
Calculate the cost at the deepest level 
\begin_inset Formula $k$
\end_inset

 multiplying (4) by 
\begin_inset Formula $T(1)$
\end_inset

, assuming each problem at the deepest level costs 
\begin_inset Formula $T(1)$
\end_inset

.
\end_layout

\begin_layout Enumerate
Calculate the entire recursion-tree cost by adding up the costs over all
 levels.
\end_layout

\begin_layout Enumerate
Find a closed form for the summation obtained in (8).
\end_layout

\begin_layout Subsubsection
Substitution method
\end_layout

\begin_layout Standard
In the substitution method, we guess a bound (by 
\begin_inset Quotes eld
\end_inset

expanding
\begin_inset Quotes erd
\end_inset

 the recursion) and then use mathematical induction to prove our guess correct.
\end_layout

\begin_layout Section
Linear data structures
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Chapter 10
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Lists
\end_layout

\begin_layout Standard
A 
\emph on
list
\emph default
 is simply a finite and 
\emph on
ordered
\emph default
 sequence of elements.
\end_layout

\begin_layout Standard
\align left
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Access (indexing)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Search
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert / Delete at end
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert / Delete at 
\emph on
i
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n-i)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Operations cost in array based implementation
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Note that whenever we use an array implementation for lists we need to know
 the maximum size of the list a priori, unless we use 
\family typewriter
ArrayList
\family default
 (i.e.
 dynamic arrays) which combine benefits of the operation costs of arrays
 (although amortized) with flexible size of linked lists.
 
\family typewriter
ArrayList
\family default
 implementations typically double in size when full.
\end_layout

\begin_layout Standard
Note that access (indexing) takes constant time because we assume that the
 index of the element we are trying to access is known.
 
\end_layout

\begin_layout Standard
Note that every time we insert/delete a value from a sorted 
\emph on
array
\emph default
 we need to shift all the other elements in order to restore the order;
 which is why insert and delete take 
\begin_inset Formula $O(n)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Access (indexing)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(i)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Search
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert / Delete at end
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert / Delete at 
\emph on
i
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Operations cost in linked list based implementation
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Note that insert operations have running time 
\begin_inset Formula $O(1)$
\end_inset

 because we assume that the pointer to the previous element is known (doubled
 linked list): therefore the only operation that needs to be performed is
 the update of the pointers.
\end_layout

\begin_layout Subsubsection
Linked-lists in Java
\end_layout

\begin_layout Standard
A note on 
\family typewriter
Vector
\family default
: it is very similar to ArrayList, but it's thread safe and its size is
 incremented in chunks.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{lstlisting}
\end_layout

\begin_layout Plain Layout

class Node { 	
\end_layout

\begin_layout Plain Layout

	int val; 	
\end_layout

\begin_layout Plain Layout

	Node next = null; 
\end_layout

\begin_layout Plain Layout

	
\end_layout

\begin_layout Plain Layout

	Node(int v) {
\end_layout

\begin_layout Plain Layout

		val = v;
\end_layout

\begin_layout Plain Layout

	}
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout


\backslash
end{lstlisting}
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Stacks
\end_layout

\begin_layout Standard
Stacks are a restricted variant of a list in which elements can be inserted
 and removed from only one end.
 (Last In First Out - LIFO) Insertion is called 
\emph on
push
\emph default
, deletion is called 
\emph on
pop
\emph default
 and access is called 
\emph on
peek
\emph default
.
 (i.e.
 check which element is on top of the stack)
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Peek
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Push
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pop
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Cost of operations (both array and linked list based implementation)
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Queues 
\end_layout

\begin_layout Standard
Restricted variant of a list in which elements can only be inserted at the
 back and deleted from the front.
 (First In First Out - FIFO) Insertion is called 
\emph on
enqueue
\emph default
, deletion is called 
\emph on
dequeue
\emph default
 and access is called 
\emph on
peek
\emph default
.
 (i.e.
 check which element is on front of the stack)
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Peek
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Enqueue
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Dequeue
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Cost of operations (both array and linked list based implementations)
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Note that to obtain 
\begin_inset Formula $O(1)$
\end_inset

 for all operations in the array implementation we need to use 
\emph on
circular arrays
\emph default
.
\end_layout

\begin_layout Standard
Note that to obtain 
\begin_inset Formula $O(1)$
\end_inset

 for all operations in the linked list implementation we need to maintain
 two pointers, one to the head and one to the tail of the list.
\end_layout

\begin_layout Section
Hash Tables
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Chapter 11
\end_layout

\end_inset


\end_layout

\begin_layout Standard
A hash table generalizes the simpler notion of an ordinary array.
 Directly addressing into an ordinary array makes effective use of our ability
 to examine an arbitrary position in an array in 
\begin_inset Formula $O(1)$
\end_inset

 time.
 Hash tables typically use an array of size proportional to the number of
 keys actually stored.
 Instead of using the key as an array index directly, the array index is
 computed from the key using a 
\emph on
hash function
\emph default
.
 We can deal with collisions using chaining.
 Storage can be reduced to 
\begin_inset Formula $\Theta(n)$
\end_inset

, where is 
\emph on
n
\emph default
 is the cardinality of the keys set of keys 
\emph on
K
\emph default
.
 Searching for an element is 
\begin_inset Formula $O(1)$
\end_inset

 on average (compared to 
\begin_inset Formula $O(1)$
\end_inset

 worst case for direct addressing).
 Worst case time serach for Hash Table is 
\begin_inset Formula $O(n)$
\end_inset

 when all the keys collide and are stored in a single linked list.
\end_layout

\begin_layout Section
Binary trees
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Chapters 6, 12, 13, 21
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Two implementations are possible.
\end_layout

\begin_layout Description
Linked
\begin_inset space ~
\end_inset

list
\begin_inset space ~
\end_inset

based: Each node contains some satellite data, the key and two pointers
 to the left and right subtree respectively.
 There might be also a third pointer to the parent node.
\end_layout

\begin_layout Description
Array
\begin_inset space ~
\end_inset

based: Efficient for complete binary trees because they have only one possible
 shape.
 The root of the tree is 
\begin_inset Formula $A[1]$
\end_inset

 and we need to implement:
\end_layout

\begin_deeper
\begin_layout Standard

\family typewriter
Parent(i) {return 
\begin_inset Formula $\lfloor$
\end_inset

i/2
\begin_inset Formula $\rfloor$
\end_inset

}
\family default
 returns the parent,
\end_layout

\begin_layout Standard

\family typewriter
Left(i) {return 2*i}
\family default
 returns the left subtree, 
\end_layout

\begin_layout Standard

\family typewriter
Right(i) {return 2*i+1}
\family default
 returns the right subtree.
\end_layout

\end_deeper
\begin_layout Subsection
Binary heaps
\end_layout

\begin_layout Standard
A 
\emph on
binary heap
\emph default
 is a complete binary tree whose values are partially ordered according
 to the 
\emph on
heap property
\emph default
.
 There are two kinds of heaps:
\end_layout

\begin_layout Description
max-heap: 
\begin_inset Formula $A[i]\leq Parent(A[i])$
\end_inset

 which means the 
\emph on
largest
\emph default
 element is stored at the root.
 This kind of heap is used in the 
\emph on
heap sort
\emph default
 algorithm.
\end_layout

\begin_layout Description
min-heap: 
\begin_inset Formula $A[i]\leq Parent(A[i])$
\end_inset

 which means the 
\emph on
smallest
\emph default
 element is stored at the root.
 This kind of heap is usually used to implement 
\emph on
priority queue
\emph default
.
\end_layout

\begin_layout Itemize
Binary heaps are efficiently implemented using arrays (since they are complete
 binary trees) 
\end_layout

\begin_layout Itemize
There is NO relation between a node and its siblings (hence the partial
 order).
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Peek root (max/min)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Delete
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Build
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Cost of operations
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Note that since root access can be done in 
\begin_inset Formula $O(1)$
\end_inset

, binary heaps are very efficient every time we need to compute the maximum
 or minimum.
 
\end_layout

\begin_layout Subsubsection
Maintaining the heap property
\end_layout

\begin_layout Standard
We consider a max-heap but the same results are true for the min-heaps.
\end_layout

\begin_layout Standard
Given a max-heap 
\begin_inset Formula $A$
\end_inset

 and an index 
\begin_inset Formula $i$
\end_inset

 the following procedure checks if the max-heap property is maintained for
 
\begin_inset Formula $A[i]$
\end_inset

 and, if not, lets the value 
\begin_inset Formula $A[i]$
\end_inset

 
\emph on
sift-down
\emph default
 in the max-heap so that the subtree rooted at index 
\begin_inset Formula $i$
\end_inset

 obeys the max-heap property.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Max-Heapify}(A,i)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $l$ = 
\backslash
proc{Left($i$)}
\end_layout

\begin_layout Plain Layout


\backslash
li $r$ = 
\backslash
proc{Right($i$)}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $l 
\backslash
leq 
\backslash
attrib{A}{heap-size}$ and $A[l]>A[i]$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then $
\backslash
id{largest} 
\backslash
gets l$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Else $
\backslash
id{largest} 
\backslash
gets i$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $r 
\backslash
leq 
\backslash
attrib{A}{heap-size}$ and $A[r]>A[largest]$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then $
\backslash
id{largest} 
\backslash
gets r$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $ 
\backslash
id{largest} 
\backslash
neq i $
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then exchange $A[i]$ with $
\backslash
attrib{A}{largest}$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
proc{Max-Heapify}(A,largest)$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Running time of this procedure is 
\begin_inset Formula $O(\log n)$
\end_inset

 (if the recursive call doesn't happen it is obviously 
\begin_inset Formula $O(1)$
\end_inset

).
 
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Max-Heapify}$
\end_layout

\end_inset

 is used as a subprocedure in 
\begin_inset Formula $\proc{Build-Max-Heap}$
\end_inset

 which builds a heap from an unordered array in 
\begin_inset Formula $O(n)$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Priority queues
\end_layout

\begin_layout Standard
A 
\emph on
priority queue
\emph default
 is a data structure for maintaining a set 
\begin_inset Formula $S$
\end_inset

 of elements, each with an associated value 
\begin_inset Formula $k$
\end_inset

 called key (which represents also the priority).
 As in queues we remove elements from the head but, whenever we need to
 insert a new element in a priority queue, we can't just enqueue it at the
 tail but we need to insert it in the proper place according to its priority.
\end_layout

\begin_layout Paragraph
Enqueue
\end_layout

\begin_layout Standard
After we insert a new value at the end of the heap we use the following
 procedure to 
\emph on
sift-up
\emph default
 the newly inserted value so that the max-heap property is restored.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Max-Heap-Insert}(A,
\backslash
id{key})$}
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{A}{heap-size} 
\backslash
gets 
\backslash
attrib{A}{heap-size} +1 $
\end_layout

\begin_layout Plain Layout


\backslash
li $A[
\backslash
attrib{A}{heap-size}] 
\backslash
gets 
\backslash
id{key}$
\end_layout

\begin_layout Plain Layout


\backslash
li $ i 
\backslash
gets  
\backslash
attrib{A}{heap-size}$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
While $i>1$ and $A[
\backslash
proc{Parent}(i)]<A[i]$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Do exchange $A[i]$ with $A[
\backslash
proc{Parent}(i)]$
\end_layout

\begin_layout Plain Layout


\backslash
li   $i 
\backslash
gets 
\backslash
proc{Parent}(i)$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Running time of this procedure is 
\begin_inset Formula $O(\log n)$
\end_inset

.
\end_layout

\begin_layout Paragraph
Dequeue
\end_layout

\begin_layout Standard
We return 
\begin_inset Formula $A[1]$
\end_inset

, store 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$A[
\backslash
attrib{A}{heap-size}]$
\end_layout

\end_inset

 in 
\begin_inset Formula $A[1]$
\end_inset

, decrease 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{A}{heap-size}$
\end_layout

\end_inset

 and run 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Max-Heapify}(A,1)$
\end_layout

\end_inset

 to restore the max-heap property.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Peek
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Enqueue
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Dequeue
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Build
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Cost of operations
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Note how cost of enqueue is 
\begin_inset Formula $O(\log n)$
\end_inset

 due to the fact that we need to maintain the heap property after we insert
 a new element in the tree.
\end_layout

\begin_layout Standard
Note how cost of dequeue is 
\begin_inset Formula $O(\log n)$
\end_inset

 due to the fact that, even if it cost only 
\begin_inset Formula $O(1)$
\end_inset

 to access the root of the tree, we need to maintain the heap property since
 we are removing the root itself.
\end_layout

\begin_layout Subsection
BSTs 
\end_layout

\begin_layout Standard
A 
\emph on
binary search tree
\emph default
 (BST) is a particular type of binary tree where the keys are always stored
 in such a way as to satisfy the 
\emph on
binary-search-tree property
\emph default
.
 
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $x$
\end_inset

 be a node in a BST.
 If 
\begin_inset Formula $y$
\end_inset

 is a node in the left subtree of 
\begin_inset Formula $x$
\end_inset

 then 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{y}{key} 
\backslash
leq 
\backslash
attrib{x}{key} $
\end_layout

\end_inset

.
 If 
\begin_inset Formula $y$
\end_inset

 is a node in the right subtree of 
\begin_inset Formula $x$
\end_inset

 then 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{y}{key} 
\backslash
geq 
\backslash
attrib{x}{key} $
\end_layout

\end_inset

.
 
\end_layout

\begin_layout Itemize
Note how this is different from just asking the left child is smaller and
 the right child is bigger than the parent.
 
\end_layout

\begin_layout Itemize
BSTs are usually implemented using linked lists since they don't have any
 shape restriction.
\end_layout

\begin_layout Subsubsection
Searching
\end_layout

\begin_layout Standard
Given a key 
\begin_inset Formula $k$
\end_inset

 and a BST 
\begin_inset Formula $x$
\end_inset

 we want to know if 
\begin_inset Formula $x$
\end_inset

 contains 
\begin_inset Formula $k$
\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Binary-Search}(x,k)$}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $x 
\backslash
isequal 
\backslash
const{nil}$ or $k 
\backslash
isequal 
\backslash
attrib{x}{key}$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then 
\backslash
Return $x$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li If $k< 
\backslash
attrib{x}{key}$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then 
\backslash
Return 
\backslash
proc{Binary-Search($
\backslash
attrib{x}{left},k$)} 
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Else 
\backslash
Return 
\backslash
proc{Binary-Search($
\backslash
attrib{x}{right},k$)} 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "bin-search"

\end_inset


\end_layout

\begin_layout Standard
This is the 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Binary-search}
\end_layout

\end_inset

 algorithm, a very prominent example of Divide-and-Conquer approach, whose
 running time is 
\begin_inset Formula $O(h)$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Inserting
\end_layout

\begin_layout Standard
To insert a new value 
\begin_inset Formula $v$
\end_inset

 into a BST 
\begin_inset Formula $T$
\end_inset

, we use the procedure 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Tree-Insert}
\end_layout

\end_inset

.
 The procedure takes a node 
\begin_inset Formula $z$
\end_inset

 for which 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{z}{key} 
\backslash
gets v$
\end_layout

\end_inset

 and modifies 
\begin_inset Formula $T$
\end_inset

 and some of the attributes of 
\begin_inset Formula $z$
\end_inset

 such that it inserts 
\begin_inset Formula $z$
\end_inset

 into the appropriate position in the tree.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Tree-Insert}(T,z)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $y 
\backslash
gets 
\backslash
const{nil}$
\end_layout

\begin_layout Plain Layout


\backslash
li $x 
\backslash
gets 
\backslash
attrib{T}{root}$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
While $x 
\backslash
neq 
\backslash
const{nil}$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
Comment find right place
\end_layout

\begin_layout Plain Layout

      
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   $y 
\backslash
gets x$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $
\backslash
attrib{z}{key} < 
\backslash
attrib{x}{key}$
\end_layout

\begin_layout Plain Layout

        
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li     $x 
\backslash
gets 
\backslash
attrib{x}{left}$
\end_layout

\begin_layout Plain Layout


\backslash
li     
\backslash
Else 
\end_layout

\begin_layout Plain Layout

        $x 
\backslash
gets 
\backslash
attrib{x}{right}$
\end_layout

\begin_layout Plain Layout

        
\backslash
End
\end_layout

\begin_layout Plain Layout

      
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{z}{p} 
\backslash
gets y$         
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
Comment connect $z$ to the rest of the tree
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $y 
\backslash
isequal 
\backslash
const{nil}$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then $
\backslash
attrib{T}{root} 
\backslash
gets z$      
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
Comment tree is empty
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
ElseIf $
\backslash
attrib{z}{key} < 
\backslash
attrib{y}{key}$ 
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then $
\backslash
attrib{y}{left} 
\backslash
gets z$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Else $
\backslash
attrib{y}{right} 
\backslash
gets z$
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Deleting
\end_layout

\begin_layout Standard
The overall strategy for deleting a node 
\begin_inset Formula $z$
\end_inset

 from a BST 
\begin_inset Formula $T$
\end_inset

 has three basic cases but one of these cases is a bit tricky.
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $z$
\end_inset

 has no children, then we simply remove it by modifying its parent to replace
 
\begin_inset Formula $z$
\end_inset

 with 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
const{nil}
\end_layout

\end_inset

 as its child.
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $z$
\end_inset

 has just one child, then we elevate that child to take 
\begin_inset Formula $z$
\end_inset

's position in the tree by modifying 
\begin_inset Formula $z$
\end_inset

's parent to replace 
\begin_inset Formula $z$
\end_inset

 by 
\begin_inset Formula $z$
\end_inset

's child.
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $z$
\end_inset

 has two children, then we find 
\begin_inset Formula $z$
\end_inset

's successor 
\begin_inset Formula $y$
\end_inset

 which is contained in 
\begin_inset Formula $z$
\end_inset

's right subtree (it is the smallest element greater than 
\begin_inset Formula $z$
\end_inset

) and have 
\begin_inset Formula $y$
\end_inset

 take 
\begin_inset Formula $z$
\end_inset

's position in the tree.
 The rest of 
\begin_inset Formula $z$
\end_inset

's original right subtree becomes 
\begin_inset Formula $y$
\end_inset

's new right subtree, and 
\begin_inset Formula $z$
\end_inset

's left subtree becomes 
\begin_inset Formula $y$
\end_inset

's new left subtree.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Search
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert/Delete
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Max/Min
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Prec./Succ.
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Cost of operations
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Note how all the basic operations on a BST take time proportional to the
 height 
\begin_inset Formula $h$
\end_inset

 of the tree.
\end_layout

\begin_layout Subsubsection
Other operations
\end_layout

\begin_layout Standard
BSTs also support other operations including 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Minimum}, 
\backslash
proc{Maximum}, 
\backslash
proc{Predecessor} and 
\backslash
proc{Successor}
\end_layout

\end_inset

, all of which run in 
\begin_inset Formula $O(h)$
\end_inset

.
\end_layout

\begin_layout Standard
Note how the BST property allows us to print out all the keys in a BST in
 sorted order in 
\begin_inset Formula $O(n)$
\end_inset

 time just performing an inorder visit.
\end_layout

\begin_layout Subsection
Self-balancing BSTs
\end_layout

\begin_layout Standard
Since all basic BST operations execute in 
\begin_inset Formula $O(h)$
\end_inset

 they are efficient if 
\begin_inset Formula $h$
\end_inset

 is small.
 However, if the tree is unbalanced, 
\begin_inset Formula $h$
\end_inset

 can become as large as 
\begin_inset Formula $n$
\end_inset

 (i.e.
 a simple path) causing all BST operations to execute in 
\begin_inset Formula $O(n)$
\end_inset

, which is no faster than using a linked list! Self-balancing BSTs try to
 keep the tree height minimal, by performing transformations (such as rotations)
 at key times on the tree, so that all the basic BST operations take 
\begin_inset Formula $O(\log n)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Search
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert/Delete
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Max/Min
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Prec./Succ.
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Cost of operations
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Rotations
\end_layout

\begin_layout Standard
Binary tree rotations are operations on a binary tree that change the structure
 (i.e.
 the pointers) without interfering with the order of the elements (which
 means
\emph on
 
\emph default
the
\emph on
 
\emph default
binary-search-tree property is maintained).
 A tree rotation moves one node up in the tree and one node down.
 The idea is to decrease the height of the tree by moving smaller subtrees
 down and larger subtrees up.
 There are two kind of rotations, left and right, which are showed in the
 following picture.
\end_layout

\begin_layout Standard
\align center
\begin_inset Graphics
	filename rotation.pdf

\end_inset


\end_layout

\begin_layout Standard
The pseudocode for 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Left-Rotate}
\end_layout

\end_inset

 assumes that 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{x}{right} 
\backslash
neq 
\backslash
attrib{T}{nil}$
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{Left-Rotate}(T,x)}
\end_layout

\begin_layout Plain Layout


\backslash
li $y 
\backslash
gets 
\backslash
attrib{x}{right}$   
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
Comment set $y$ (extract it from $x$)
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{x}{right} 
\backslash
gets 
\backslash
attrib{y}{left}$ 
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
Comment save $y$'s left subtree into $x$'s right subtree
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $
\backslash
attrib{x}{right} 
\backslash
neq 
\backslash
attrib{T}{nil}$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then $
\backslash
attribb{y}{left}{p} 
\backslash
gets x$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{y}{p} 
\backslash
gets 
\backslash
attrib{x}{p}$    
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
Comment link $x$'s parent to $y$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $
\backslash
attrib{x}{p} 
\backslash
isequal 
\backslash
attrib{T}{nil}$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then $
\backslash
attrib{T}{root} 
\backslash
gets y$  
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
ElseIf $x 
\backslash
isequal 
\backslash
attribb{x}{p}{left}$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
> $
\backslash
attribb{x}{p}{left} 
\backslash
gets y$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Else $
\backslash
attribb{x}{p}{right} 
\backslash
gets y$  
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{y}{left} 
\backslash
gets x$    
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
Comment put $x$ on $y$'s left
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{x}{p} 
\backslash
gets y$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Symmetrically the pseudocode for 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Right-Rotate}
\end_layout

\end_inset

 assumes that 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{y}{left} 
\backslash
neq 
\backslash
attrib{T}{nil}$
\end_layout

\end_inset

.
 We can easily obtain it from 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Left-Rotate}
\end_layout

\end_inset

 substituting 
\begin_inset Formula $x$
\end_inset

 with 
\begin_inset Formula $y$
\end_inset

 and 
\begin_inset Formula $right$
\end_inset

 with 
\begin_inset Formula $left$
\end_inset

.
\end_layout

\begin_layout Subsubsection
AVL Trees
\end_layout

\begin_layout Standard
An 
\emph on
AVL-tree
\emph default
 is a binary tree where the heights of the two child subtrees of any node
 differ by at most one; therefore, it is also said to be height-balanced.
\end_layout

\begin_layout Standard
The 
\emph on
balance factor
\emph default
 of a node is the height of its left subtree minus the height of its right
 subtree.
 A node with balance factor 1, 0, or −1 is considered balanced while a node
 with any other balance factor is considered unbalanced and requires rebalancing
 the tree.
\end_layout

\begin_layout Paragraph
Insertion
\end_layout

\begin_layout Standard
The pseudocode for 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{AVL-Insert}
\end_layout

\end_inset

 assumes that every node 
\begin_inset Formula $x$
\end_inset

 in the AVL-tree stores its balance factor 
\begin_inset Formula $bf$
\end_inset

.
 Every leaf and newly inserted node 
\begin_inset Formula $z$
\end_inset

 have 
\begin_inset Formula $bf=0$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{AVL-Insert}(T,z)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
proc{TreeInsert}(T,z)$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $
\backslash
attribb{z}{p}{left} 
\backslash
isequal z$   
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment changes balance factor in $z$'s parent
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
Then $
\backslash
attribb{z}{p}{bf} = 
\backslash
attribb{z}{p}{bf} + 1 $
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Else $
\backslash
attribb{z}{p}{bf} = 
\backslash
attribb{z}{p}{bf} -1 $ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $x 
\backslash
gets 
\backslash
attrib{z}{p}$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
While $x 
\backslash
neq 
\backslash
const{nil}$ and $
\backslash
attrib{x}{bf} 
\backslash
neq 0$ and $|
\backslash
attrib{x}{bf}|<2$  
\end_layout

\begin_layout Plain Layout

    
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment propagates balance factor changes
\end_layout

\begin_layout Plain Layout

    
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $
\backslash
attribb{x}{p}{left} 
\backslash
isequal x$
\end_layout

\begin_layout Plain Layout


\backslash
li     
\backslash
Then $
\backslash
attribb{x}{p}{bf} = 
\backslash
attribb{x}{p}{bf} + 1 $
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Else $
\backslash
attribb{x}{p}{bf} = 
\backslash
attribb{x}{p}{bf} -1 $ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li   $ x 
\backslash
gets 
\backslash
attrib{x}{p}$ 
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $ 
\backslash
attrib{x}{bf} 
\backslash
isequal -2 $   
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment $x$'s right subtree is unbalanced
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then 
\backslash
If $ 
\backslash
attribb{x}{right}{bf} 
\backslash
isequal -1 $
\end_layout

\begin_layout Plain Layout


\backslash
li           
\backslash
Then $
\backslash
proc{Left-Rotate}(x)$
\end_layout

\begin_layout Plain Layout


\backslash
li         
\backslash
Else $
\backslash
proc{Right-Rotate}(
\backslash
attrib{x}{right})$
\end_layout

\begin_layout Plain Layout


\backslash
li         $
\backslash
proc{Left-Rotate}(x)$
\end_layout

\begin_layout Plain Layout

            
\backslash
End
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $ 
\backslash
attrib{x}{bf} 
\backslash
isequal 2 $     
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment $x$'s left subtree is unbalanced
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then 
\backslash
If $ 
\backslash
attribb{x}{left}{bf} 
\backslash
isequal 1 $
\end_layout

\begin_layout Plain Layout


\backslash
li           
\backslash
Then $
\backslash
proc{Right-Rotate}(x)$
\end_layout

\begin_layout Plain Layout


\backslash
li         
\backslash
Else $
\backslash
proc{Left-Rotate}(
\backslash
attrib{x}{left})$
\end_layout

\begin_layout Plain Layout


\backslash
li         $
\backslash
proc{Right-Rotate}(x)$
\end_layout

\begin_layout Plain Layout

            
\backslash
End
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Deletion
\end_layout

\begin_layout Standard
The overall strategy for deleting a node 
\begin_inset Formula $z$
\end_inset

 from an AVL tree 
\begin_inset Formula $T$
\end_inset

 has the same three basic cases we have already seen in BSTs.
 
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $z$
\end_inset

 has no children, then we simply remove it by modifying its parent to replace
 
\begin_inset Formula $z$
\end_inset

 with 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
const{nil}
\end_layout

\end_inset

 as its child.
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $z$
\end_inset

 has just one child, then we elevate that child to take 
\begin_inset Formula $z$
\end_inset

's position in the tree by modifying 
\begin_inset Formula $z$
\end_inset

's parent to replace 
\begin_inset Formula $z$
\end_inset

 by 
\begin_inset Formula $z$
\end_inset

's child.
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $z$
\end_inset

 has two children, then we find 
\begin_inset Formula $z$
\end_inset

's successor 
\begin_inset Formula $y$
\end_inset

 which is contained in 
\begin_inset Formula $z$
\end_inset

's right subtree (it is the smallest element greater than 
\begin_inset Formula $z$
\end_inset

) and have 
\begin_inset Formula $y$
\end_inset

 take 
\begin_inset Formula $z$
\end_inset

's position in the tree.
 The rest of 
\begin_inset Formula $z$
\end_inset

's original right subtree becomes 
\begin_inset Formula $y$
\end_inset

's new right subtree, and 
\begin_inset Formula $z$
\end_inset

's left subtree becomes 
\begin_inset Formula $y$
\end_inset

's new left subtree.
 After deletion, retrace the path back up the tree from 
\begin_inset Formula $y$
\end_inset

's parent to the root, adjusting the balance factors as needed.
 The retracing can stop if the balance factor becomes −1 or +1 indicating
 that the height of that subtree has remained unchanged.
 If the balance factor becomes 0 then the height of the subtree has decreased
 by one and the retracing needs to continue.
 If the balance factor becomes −2 or +2 then the subtree is unbalanced and
 needs to be rotated to fix it.
 If the rotation leaves the subtree's balance factor at 0 then the retracing
 towards the root must continue since the height of this subtree has decreased
 by one.
 This is in contrast to an insertion where a rotation resulting in a balance
 factor of 0 indicated that the subtree's height has remained unchanged.
\end_layout

\begin_layout Subsubsection
Red-Black trees
\end_layout

\begin_layout Standard
A
\emph on
 red-black tree
\emph default
 is a binary tree that satisfies the following red-black properties:
\end_layout

\begin_layout Enumerate
Every node is either red or black.
\end_layout

\begin_layout Enumerate
The root is black.
\end_layout

\begin_layout Enumerate
Every leaf (
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
const{nil}
\end_layout

\end_inset

) is black.
 
\end_layout

\begin_layout Enumerate
If a node is red, then both its children are black.
\end_layout

\begin_layout Enumerate
For each node 
\begin_inset Formula $x$
\end_inset

, all simple paths form 
\begin_inset Formula $x$
\end_inset

 to descendant leaves contain the same number of black nodes.
 We call such a number the
\emph on
 back-height
\emph default
 of 
\begin_inset Formula $x$
\end_inset

, denoted 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
func{bh}(x)$
\end_layout

\end_inset

.
 The black-height of a tree is the black-height of its root.
\end_layout

\begin_layout Standard
Note how the leaves here are simply the sentinel value 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
attrib{T}{nil}
\end_layout

\end_inset

 which is used to treat a 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
const{nil}
\end_layout

\end_inset

 child of a node 
\begin_inset Formula $x$
\end_inset

 as an ordinary node whose parent is 
\begin_inset Formula $x$
\end_inset

.
\end_layout

\begin_layout Standard
A red black tree with 
\begin_inset Formula $n$
\end_inset

 internal nodes has height at most 
\begin_inset Formula $2\log(n+1)$
\end_inset

.
\end_layout

\begin_layout Subsection
Tries (or Radix trees)
\end_layout

\begin_layout Standard
A trie is a variant of an n-ary tree in which characters are stored at each
 node.
 Each path down the tree may represent a word.
 Radix trees are often called “tries,” which comes from the middle letters
 in the word retrieval.
 It is good whenever the alphabed is limited and there is a high degree
 of redundancy in the first portion of the word (sequences share prefixes).
\end_layout

\begin_layout Subsection
Union-Find
\end_layout

\begin_layout Standard
A 
\emph on
disjoint-set data structure
\emph default
 (or 
\emph on
Union-Find data structure
\emph default
) maintains a collection 
\begin_inset Formula $\mathcal{S}=\{S_{1},S_{2},\ldots,S_{k}\}$
\end_inset

 of disjoint dynamic sets and, for each element 
\begin_inset Formula $x\in S_{i},\,1\leq i\leq k$
\end_inset

 supports the following operations:
\end_layout

\begin_layout Itemize
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}(x)$
\end_layout

\end_inset

 which creates a new set whose only member is 
\begin_inset Formula $x$
\end_inset

.
 Since sets are disjoint, we require that 
\begin_inset Formula $x$
\end_inset

 not already be in some other set.
\end_layout

\begin_layout Itemize
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Union}(x,y)$
\end_layout

\end_inset

 which unites the dynamic sets that contain 
\begin_inset Formula $x$
\end_inset

 and 
\begin_inset Formula $y$
\end_inset

, say 
\begin_inset Formula $S_{x}$
\end_inset

 and 
\begin_inset Formula $S_{y}$
\end_inset

, into a new set that is 
\begin_inset Formula $S_{x}\cup S_{y}$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Find-Set}(x)$
\end_layout

\end_inset

 which returns the dynamic set that contains 
\begin_inset Formula $x$
\end_inset

.
\end_layout

\begin_layout Standard
Usually each set is referenced by a representative, that is an element 
\begin_inset Formula $x$
\end_inset

 of such a set and we represent the overall number of elements 
\begin_inset Formula $x$
\end_inset

 in the data structure with 
\begin_inset Formula $n$
\end_inset

.
 Also, we assume that the 
\begin_inset Formula $n$
\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}$
\end_layout

\end_inset

 operations are the first 
\begin_inset Formula $n$
\end_inset

 operations performed when building a new disjoint-set data structure.
\end_layout

\begin_layout Standard
Union-Find data structures are used to represent the connected components
 of an undirected graph and in particular in Kruskal's Algorithm to find
 the Minimum Spanning Tree in an undirected graph.
\end_layout

\begin_layout Subsubsection
Implementation
\end_layout

\begin_layout Standard
Two implementations are possible: 
\end_layout

\begin_layout Description
linked-lists: each set is represented by its own linked list.
 With this implementation, both 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}$
\end_layout

\end_inset

 and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Find-Set}$
\end_layout

\end_inset

 are easy, and require 
\begin_inset Formula $O(1)$
\end_inset

 time.
 To carry out 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}(x)$
\end_layout

\end_inset

, we create a new linked-list whose only object is 
\begin_inset Formula $x$
\end_inset

.
 For 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Find-Set}(x)$
\end_layout

\end_inset

, we just follow the pointer from 
\begin_inset Formula $x$
\end_inset

 back to its set object and return it.
 However 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Union}(x,y)$
\end_layout

\end_inset

 procedure requires an average of 
\begin_inset Formula $\Theta(n)$
\end_inset

 time per call because, after appending 
\begin_inset Formula $y$
\end_inset

 to 
\begin_inset Formula $x$
\end_inset

, we must update the pointers of all elements in 
\begin_inset Formula $y$
\end_inset

's list.
\end_layout

\begin_layout Description
forest: each set is represented by a rooted tree.
 A
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}$
\end_layout

\end_inset

 operation simply creates a tree with just one node.
 We perform a 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Find-Set}$
\end_layout

\end_inset

 operation by simply following parent pointers until we find the root of
 the tree.
 A 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Union}$
\end_layout

\end_inset

 operation causes the root of one tree to point to the root of the other.
 
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="2">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Operation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Cost
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Make-Set
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Union
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\alpha(n))$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Find-Set
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\alpha(n))$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Cost of operations
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset

Note that these values refer to the optimal forest implementation.
\end_layout

\begin_layout Standard
There is a nice theorem that states that a sequence of 
\begin_inset Formula $m$
\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}$
\end_layout

\end_inset

, 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Union}$
\end_layout

\end_inset

, and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Find-Set}$
\end_layout

\end_inset

 operations, 
\begin_inset Formula $n$
\end_inset

 of which are 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}$
\end_layout

\end_inset

 operations, can be performed on a disjoint-set forest in worst-case time
 
\begin_inset Formula $O(m\alpha(n))$
\end_inset

.
 Note that, since each 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Union}$
\end_layout

\end_inset

 operation reduces the number of sets by one, the maximum number of such
 operations is 
\begin_inset Formula $n-1$
\end_inset

.
 Also note that 
\begin_inset Formula $m\geq n$
\end_inset

 and that we assume that the first 
\begin_inset Formula $n$
\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}$
\end_layout

\end_inset

 operations are the first 
\begin_inset Formula $n$
\end_inset

 operations performed.
\end_layout

\begin_layout Section
Sorting, selecting, searching
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Chapters 2, 6, 7, 8, 9
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Insertion sort
\end_layout

\begin_layout Standard
The 
\emph on
insertion sort
\emph default
 algorithm is the most intuitive, yet inefficient, sorting algorithm.
 It orders the sequence by inserting each element in the right place in
 the sorted portion of the sequence.
\end_layout

\begin_layout Subsubsection
Implementation
\end_layout

\begin_layout Standard
The following procedure takes as a parameter an array 
\begin_inset Formula $A[1\twodots n]$
\end_inset

 containing a sequence of numbers of length 
\begin_inset Formula $n$
\end_inset

 and sorts it 
\emph on
in place
\emph default
 by rearranging the numbers within the array itself.
 This means the input array 
\begin_inset Formula $A$
\end_inset

 contains the sorted output sequence when the procedure is finished.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox} 
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Insertion-Sort}(A)$} 
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $j 
\backslash
gets 2$ 
\backslash
To $
\backslash
attrib{A}{length}$ 
\end_layout

\begin_layout Plain Layout

      
\backslash
Do 
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
id{key} 
\backslash
gets A[j]$ 
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Comment Insert $A[j]$ into the sorted sequence $A[1 
\backslash
twodots j-1]$.
 
\end_layout

\begin_layout Plain Layout


\backslash
li   $i 
\backslash
gets j-1$ 
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
While $i > 0$ and $A[i] > 
\backslash
id{key}$ 
\end_layout

\begin_layout Plain Layout

        
\backslash
Do 
\end_layout

\begin_layout Plain Layout


\backslash
li     $A[i+1] 
\backslash
gets A[i]$ 
\end_layout

\begin_layout Plain Layout


\backslash
li     $i 
\backslash
gets i-1$ 
\end_layout

\begin_layout Plain Layout

      
\backslash
End 
\end_layout

\begin_layout Plain Layout


\backslash
li   $A[i+1] 
\backslash
gets 
\backslash
id{key}$ 
\end_layout

\begin_layout Plain Layout

     
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Time complexity
\end_layout

\begin_layout Standard
\begin_inset Formula $O(n^{2})$
\end_inset

: When the array is reverse sorted order, which is the worst case, we need
 to compare each element 
\begin_inset Formula $A[j]$
\end_inset

 with each element in the entire sorted subarray 
\begin_inset Formula $A[1\twodots j-1]$
\end_inset

.
\end_layout

\begin_layout Subsection
Merge sort
\end_layout

\begin_layout Standard
The 
\emph on
merge sort 
\emph default
algorithm closely follows the Divide-and-Conquer paradigm.
 Intuitively, it operates as follows:
\end_layout

\begin_layout Description
Divide: Divide the 
\begin_inset Formula $n$
\end_inset

-element sequence to be sorted into two subsequences of 
\begin_inset Formula $n/2$
\end_inset

 elements each.
\end_layout

\begin_layout Description
Conquer: Sort the two subsequences recursively using merge sort.
\end_layout

\begin_layout Description
Combine: Merge the two sorted subsequences to produce the sorted answer.
\end_layout

\begin_layout Standard
Merge sort does not sort in place but it is possible to devise a modified
 version that does so.
\end_layout

\begin_layout Subsubsection
Implementation
\end_layout

\begin_layout Standard
The following procedure assumes that the subarrays 
\begin_inset Formula $A[p\twodots q]$
\end_inset

 and 
\begin_inset Formula $A[q+1\twodots r]$
\end_inset

 are already sorted and it merges them to form a single sorted subarray
 that replaces the current subarray 
\begin_inset Formula $A[p\twodots r]$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Merge}(A,p,q,r)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $n_1 
\backslash
gets q-p +1$
\end_layout

\begin_layout Plain Layout


\backslash
li $n_2 
\backslash
gets r-q $
\end_layout

\begin_layout Plain Layout


\backslash
li let $L[1
\backslash
twodots n_1+1]$ and $R[1
\backslash
twodots n_2+1]$ be new arrays
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To n_1$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Do $L[i] 
\backslash
gets A[p+i-1]$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $j 
\backslash
gets 1 
\backslash
To n_2$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Do $R[j] 
\backslash
gets A[q+j]$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $L[n_1+1] 
\backslash
gets 
\backslash
infty$
\end_layout

\begin_layout Plain Layout


\backslash
li $R[n_2+1] 
\backslash
gets 
\backslash
infty$
\end_layout

\begin_layout Plain Layout


\backslash
li $i 
\backslash
gets 1$
\end_layout

\begin_layout Plain Layout


\backslash
li $j 
\backslash
gets 1$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $k 
\backslash
gets p 
\backslash
To r$
\end_layout

\begin_layout Plain Layout

      
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $L[i]
\backslash
leq R[j]$
\end_layout

\begin_layout Plain Layout

        
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li     $A[k] 
\backslash
gets L[i]$
\end_layout

\begin_layout Plain Layout


\backslash
li     $i 
\backslash
gets i+1$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Else $A[k] 
\backslash
gets R[j]$
\end_layout

\begin_layout Plain Layout


\backslash
li     $j 
\backslash
gets j+1$
\end_layout

\begin_layout Plain Layout

      
\backslash
End
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
We can use the 
\begin_inset Formula $\proc{Merge}$
\end_inset

 procedure as a subroutine in the merge sort algorithm.
 The following procedure sorts the elements in the subarray 
\begin_inset Formula $A[p\twodots r]$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Merge-Sort}(A,p,r)$}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $p<r$
\end_layout

\begin_layout Plain Layout

      
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li   $q 
\backslash
gets 
\backslash
lfloor (p+r)/2 
\backslash
rfloor$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
proc{Merge-Sort}(A,p,q)$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
proc{Merge-Sort}(A,q+1,r)$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
proc{Merge}(A,p,q,r)$
\end_layout

\begin_layout Plain Layout

      
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
To sort the entire array 
\begin_inset Formula $A$
\end_inset

 we make the initial call 
\begin_inset Formula $\proc{Merge-Sort}(A,1,\attrib{A}{length})$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Time complexity
\end_layout

\begin_layout Standard
\begin_inset Formula $\Theta(n\log n)$
\end_inset

, since the 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Merge}
\end_layout

\end_inset

 procedure, which runs in 
\begin_inset Formula $\Theta(n)$
\end_inset

, is executed 
\begin_inset Formula $\log n$
\end_inset

 times.
\end_layout

\begin_layout Subsection
Heap sort
\end_layout

\begin_layout Standard
The 
\emph on
heap sort
\emph default
 algorithm works by exploiting the max-heap property that the biggest element
 is always at the root.
 It swaps the root of the heap with the last element in the array and then
 reorganizes all the elements but the last one so that the data structure
 satisfies again the max-heap property.
\end_layout

\begin_layout Subsubsection
Implementation
\end_layout

\begin_layout Standard
The following procedure takes as a parameter an array 
\begin_inset Formula $A[1\twodots n]$
\end_inset

 and sorts it 
\emph on
in place
\emph default
.
 The procedure 
\begin_inset Formula $\proc{Build-Max-Heap}(A)$
\end_inset

 is not described in this document.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Heap-Sort}(A)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
proc{Build-Max-Heap}(A)$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 
\backslash
attrib{A}{length} 
\backslash
Downto 2$
\end_layout

\begin_layout Plain Layout

       
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li    exchange $A[1]$ with $A[i]$
\end_layout

\begin_layout Plain Layout


\backslash
li    $
\backslash
attrib{A}{heap-size} 
\backslash
gets 
\backslash
attrib{A}{heap-size} - 1$
\end_layout

\begin_layout Plain Layout


\backslash
li    $
\backslash
proc{Max-Heapify}(A,1)$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Time complexity
\end_layout

\begin_layout Standard
\begin_inset Formula $\Theta(n\log n)$
\end_inset

, since the call to 
\begin_inset Formula $\proc{Build-Max-Heap}$
\end_inset

 takes time 
\begin_inset Formula $O(n)$
\end_inset

 and each of the 
\begin_inset Formula $n-1$
\end_inset

 calls to 
\begin_inset Formula $\proc{Max-Heapify}$
\end_inset

 takes time 
\begin_inset Formula $O(\log n)$
\end_inset

.
\end_layout

\begin_layout Subsection
Quick sort
\end_layout

\begin_layout Standard
The 
\emph on
quick sort
\emph default
 algorithm is another example of application of the Divide-and-Conquer paradigm.
 However, differently from merge sort, it sorts
\emph on
 in place
\emph default
.
 The three steps to sort a subarray 
\begin_inset Formula $A[p\twodots r]$
\end_inset

 are:
\end_layout

\begin_layout Description
Divide: Partition (rearrange) the array
\begin_inset Formula $A[p\twodots r]$
\end_inset

 into (possibly empty) subarrays 
\begin_inset Formula $A[p\twodots q-1]$
\end_inset

 and 
\begin_inset Formula $A[q+1\twodots r]$
\end_inset

 such that each element of 
\begin_inset Formula $A[p\twodots q-1]$
\end_inset

 is less or equal to 
\begin_inset Formula $A[q]$
\end_inset

, which is, in turn, less than or equal to each element of 
\begin_inset Formula $A[q+1\twodots r]$
\end_inset

.
 Compute the index 
\begin_inset Formula $q$
\end_inset

 as part of this partition procedure.
\end_layout

\begin_layout Description
Conquer: Sort the two subarrays 
\begin_inset Formula $A[p\twodots q-1]$
\end_inset

 and 
\begin_inset Formula $A[q+1\twodots r]$
\end_inset

 by recursive calls to quick sort.
\end_layout

\begin_layout Description
Combine: Because the subarrays are already sorted, no work is needed to
 combine them: the entire array 
\begin_inset Formula $A[p\twodots r]$
\end_inset

 is now sorted.
\end_layout

\begin_layout Subsubsection
Implementation
\end_layout

\begin_layout Standard
The following procedure implements quick sort.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Quick-Sort}(A,p,r)$}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $p<r$ 
\backslash
Then 
\end_layout

\begin_layout Plain Layout


\backslash
li   $q 
\backslash
gets 
\backslash
proc{Partition}(A,p,r)$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
proc{Quick-Sort}(A,p,q-1)$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
proc{Quick-Sort}(A,q+1,r)$
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
The key to the algorithm is the 
\begin_inset Formula $\proc{Partition}$
\end_inset

 procedure, which rearranges the subarray 
\begin_inset Formula $A[p\twodots r]$
\end_inset

 in place by partitioning the array in three (possibly empty) regions: elements
 
\begin_inset Formula $\leq x$
\end_inset

, elements 
\begin_inset Formula $>x$
\end_inset

 and 
\begin_inset Formula $x$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Partition}(A,p,r)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $x 
\backslash
gets A[r]$   
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment selects the $pivot$
\end_layout

\begin_layout Plain Layout


\backslash
li $i 
\backslash
gets p-1$  
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $j 
\backslash
gets p 
\backslash
To r-1$    
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment separates the elements $
\backslash
leq x$ from the ones $>x$
\end_layout

\begin_layout Plain Layout

       
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
If $A[j] 
\backslash
leq x$
\end_layout

\begin_layout Plain Layout

          
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li       $i 
\backslash
gets i+1$
\end_layout

\begin_layout Plain Layout


\backslash
li       exchange $A[i]$ with $A[j]$
\end_layout

\begin_layout Plain Layout

       
\backslash
End
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li exchange $A[i+1]$ with $A[r]$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment moves the pivot "in the middle"
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return  $i+1$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
To sort the entire array 
\begin_inset Formula $A$
\end_inset

 we make the initial call 
\begin_inset Formula $\proc{Quick-Sort}(A,1,\attrib{A}{length})$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Time complexity
\end_layout

\begin_layout Standard
The running time of quick sort depends on whether the partition is balanced
 (
\begin_inset Formula $\Theta(n\log n)$
\end_inset

) or unbalanced (
\begin_inset Formula $\Theta(n^{2})$
\end_inset

).
 The average-case running time of quick sort is 
\begin_inset Formula $O(n\log n)$
\end_inset

 which is much closer to the best case than to the worst case.
\end_layout

\begin_layout Standard
It is possible to devise a randomized version of quick sort where the pivot
 is chosen randomly among the elements of the subarray 
\begin_inset Formula $A[p\twodots r]$
\end_inset

 yielding an average running time of 
\begin_inset Formula $O(n\log n)$
\end_inset

.
\end_layout

\begin_layout Subsection
Lower bounds for sorting
\end_layout

\begin_layout Standard
All the previous sorting algorithms belong to the family of the so called
 
\emph on
comparison sorts
\emph default
.
 This family is important because we can prove that any comparison sort
 algorithm requires 
\begin_inset Formula $\Omega(n\log n)$
\end_inset

 comparisons in the worst case.
 
\end_layout

\begin_layout Standard
This means that heap sort and merge sort are 
\emph on
asymptotically optimal
\emph default
 comparison sorts.
\end_layout

\begin_layout Subsection
Counting sort, radix sort and bucket sort
\end_layout

\begin_layout Standard
These sorting algorithms have an average case of 
\begin_inset Formula $O(n)$
\end_inset

.
 They are faster than comparison sort algorithms because they assume something
 about the input.
\end_layout

\begin_layout Standard
Counting sort assumes that each of the 
\begin_inset Formula $n$
\end_inset

 input elements is an 
\emph on
integer
\emph default
 in the range 
\emph on
0
\emph default
 to 
\emph on
k
\emph default
, for some integer 
\emph on
k
\emph default
.
 When 
\begin_inset Formula $k=O(n)$
\end_inset

, the sort runs in 
\begin_inset Formula $\Theta(n)$
\end_inset

 time.
 Counting sort determines, for each input element 
\emph on
x
\emph default
, the number of elements less than 
\emph on
x
\emph default
.
 It uses this information to place element 
\emph on
x
\emph default
 directly into its position in the output array.
 Care must be placed to handle duplicate entries.
 In the code for counting sort, we assume that the input is an array 
\begin_inset Formula $A[1\twodots\, n]$
\end_inset

, and thus 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{A}{length} 
\backslash
gets n$
\end_layout

\end_inset

.
 We require two other arrays: the array 
\begin_inset Formula $B[1\twodots\, n]$
\end_inset

 holds the sorted output, and the array 
\begin_inset Formula $C[0\twodots\, k]$
\end_inset

 provides temporary working storage.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Counting-Sort}(A,B,k)$}
\end_layout

\begin_layout Plain Layout


\backslash
li let $C[0
\backslash
twodots k]$ be a new array
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i=0$ 
\backslash
To $k$
\end_layout

\begin_layout Plain Layout

	
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li $C[i]=0$
\end_layout

\begin_layout Plain Layout

	
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $j=1$ 
\backslash
To 
\backslash
attrib{A}{length} 
\end_layout

\begin_layout Plain Layout

	
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li $C[A[j]]=C[A[j]]+1$	
\end_layout

\begin_layout Plain Layout

	
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Comment $C[i]$ now contains the number of elements equal to $i$.
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i=1$ 
\backslash
To $k$
\end_layout

\begin_layout Plain Layout

	
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li $C[i]=C[i]+C[i-1]$
\end_layout

\begin_layout Plain Layout

	
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Comment $C[i]$ now contains the number of elements less than or equal to
 $i$.
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $j=$
\backslash
attrib{A}{length} 
\backslash
Downto 1
\end_layout

\begin_layout Plain Layout

	
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li $B[C[A[j]]]=A[j]$
\end_layout

\begin_layout Plain Layout


\backslash
li $C[A[j]]=C[A[j]]-1$
\end_layout

\begin_layout Plain Layout

	
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Bucket sort assumes that the input is generated by a random process that
 distributes elements uniformly and independently over the interval 
\begin_inset Formula $[0,1)$
\end_inset

.
 Bucket sort divides the interval 
\begin_inset Formula $[0,1)$
\end_inset

 into 
\emph on
n
\emph default
 equal-sized subintervals, or buckets, and then distributes the 
\emph on
n
\emph default
 input numbers into the buckets.
 Since the inputs are uniformly and independently distributed over 
\begin_inset Formula $[0,1)$
\end_inset

, we do not expect many numbers to fall into each bucket.
 To produce the output, we simply sort the numbers in each bucket and then
 go through the buckets in order, listing the elements in each.
 Code for bucket sort assumes that the input is an 
\emph on
n
\emph default
-element array 
\emph on
A
\emph default
 and that each element 
\begin_inset Formula $A[i]$
\end_inset

 in the array satisfies 
\begin_inset Formula $0\le A[i]<1$
\end_inset

.
 The code requires an auxiliary array 
\begin_inset Formula $B[0\twodots1]$
\end_inset

 of linked lists (buckets) and assumes that there is a mechanism for maintaining
 such lists.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Bucket-Sort}(A)$}
\end_layout

\begin_layout Plain Layout


\backslash
li let $B[0
\backslash
twodots n-1]$ be a new array
\end_layout

\begin_layout Plain Layout


\backslash
li $n=
\backslash
attrib{A}{length}$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i=0$ 
\backslash
To $n-1$
\end_layout

\begin_layout Plain Layout

	
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li make $B[i]$ an empty list
\end_layout

\begin_layout Plain Layout

	
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i=1$ 
\backslash
To $n$
\end_layout

\begin_layout Plain Layout

	
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li inser $A[i]$ into list $B[
\backslash
lfloor nA[i]
\backslash
rfloor ]$	
\end_layout

\begin_layout Plain Layout

	
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i=0$ 
\backslash
To $n-1$
\end_layout

\begin_layout Plain Layout

	
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li sort list $B[i]$ with $
\backslash
proc{Insertion-Sort}$
\end_layout

\begin_layout Plain Layout

	
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li concatenate the lists $B[0],B[1],
\backslash
dots ,B[n-1]$ together in order
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Binary search
\end_layout

\begin_layout Standard
See page 
\begin_inset CommandInset ref
LatexCommand pageref
reference "bin-search"

\end_inset

.
\end_layout

\begin_layout Subsection
Quick select
\end_layout

\begin_layout Standard
A 
\emph on
selection algorithm
\emph default
 is an algorithm for finding the 
\begin_inset Formula $i$
\end_inset

th smallest number in a set of 
\begin_inset Formula $n$
\end_inset

 (distinct) elements.
 Such a number is called the 
\begin_inset Formula $i$
\end_inset

th order statistic of the set.
 This includes the cases of finding the minimum (first order statistics),
 maximum (
\begin_inset Formula $n$
\end_inset

th order statistics), and median (
\begin_inset Formula $\lfloor(n+1)/2\rfloor$
\end_inset

 lower median or 
\begin_inset Formula $\lceil(n+1)/2\rceil$
\end_inset

 upper median) elements.
\end_layout

\begin_layout Standard
We can solve the selection problem in 
\begin_inset Formula $O(n\log n)$
\end_inset

 time, since we can sort the numbers and then simply access the 
\begin_inset Formula $i$
\end_inset

th element in the output array.
 However, there are 
\begin_inset Formula $\Theta(n)$
\end_inset

 time algorithms to determine the minimum and the maximum and the following
 algorithm, to solve the general selection problem, is faster.
\end_layout

\begin_layout Subsubsection
Implementation
\end_layout

\begin_layout Standard
The following procedure implements the quick select algorithm which works
 similarly to quick sort: it takes as input the array 
\begin_inset Formula $A[p\twodots r]$
\end_inset

 and returns its 
\begin_inset Formula $i$
\end_inset

th smallest element.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Randomized-Select}(A,p,r,i)$}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $p 
\backslash
isequal r$ 
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then 
\backslash
Return $A[p]$
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $q 
\backslash
gets 
\backslash
proc{Randomized-Partition}(A,p,r)$
\end_layout

\begin_layout Plain Layout


\backslash
li $k 
\backslash
gets q-p+1 $
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $i 
\backslash
isequal k $     
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment the pivot is the answer
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Then 
\backslash
Return $A[q]$  
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
ElseIf $i<k$  
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Return $
\backslash
proc{Randomized-Select}(A,p,q-1,i)$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment continue search within the smaller elements
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Else 
\backslash
Return $
\backslash
proc{Randomized-Select}(A,q+1,r,i)$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment continue search within the bigger elements
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
The algorithm uses the 
\begin_inset Formula $\proc{Randomized-Partition}$
\end_inset

 procedure, which is the randomized version of the 
\begin_inset Formula $\proc{Partition}$
\end_inset

 procedure used by quick sort.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Randomized-Partition}(A,p,r)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $i 
\backslash
gets 
\backslash
proc{Random}(p,r)$
\end_layout

\begin_layout Plain Layout


\backslash
li exchange $A[r]$ with $A[i]$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return  $
\backslash
proc{Partition}(A,p,r)$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Time complexity
\end_layout

\begin_layout Standard
The expected running time of 
\begin_inset Formula $\proc{Randomized-Select}$
\end_inset

 is 
\begin_inset Formula $\Theta(n)$
\end_inset

.
 This is due to the fact that, as in quick sort, we partition the input
 array recursively but unlike quick sort, which recursively processes both
 sides of the partition, 
\begin_inset Formula $\proc{Randomized-Select}$
\end_inset

 works only on one side of the partition.
 (the one containing the i-th element)
\end_layout

\begin_layout Section
Patterns in algorithms design
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Chapters 15, 16
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Dynamic Programming
\end_layout

\begin_layout Standard
An 
\emph on
optimization problem
\emph default
 needs to have the following two characteristics in order for DP to apply:
 
\end_layout

\begin_layout Itemize
expose 
\emph on
optimal substructure
\emph default
, which means that an optimal solution to a problem contains optimal solutions
 to smaller subproblems (exactly like in Divide-and-Conquer)
\end_layout

\begin_layout Itemize
have 
\emph on
overlapping problems
\emph default
, which means that a subproblem is revisited multiple times.
 If problems are not overlapping it doesn't make sense to store the partial
 results and a Divide-and-Conquer algorithm is probably a better choice.
\end_layout

\begin_layout Standard
DP algorithms work in a bottom-up fashion by finding optimal solutions to
 subproblems (often all of them) and then making a choice among these subproblem
s to select which one will be used in solving the bigger subproblems and
 ultimately the original problem.
\end_layout

\begin_layout Subsubsection
Longest Common Subsequence (LCS)
\end_layout

\begin_layout Standard
Given a sequence 
\begin_inset Formula $X=\langle x_{1},x_{2},\ldots,x_{m}\rangle$
\end_inset

, another sequence 
\begin_inset Formula $Z=\langle z_{1},z_{2},\ldots,z_{k}\rangle$
\end_inset

 is a subsequence of 
\begin_inset Formula $X$
\end_inset

 if there exists a strictlyr increasing sequence 
\begin_inset Formula $\langle i_{1},i_{2},\ldots,i_{k}\rangle$
\end_inset

 of indices of 
\begin_inset Formula $X$
\end_inset

 such that for all 
\begin_inset Formula $j=1,2,\ldots,k$
\end_inset

, we have 
\begin_inset Formula $x_{i_{j}}=z_{j}$
\end_inset

.
 Given two sequences 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

, we say that a sequence 
\begin_inset Formula $Z$
\end_inset

 is a common subsequence of 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

 if 
\begin_inset Formula $Z$
\end_inset

 is a subsequence of both 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

.
\end_layout

\begin_layout Standard
In the longest subsequence problem, we are given two sequences 
\begin_inset Formula $X=\langle x_{1},x_{2},\ldots,x_{m}\rangle$
\end_inset

 and 
\begin_inset Formula $Y=\langle y_{1},y_{2},\ldots,y_{n}\rangle$
\end_inset

 and wish to find a maximum length common subsequence 
\begin_inset Formula $Z=\langle z_{1},z_{2},\ldots,z_{k}\rangle$
\end_inset

 of 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

.
\end_layout

\begin_layout Paragraph
Optimal substructure and overlapping problems
\end_layout

\begin_layout Standard
In order to apply DP we need to show that the problem has optimal substructure.
 This step will also offer a hint on how to use the subproblems solution
 to find the solution to the problem.
 
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $X=\langle x_{1},x_{2},\ldots,x_{m}\rangle$
\end_inset

 and 
\begin_inset Formula $Y=\langle y_{1},y_{2},\ldots,y_{n}\rangle$
\end_inset

 be sequences, and let 
\begin_inset Formula $Z=\langle z_{1},z_{2},\ldots,z_{k}\rangle$
\end_inset

 be any LCS of 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $x_{m}=y_{n}$
\end_inset

, then 
\begin_inset Formula $z_{k}=x_{m}=y_{n}$
\end_inset

 and 
\begin_inset Formula $Z_{k-1}$
\end_inset

 is an LCS of 
\begin_inset Formula $X_{m-1}$
\end_inset

 and 
\begin_inset Formula $Y_{n-1}$
\end_inset

.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $x_{m}\neq y_{n}$
\end_inset

, then 
\begin_inset Formula $z_{k}\neq x_{m}$
\end_inset

 implies that 
\begin_inset Formula $Z$
\end_inset

 is an LCS of 
\begin_inset Formula $X_{m-1}$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $x_{m}\neq y_{n}$
\end_inset

, then 
\begin_inset Formula $z_{k}\neq y_{n}$
\end_inset

 implies that 
\begin_inset Formula $Z$
\end_inset

 is an LCS of 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y_{n-1}$
\end_inset

.
\end_layout

\begin_layout Standard
We can also see how to find an LCS of 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

, we may need to find the LCS of 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y_{n-1}$
\end_inset

 and of 
\begin_inset Formula $X_{m-1}$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

.
 
\end_layout

\begin_layout Paragraph
Implementation
\end_layout

\begin_layout Standard
We can define 
\begin_inset Formula $c[i,j]$
\end_inset

 to be the length of an LCS of the sequences 
\begin_inset Formula $X_{i}$
\end_inset

 and 
\begin_inset Formula $Y_{j}$
\end_inset

.
 The optimal substructure of the LCS problem gives the recursive formula
 
\begin_inset Formula 
\[
c[i,j]=\begin{cases}
0 & \text{if \ensuremath{i=0}or \ensuremath{j=0}}\\
c[i-1,j-1]+1 & \text{if \ensuremath{i,j>0}and \ensuremath{z_{i}=y_{j}}}\\
max(c[i,j-1],c[i-1,j]) & \text{if \ensuremath{i,j>0}and \ensuremath{z_{i}\neq y_{j}}}
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
We can use such a recursion to write an algorithm that takes in input 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

 and stores the values of 
\begin_inset Formula $c[i,j]$
\end_inset

 in a table 
\begin_inset Formula $c[0\twodots m,0\twodots n]$
\end_inset

, and it computes the entries in row-major order.
 The procedure also maintains a table 
\begin_inset Formula $b[1\twodots m,1\twodots n]$
\end_inset

 to help us construct an optimal solution: intuitively, 
\begin_inset Formula $b[i,j]$
\end_inset

 points to the table entry corresponding to the optimal subproblem solution
 chosen when computing 
\begin_inset Formula $c[i,j]$
\end_inset

.
 The procedure returns tables 
\begin_inset Formula $b$
\end_inset

 and 
\begin_inset Formula $c$
\end_inset

 and the LCS for 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $Y$
\end_inset

 is stored in 
\begin_inset Formula $c[m,n]$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{LCS-Length}($X$,$Y$)}
\end_layout

\begin_layout Plain Layout


\backslash
li $m 
\backslash
gets 
\backslash
attrib{X}{length}$
\end_layout

\begin_layout Plain Layout


\backslash
li $n 
\backslash
gets 
\backslash
attrib{Y}{length}$
\end_layout

\begin_layout Plain Layout


\backslash
li let $c[0
\backslash
twodots m,0
\backslash
twodots n]$ and $b[1
\backslash
twodots m,1
\backslash
twodots n]$ be new tables
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To m $ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   $c[i,0] 
\backslash
gets 0$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $j 
\backslash
gets 0 
\backslash
To n $ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   $c[0,j] 
\backslash
gets 0$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To m $ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
For $j 
\backslash
gets 1 
\backslash
To n $ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li      
\backslash
If $x_i 
\backslash
isequal y_j$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li          $c[i,j] 
\backslash
gets c[i-1,j-1] + 1$
\end_layout

\begin_layout Plain Layout


\backslash
li          $b[i,j] 
\backslash
gets "
\backslash
nwarrow"$
\end_layout

\begin_layout Plain Layout


\backslash
li      
\backslash
ElseIf $c[i-1,j] 
\backslash
geq c[i,j-1] $ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li          $c[i,j] 
\backslash
gets c[i-1,j] $
\end_layout

\begin_layout Plain Layout


\backslash
li          $b[i,j] 
\backslash
gets "
\backslash
uparrow"$
\end_layout

\begin_layout Plain Layout


\backslash
li      
\backslash
Else $c[i,j] 
\backslash
gets c[i,j-1] + 1$
\end_layout

\begin_layout Plain Layout


\backslash
li          $b[i,j] 
\backslash
gets "
\backslash
leftarrow"$
\end_layout

\begin_layout Plain Layout

         
\backslash
End 
\backslash
End 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $c$ and $b$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
We can then print the LCS using table 
\begin_inset Formula $b$
\end_inset

 and the following procedure.
 The initial call is 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Print-LCS}($b$,$X$,
\backslash
attrib{X}{length},
\backslash
attrib{Y}{length})
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{Print-LCS}($b$,$X$,$i$,$j$)}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $i 
\backslash
isequal 0$ or $j 
\backslash
isequal 0$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
Return 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
If $b[i,j] 
\backslash
isequal "
\backslash
nwarrow"$ 
\backslash
Then 
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
proc{Print-LCS}($b$,$X$,$i-1$,$j-1$)
\end_layout

\begin_layout Plain Layout


\backslash
li    print $x_i$ 
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
ElseIf $b[i,j] 
\backslash
isequal "
\backslash
uparrow"$ 
\backslash
Then 
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
proc{Print-LCS}($b$,$X$,$i-1$,$j$)
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Else 
\backslash
proc{Print-LCS}($b$,$X$,$i$,$j-1$)
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Other problems that are solvable with DP algorithms
\end_layout

\begin_layout Paragraph
Rod cutting problem 
\end_layout

\begin_layout Standard
Given a rod of length 
\begin_inset Formula $n$
\end_inset

 and a table of prices 
\begin_inset Formula $p_{i}$
\end_inset

 for 
\begin_inset Formula $i=1,2\ldots,n$
\end_inset

, determine the maximum revenue 
\begin_inset Formula $r_{n}$
\end_inset

 obtainable by cutting up the rod and selling the pieces.
 Note that if the price 
\begin_inset Formula $p_{n}$
\end_inset

 for a rod of length 
\begin_inset Formula $n$
\end_inset

 is large enough, an optimal solution may require no cutting at all.
\end_layout

\begin_layout Standard
The following dynamic programming algorithm takes as input an array 
\begin_inset Formula $p[1\twodots n]$
\end_inset

 of prices and an integer 
\begin_inset Formula $n$
\end_inset

 and returns an array 
\begin_inset Formula $r[0\twodots n]$
\end_inset

 in which it saves the results of the subproblems and an array 
\begin_inset Formula $s[0\twodots n]$
\end_inset

 containing the optimal size of the first piece to cut off when solving
 a subproblem of size 
\begin_inset Formula $j$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{Cut-Rod}($p,n$)}
\end_layout

\begin_layout Plain Layout


\backslash
li let $r[0
\backslash
twodots n]$ and $s[0
\backslash
twodots n]$ be new arrays
\end_layout

\begin_layout Plain Layout


\backslash
li $r[0] 
\backslash
gets 0$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $j 
\backslash
gets 1 
\backslash
To n$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   $q 
\backslash
gets -
\backslash
infty$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
For $i 
\backslash
gets 1 
\backslash
To j$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li     
\backslash
If $q<p[i]+r[j-i]$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li        $q 
\backslash
gets p[i]+r[j-i]$
\end_layout

\begin_layout Plain Layout


\backslash
li        $s[j] 
\backslash
gets i$ 
\backslash
End  
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li   $r[j] 
\backslash
gets q$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $r$ and $s$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
0-1 knapsack problem
\end_layout

\begin_layout Standard
We are given 
\begin_inset Formula $n$
\end_inset

 items.
 Each item 
\begin_inset Formula $i$
\end_inset

 has a value of 
\begin_inset Formula $v_{i}$
\end_inset

 dollars and a weight 
\begin_inset Formula $w_{i}$
\end_inset

 pounds which are nonnegative integers.
 Given a bag whose capacity is 
\begin_inset Formula $W$
\end_inset

 what is the maximum value that we can carry knowing that we can either
 carry an item (therefore 
\begin_inset Formula $1\cdot w_{i}$
\end_inset

) or leave it behind (therefore 
\begin_inset Formula $0\cdot w_{i}$
\end_inset

) but not carry a portion of it?
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $i$
\end_inset

 is the highest-numbered item in an optimal solution 
\begin_inset Formula $S$
\end_inset

 for 
\begin_inset Formula $W$
\end_inset

 pounds and items 
\begin_inset Formula $1\twodots n$
\end_inset

.
 Then 
\begin_inset Formula $S′=S−\{i\}$
\end_inset

 must be an optimal solution for 
\begin_inset Formula $W-w_{i}$
\end_inset

 pounds and items 
\begin_inset Formula $1\twodots i$
\end_inset

-1 pounds, and the value of the solution 
\begin_inset Formula $S$
\end_inset

 is 
\begin_inset Formula $v_{i}$
\end_inset

 plus the value of the subproblem solution 
\begin_inset Formula $S′$
\end_inset

.
 Assuming 
\begin_inset Formula $c[i,w]$
\end_inset

 to be the value of the solution for items 
\begin_inset Formula $1\twodots1$
\end_inset

 and maximum weight 
\begin_inset Formula $w$
\end_inset

 we can formalize the previous statement as
\begin_inset Formula 
\[
c[i,w]=\begin{cases}
0 & \text{if }i=0\text{ or }w=0\\
c[i-1,w] & \text{if }w_{i}>w\\
\max(v_{i}+c[i-1,w-w_{i}],c[i-1,w]) & \text{if }i>1\text{ and }w\geq w_{i}
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
The following dynamic programming algorithm takes as input the arrays of
 values 
\begin_inset Formula $v[1\twodots n]$
\end_inset

 and weights 
\begin_inset Formula $w[1\twodots n]$
\end_inset

, the capacity 
\begin_inset Formula $W$
\end_inset

 and returns a table 
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $c[0\twodots n,0\twodots W]$
\end_inset


\family default
\series default
\shape default
\size default
\emph default
\bar default
\noun default
\color inherit
 which contains the values of the solutions for all subproblems.
 At the end of the computation 
\begin_inset Formula $c[n,W]$
\end_inset

 contains the maximum value we can carry.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{0-1-Knapsack}($v,w,W$)}
\end_layout

\begin_layout Plain Layout


\backslash
li $n 
\backslash
gets 
\backslash
attrib{v}{length}$
\end_layout

\begin_layout Plain Layout


\backslash
li let $c[0
\backslash
twodots n,0
\backslash
twodots W]$ be a new table
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $w 
\backslash
gets 0 
\backslash
To W$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   $c[0,w] 
\backslash
gets 0$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To n$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   $c[i,0] 
\backslash
gets 0$ 
\backslash
End
\end_layout

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To n$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
For $w 
\backslash
gets 1 
\backslash
To W$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li       
\backslash
If $w[i] 
\backslash
leq w $ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li          
\backslash
If $v[i] + c[i-1,w-w[i]]> c[i-1,w]$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li               $c[i,w] 
\backslash
gets v[i] + c[i-1,w-w[i]]$
\end_layout

\begin_layout Plain Layout


\backslash
li          
\backslash
Else $c[i,w] 
\backslash
gets c[i-1,w]$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li       
\backslash
Else $c[i,w] 
\backslash
gets c[i-1,w] $ 
\backslash
End 
\backslash
End 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $c$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
To find out which items are included in the solution we need to start at
 c
\begin_inset Formula $[n,W]$
\end_inset

 and tracing where the optimal values came from.
 If 
\begin_inset Formula $c[i,w]=c[i−1,w]$
\end_inset

, then item 
\begin_inset Formula $i$
\end_inset

 is not part of the solution, and we continue tracing with 
\begin_inset Formula $c[i−1,w]$
\end_inset

.
 Otherwise item 
\begin_inset Formula $i$
\end_inset

 is part of the solution, and we continue tracing with 
\begin_inset Formula $c[i−1,w−w[i]]$
\end_inset

.
\end_layout

\begin_layout Subsection
Greedy Algorithms
\end_layout

\begin_layout Standard
A greedy algorithm obtains an optimal solution to a problem by making a
 sequence of choices that looks best at the moment (i.e.
 a local optimal choice) hoping that it will lead to a globally optimal
 solution.
 
\end_layout

\begin_layout Standard
An optimization problem needs to have the following two characteristics
 in order to be efficiently solvable with a greedy algorithm: 
\end_layout

\begin_layout Itemize
expose 
\emph on
optimal substructure
\emph default
, exactly as DP
\end_layout

\begin_layout Itemize
have a 
\emph on
greedy-choice property
\emph default
, which means that we can assemble a globally optimal solution by making
 a locally optimal (greedy) choices.
 
\end_layout

\begin_layout Standard
In DP algorithms we make a choice at each step, but the choice usually depends
 on the solutions to subproblems.
 In greedy algorithms, we make whatever choice seems best at the moment
 and then solve the subproblem that remains.
 
\end_layout

\begin_layout Standard
A DP algorithm proceeds bottom-up, whereas a greedy strategy usually progresses
 in a top-down fashion, making one greedy choice after another, reducing
 each given problem instance to a smaller one.
\end_layout

\begin_layout Subsubsection
Proving correctness and optimality 
\end_layout

\begin_layout Standard
How can we prove that the solution found by a greedy algorithm is optimal
 if we don't even know what the optimal solution is? Of course if we can
 prove that an optimal solution exists and is the same one found by the
 greedy algorithm then we are done.
 There are cases where this is not possible and therefore we need to use
 techniques that only use a property of the optimal solution which can in
 turn be used to prove the correctness and optimality of a greedy algorithm.
\end_layout

\begin_layout Itemize
Greedy algorithm stays ahead.
 Show that after each step of the algorithm, the solution it finds is at
 least as good as any other algorithm's solution.
 
\end_layout

\begin_layout Itemize
Exchange argument.
 Gradually transform any solution to the one found by the greedy algorithm
 without hurting its quality.
\end_layout

\begin_layout Itemize
Structural.
 Discover a simple "structural" bound asserting that every possible solution
 must have a certain value.
 Then show that your algorithm always achieves this bound.
\end_layout

\begin_layout Subsubsection
Huffman codes
\end_layout

\begin_layout Standard
Huffman's greedy algorithm builds a variable length binary character code,
 in which each character is represented by a unique binary string, which
 we call codeword.
 The goal is to give more frequent character short codewords and infrequent
 characters long codewords to achieve data compression.
\end_layout

\begin_layout Standard
In the pseudocode that follows , we assume 
\begin_inset Formula $C$
\end_inset

 is a set of 
\begin_inset Formula $n$
\end_inset

 characters and that each character 
\begin_inset Formula $c\in C$
\end_inset

 is an object with an attribute 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
attrib{c}{freq}
\end_layout

\end_inset

 giving its frequency.
 The algorithm builds a tree 
\begin_inset Formula $T$
\end_inset

 corresponding to the optimal code in a bottom-up fashion and uses a min-priorit
y queue 
\begin_inset Formula $Q$
\end_inset

, keyed on the 
\begin_inset Formula $freq$
\end_inset

 attribute, to identify the two least-frequent objects to merge together.
 
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Huffman}(C)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $n 
\backslash
gets |C|$
\end_layout

\begin_layout Plain Layout


\backslash
li $Q 
\backslash
gets C$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To n-1$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   allocate a new node $z$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{z}{left} 
\backslash
gets x 
\backslash
gets 
\backslash
proc{Extract-Min}(Q)$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{z}{right} 
\backslash
gets y 
\backslash
gets 
\backslash
proc{Extract-Min}(Q)$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{z}{freq} 
\backslash
gets 
\backslash
attrib{x}{freq} + 
\backslash
attrib{y}{freq}$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
proc{Insert}(Q,z)$
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return 
\backslash
proc{Extract-Min}(Q) 
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment returns the root of the tree
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Running time of this algorithm is 
\begin_inset Formula $O(n\log n)$
\end_inset

 since priority queue operations run in 
\begin_inset Formula $\log n$
\end_inset

 time and the main loop executes 
\begin_inset Formula $n-1$
\end_inset

 times.
\end_layout

\begin_layout Subsubsection
Other problems that are solvable with greedy algorithms
\end_layout

\begin_layout Paragraph
Activity selection problem 
\end_layout

\begin_layout Standard
In this problem we are given a set of activities 
\begin_inset Formula $A=\{a_{1},\ldots,a_{n}\}$
\end_inset

 and their start and finish times 
\begin_inset Formula $s_{i}$
\end_inset

 and 
\begin_inset Formula $f_{i}$
\end_inset

 and we need to find the maximum subset of mutually compatible activities.
 Two activities 
\begin_inset Formula $i$
\end_inset

 and 
\begin_inset Formula $j$
\end_inset

 are compatible if they don't overlap.
 
\end_layout

\begin_layout Standard
To solve this problem we consider activities in increasing order of finish
 time and we schedule them provided they are compatible with the ones already
 taken.
 Here 
\begin_inset Formula $S$
\end_inset

 is the set of selected activities.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{Activity-selection}($A$)}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
proc{Sort}($A$)  
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment in increasing order of finish time $f_i$
\end_layout

\begin_layout Plain Layout


\backslash
li $S 
\backslash
gets 
\backslash
emptyset$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To n$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $a_i$ is compatible with $S$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li     $S 
\backslash
gets S 
\backslash
cup a_i$ 
\backslash
End 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $S$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Activity partitioning problem
\end_layout

\begin_layout Standard
In this problem we are given a set of activities 
\begin_inset Formula $A=\{a_{1},\ldots,a_{n}\}$
\end_inset

 and their start and finish times 
\begin_inset Formula $s_{i}$
\end_inset

 and 
\begin_inset Formula $f_{i}$
\end_inset

 and we need to find the minimum number of 
\begin_inset Quotes eld
\end_inset

slots
\begin_inset Quotes erd
\end_inset

 necessary to schedule all activities.
 Clearly two activities can't overlap in the same slot.
 
\end_layout

\begin_layout Standard
To solve this problem we consider activities in increasing order of start
 time.
 Here 
\begin_inset Formula $s$
\end_inset

 is the number of a slots.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{Activity-partitioning}($A$)}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
proc{Sort}($A$)  
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment in increasing order of start time $s_i$
\end_layout

\begin_layout Plain Layout


\backslash
li $s 
\backslash
gets 0$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To n$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $a_i$ is compatible with some slot $k$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li     schedule $a_i$ in slot $k$ 
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
Else allocate a new slot $s+1$
\end_layout

\begin_layout Plain Layout


\backslash
li   schedule $a_i$ in slot $s+1$
\end_layout

\begin_layout Plain Layout


\backslash
li   $s 
\backslash
gets s + 1$ 
\backslash
End 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $s$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Lateness minimization problem 
\end_layout

\begin_layout Standard
In this problem we are given a set of activities 
\begin_inset Formula $A=\{a_{1},\ldots,a_{n}\}$
\end_inset

, their start and finish times 
\begin_inset Formula $s_{i}$
\end_inset

 and 
\begin_inset Formula $f_{i}$
\end_inset

 and their due time (deadline) 
\begin_inset Formula $d_{i}$
\end_inset

.
 We can also define, for each job 
\begin_inset Formula $i$
\end_inset

, lateness as 
\begin_inset Formula $l_{i}=\max(0,f_{i}-d_{i})$
\end_inset

 and the amount of time required to complete as 
\begin_inset Formula $t_{i}=f_{i}-s_{i}$
\end_inset

.
 
\begin_inset Formula $ $
\end_inset


\end_layout

\begin_layout Standard
Our goal is to schedule all activities minimizing maximum lateness 
\begin_inset Formula $L=\underset{i\in\{[1\twodots n]\}}{\max l_{i}}$
\end_inset


\end_layout

\begin_layout Standard
To solve this problem we consider activities in increasing order of deadline
 (earlies deadline activities come first).
 At the end of the algorithm 
\begin_inset Formula $A$
\end_inset

 contains the scheduled activities.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{Lateness-Minimization}($A$)}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
proc{Sort}($A$)  
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment in increasing order of deadline $d_i$
\end_layout

\begin_layout Plain Layout


\backslash
li $t 
\backslash
gets 0$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To n$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   schedule $a_i$ in interval $[t,t+t_i]$ 
\end_layout

\begin_layout Plain Layout


\backslash
li   $s_i 
\backslash
gets t$
\end_layout

\begin_layout Plain Layout


\backslash
li   $f_i 
\backslash
gets t+t_i$
\end_layout

\begin_layout Plain Layout


\backslash
li   $t 
\backslash
gets t + t_i$  
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Optimal off-line caching problem
\end_layout

\begin_layout Standard
In this problem we are given a cache with capacity 
\begin_inset Formula $k$
\end_inset

 and a sequence of requests 
\begin_inset Formula $d_{1},d_{2},\ldots,d_{m}$
\end_inset

.
 We want to find an eviction schedule (i.e.
 decide which element in the cache we want to overwrite) that minimizes
 the number of cache misses.
\end_layout

\begin_layout Standard
The optimal solution is to evict the item that is not requested until 
\emph on
farthest in the future
\emph default
.
 
\end_layout

\begin_layout Paragraph
Coin changing problem
\end_layout

\begin_layout Standard
In this problem we are given the currency denominations 
\begin_inset Formula $D=\{1,5,10,25,100\}$
\end_inset

 (US coinage) and and a certain amount 
\begin_inset Formula $x$
\end_inset

.
 We need to devise a method to pay the amount 
\begin_inset Formula $x$
\end_inset

 using the fewest number of coins.
\end_layout

\begin_layout Standard
The problem can be solved using the so called cashier's algorithm, which
 at each iteration adds the coin of largest value that does not take us
 past the amount to be paid.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{
\backslash
proc{Coin-Change}($D$)}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
proc{Sort}($D$)  
\backslash
>
\backslash
>
\backslash
>  
\backslash
Comment in increasing order
\end_layout

\begin_layout Plain Layout


\backslash
li $S 
\backslash
gets 
\backslash
emptyset$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
While $x 
\backslash
neq 0$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   let $k$ be the largest integer such that $c_k < x$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $k 
\backslash
isequal 0$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li      
\backslash
Return 
\backslash
Error 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li   $x 
\backslash
gets x - c_k$
\end_layout

\begin_layout Plain Layout


\backslash
li   $S 
\backslash
gets S 
\backslash
cup 
\backslash
{ k 
\backslash
}$  
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $S$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Note that the previous algorithm is optimal for US coinage.
 If we use different denomiations we might need a different algorithm that
 uses Dynamic Programming.
\end_layout

\begin_layout Paragraph
Fractional knapsack problem 
\end_layout

\begin_layout Standard
In this problem we are given a set of items 
\begin_inset Formula $A=\{a_{1},\ldots,a_{n}\}$
\end_inset

, each with a weight 
\begin_inset Formula $w_{i}$
\end_inset

 and a value 
\begin_inset Formula $v_{i}$
\end_inset

 and a container of capacity 
\begin_inset Formula $x$
\end_inset

.
 We need to find the set of items (or fraction of items) so that the total
 weight is less than 
\begin_inset Formula $x$
\end_inset

 and the total value is as large as possible.
\end_layout

\begin_layout Standard
The problem can be solved by sorting the items in decreasing order of revenue
 
\begin_inset Formula $r_{i}=\frac{v_{i}}{w_{i}}$
\end_inset

 and then filling the container up to 
\begin_inset Formula $x$
\end_inset

 by taking a fraction of the last item if such an item doesn't fit entirely.
\end_layout

\begin_layout Section
Graphs
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Chapters 22, 23, 24, 25
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Data structures
\end_layout

\begin_layout Subsubsection
Adjacency-list
\end_layout

\begin_layout Standard
The 
\emph on
adjacency-list
\emph default
 
\emph on
representation
\emph default
 of a graph 
\begin_inset Formula $G=(V,E)$
\end_inset

 consists of an array 
\begin_inset Formula $Adj$
\end_inset

 of 
\begin_inset Formula $n$
\end_inset

 linked lists, one for each vertex 
\begin_inset Formula $u\in V$
\end_inset

, such that 
\begin_inset Formula $Adj[u]$
\end_inset

 contains all the vertices adjacent to 
\begin_inset Formula $u$
\end_inset

 in 
\begin_inset Formula $G$
\end_inset

.
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $G$
\end_inset

 is directed then the sum of the lengths of all the adjacency lists is 
\begin_inset Formula $m$
\end_inset

.
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $G$
\end_inset

 is undirected then the sum of the lengths of all the adjacency lists is
 
\begin_inset Formula $2m$
\end_inset

.
\end_layout

\begin_layout Itemize
The amount of memory required to store the adjacency-list representation
 of 
\begin_inset Formula $G$
\end_inset

 is 
\begin_inset Formula $\Theta(n+m)$
\end_inset

: this is the major advantage of this representation.
\end_layout

\begin_layout Itemize
The amount of time needed to scan the entire data structure is 
\begin_inset Formula $\Theta(n+m)$
\end_inset

: this is an advantage of this representation.
\end_layout

\begin_layout Itemize
The amount of time to search for 
\begin_inset Formula $v$
\end_inset

 in the adjacency-list 
\begin_inset Formula $Adj[u]$
\end_inset

 is 
\begin_inset Formula $O(\deg(u))$
\end_inset

 because in the worst case we need to scan 
\begin_inset Formula $G.Adj[u]$
\end_inset

 entirely.
 
\end_layout

\begin_layout Itemize
The amount of time to check if a given edge 
\begin_inset Formula $(u,v)$
\end_inset

 is present in the graph is 
\begin_inset Formula $O(\deg(u))$
\end_inset

 that is the same time needed to search for 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $Adj[u]$
\end_inset

: this is the major drawback of this representation.
\end_layout

\begin_layout Itemize
Generally speaking this representation is better for sparse and/or big graphs.
\end_layout

\begin_layout Subsubsection
Adjacency-matrix
\end_layout

\begin_layout Standard
The 
\emph on
adjacency-matrix
\emph default
 
\emph on
representation
\emph default
 of a graph 
\begin_inset Formula $G=(V,E)$
\end_inset

 consists of a matrix 
\begin_inset Formula $A=(a_{ij})$
\end_inset

 such that 
\begin_inset Formula 
\[
a_{ij}=\begin{cases}
1 & \text{if }(i,j)\in E\\
0 & \text{otherwise}
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $G$
\end_inset

 is undirected then 
\begin_inset Formula $A=A^{T}$
\end_inset

, that is 
\begin_inset Formula $A$
\end_inset

 is symmetrical.
\end_layout

\begin_layout Itemize
The amount of memory required to store the adjacency-matrix representation
 is 
\begin_inset Formula $\Theta(n^{2})$
\end_inset

, independently from the number of edges: this is the major drawback of
 this representation
\end_layout

\begin_layout Itemize
The amount of time needed to scan the entire data structure is 
\begin_inset Formula $\Theta(n^{2})$
\end_inset

 that is asymptotically more complex than the time needed to scan the adjacency-
list: this is a drawback of this representation.
\end_layout

\begin_layout Itemize
The amount of time to check if a given edge 
\begin_inset Formula $(u,v)$
\end_inset

 is present in the graph is 
\begin_inset Formula $\Theta(1)$
\end_inset

 because we just need to check the relative entry in the adjacency-matrix:
 this is the major advantage of this representation.
\end_layout

\begin_layout Itemize
Generally speaking this representation is better for dense and/or small
 graphs.
\end_layout

\begin_layout Subsection
Elementary Algorithms
\end_layout

\begin_layout Subsubsection
Breadth-first search (BFS)
\end_layout

\begin_layout Standard
Given a graph 
\begin_inset Formula $G=(V,E)$
\end_inset

 and a distinguished source vertex 
\begin_inset Formula $s$
\end_inset

 this algorithm:
\end_layout

\begin_layout Itemize
assumes an adjacency-list representation;
\end_layout

\begin_layout Itemize
works both on directed and undirected graphs;
\end_layout

\begin_layout Itemize
systematically explores the edges of 
\begin_inset Formula $G$
\end_inset

 to 
\begin_inset Quotes eld
\end_inset

discover
\begin_inset Quotes erd
\end_inset

 every vertex that is reachable from 
\begin_inset Formula $s$
\end_inset

 (can be used to identify the connected components if executed on multiple
 sources);
\end_layout

\begin_layout Itemize
computes the shortest-path
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
We define the 
\emph on
shortest-path distance
\emph default
 
\begin_inset Formula $\delta(s,v)$
\end_inset

 from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 as the minimum number of edges in any path from vertex 
\begin_inset Formula $s$
\end_inset

 to vertex 
\begin_inset Formula $v$
\end_inset

; if there is no path from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 then 
\begin_inset Formula $\delta(s,v)=\infty$
\end_inset

.
\end_layout

\begin_layout Plain Layout
We call a simple path of length 
\begin_inset Formula $\delta(s,v)$
\end_inset

 from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 a 
\emph on
shortest path
\emph default
 from 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

.
 
\end_layout

\begin_layout Plain Layout
Note that this is a particular case of the more general shortest-path problem
 which involves edges with different weights.
\end_layout

\end_inset

 from 
\begin_inset Formula $s$
\end_inset

 to every reachable vertex 
\begin_inset Formula $v$
\end_inset

;
\end_layout

\begin_layout Itemize
produces a 
\emph on
breadth-first tree
\emph default
 with root 
\begin_inset Formula $s$
\end_inset

 that contains all reachable vertices (which can be used to print the (reverse-)
shortest-path from 
\begin_inset Formula $s$
\end_inset

 to any vertex 
\begin_inset Formula $v$
\end_inset

);
\end_layout

\begin_layout Itemize
uses a 
\emph on
queue
\emph default
 to store the neighbors (which ensures that the algorithm discovers all
 the vertices at distance 
\begin_inset Formula $k$
\end_inset

 from 
\begin_inset Formula $s$
\end_inset

 before discovering vertices at distance 
\begin_inset Formula $k+1$
\end_inset

;
\end_layout

\begin_layout Itemize
has a running time of 
\begin_inset Formula $O(n+m)$
\end_inset

, that is a time linear in the size of the adjacency-list representation
 (because each vertex is enqueued/dequeued only once and the adjacency-list
 of each vertex is scanned only when the vertex is dequeued.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{BFS}(G,s)$}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each vertex $u 
\backslash
in 
\backslash
attrib{G}{V}-
\backslash
{s
\backslash
}$
\end_layout

\begin_layout Plain Layout

      
\backslash
Do   
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment initialize vertices
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{u}{color} 
\backslash
gets 
\backslash
const{white}$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{u}{d} 
\backslash
gets 
\backslash
infty $
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{u}{
\backslash
pi} 
\backslash
gets 
\backslash
const{nil}$
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{s}{color} 
\backslash
gets 
\backslash
const{gray}$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment inintializes $Q$ with $s$
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{s}{d} 
\backslash
gets 0$
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{s}{
\backslash
pi} 
\backslash
gets 
\backslash
const{nil}$
\end_layout

\begin_layout Plain Layout


\backslash
li $Q 
\backslash
gets 
\backslash
emptyset$
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
proc{Enqueue}(Q,s)$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
While $Q 
\backslash
neq 
\backslash
emptyset$
\end_layout

\begin_layout Plain Layout

      
\backslash
Do 
\end_layout

\begin_layout Plain Layout


\backslash
li   $u 
\backslash
gets 
\backslash
proc{Dequeue}(Q)$    
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment fetch next vertex to be visited
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
For each $v
\backslash
in 
\backslash
attrib{G}{Adj[u]}$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment add neighbors to queue
\end_layout

\begin_layout Plain Layout

        
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li     
\backslash
If $
\backslash
attrib{u}{color} 
\backslash
isequal 
\backslash
const{white}$
\end_layout

\begin_layout Plain Layout

          
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li       $
\backslash
attrib{v}{color} 
\backslash
gets 
\backslash
const{gray}$
\end_layout

\begin_layout Plain Layout


\backslash
li       $
\backslash
attrib{v}{d} 
\backslash
gets 
\backslash
attrib{u}{d} +1$
\end_layout

\begin_layout Plain Layout


\backslash
li       $
\backslash
attrib{v}{
\backslash
pi} 
\backslash
gets u$
\end_layout

\begin_layout Plain Layout


\backslash
li       $
\backslash
proc{Enqueue}(Q,v)$
\end_layout

\begin_layout Plain Layout

        
\backslash
End
\end_layout

\begin_layout Plain Layout

      
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li    $
\backslash
attrib{u}{color} 
\backslash
gets 
\backslash
const{black}$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment mark as visited
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
Depth-first search (DFS)
\end_layout

\begin_layout Standard
Given a graph 
\begin_inset Formula $G=(V,E)$
\end_inset

 this algorithm:
\end_layout

\begin_layout Itemize
assumes an adjacency-list representation;
\end_layout

\begin_layout Itemize
works both on directed and undirected graphs;
\end_layout

\begin_layout Itemize
systematically explores the edges out of the most recently discovered vertex
 
\begin_inset Formula $v$
\end_inset

 that still has unexplored edges leaving it and, once all of 
\begin_inset Formula $v$
\end_inset

's edges have been explored, the search 
\begin_inset Quotes eld
\end_inset

backtracks
\begin_inset Quotes erd
\end_inset

 to explore edges leaving the vertex from which 
\begin_inset Formula $v$
\end_inset

 was discovered;
\end_layout

\begin_layout Itemize
produces a 
\emph on
depth-first forest
\emph default
 
\begin_inset Formula $G_{\pi}$
\end_inset

comprising several 
\emph on
depth-first trees
\emph default
;
\end_layout

\begin_layout Itemize
it's recursive, which means it implicitly uses a 
\emph on
stack
\emph default
 to store the vertices that have been 
\emph on
discovered
\emph default
 but not yet 
\emph on
finished
\emph default
;
\end_layout

\begin_layout Itemize
has a running time of 
\begin_inset Formula $O(n+m)$
\end_inset

, that is a time linear in the size of the adjacency-list representation
 (because the 
\begin_inset Quotes eld
\end_inset

visit procedure
\begin_inset Quotes erd
\end_inset

 is called once for every vertex and has a running time of 
\begin_inset Formula $\sum_{v\in V}|Adj[v]|=\Theta(m)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{DFS}(G)$}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each vertex $u 
\backslash
in 
\backslash
attrib{G}{V}$
\end_layout

\begin_layout Plain Layout

      
\backslash
Do   
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment initialize vertices
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{u}{color} 
\backslash
gets 
\backslash
const{white}$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{u}{
\backslash
pi} 
\backslash
gets 
\backslash
const{nil}$
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $time 
\backslash
gets 0$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each $u
\backslash
in 
\backslash
attrib{G}{V}$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment make sure we visit all nodes
\end_layout

\begin_layout Plain Layout

        
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li     
\backslash
If $
\backslash
attrib{u}{color} 
\backslash
isequal 
\backslash
const{white}$
\end_layout

\begin_layout Plain Layout

          
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li       $
\backslash
proc{DFS-Visit}(G,u)$
\end_layout

\begin_layout Plain Layout

        
\backslash
End
\end_layout

\begin_layout Plain Layout

      
\backslash
End
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{DFS-Visit}(G,u)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $time 
\backslash
gets time +1$
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{u}{d} 
\backslash
gets time$   
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment set $discovery$ time
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{u}{color} 
\backslash
gets 
\backslash
const{gray}$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each $v
\backslash
in 
\backslash
attrib{G}{Adj[u]}$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment add neighbors to stack
\end_layout

\begin_layout Plain Layout

      
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $
\backslash
attrib{v}{color} 
\backslash
isequal 
\backslash
const{white}$
\end_layout

\begin_layout Plain Layout

          
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li       $
\backslash
attrib{v}{
\backslash
pi} 
\backslash
gets u$
\end_layout

\begin_layout Plain Layout


\backslash
li       $
\backslash
proc{DFS-Visit}(G,v)$
\end_layout

\begin_layout Plain Layout

      
\backslash
End
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{u}{color} 
\backslash
gets 
\backslash
const{black}$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment mark as visited
\end_layout

\begin_layout Plain Layout


\backslash
li $time 
\backslash
gets time +1$
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
attrib{u}{f} 
\backslash
gets time$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment set $finishing$ time
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Edge classification
\end_layout

\begin_layout Standard
DFS can be used to classify the edges of the input graph 
\begin_inset Formula $G$
\end_inset

.
 We can define four edges types in terms of the depth-first forest 
\begin_inset Formula $G_{\pi}$
\end_inset

:
\end_layout

\begin_layout Itemize

\emph on
Tree edges
\emph default
 are edges in 
\begin_inset Formula $G_{\pi}$
\end_inset

.
 Edge 
\begin_inset Formula $(u,v)$
\end_inset

 is a tree edge if 
\begin_inset Formula $v$
\end_inset

 was first discovered by exploring edge 
\begin_inset Formula $(u,v)$
\end_inset

, which means 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{v}{color} 
\backslash
gets 
\backslash
const{white}$
\end_layout

\end_inset

.
\end_layout

\begin_layout Itemize

\emph on
Back edges
\emph default
 are those edges 
\begin_inset Formula $(u,v)$
\end_inset

 connecting a vertex 
\begin_inset Formula $u$
\end_inset

 to an ancestor 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $G_{\pi}$
\end_inset

.
 Edge 
\begin_inset Formula $(u,v)$
\end_inset

 is a back edge if 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{v}{color} 
\backslash
gets 
\backslash
const{gray}$
\end_layout

\end_inset

 when 
\begin_inset Formula $v$
\end_inset

 was first discovered by exploring edge 
\begin_inset Formula $(u,v)$
\end_inset

.
 
\end_layout

\begin_layout Itemize

\emph on
Forward edges
\emph default
 are those nontree edges 
\begin_inset Formula $(u,v)$
\end_inset

 connecting a vertex 
\begin_inset Formula $u$
\end_inset

 to a descendant 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $G_{\pi}$
\end_inset

.
 Edge 
\begin_inset Formula $(u,v)$
\end_inset

 is a forward edge if 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{v}{color} 
\backslash
gets 
\backslash
const{black}$
\end_layout

\end_inset

 and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
attrib{u}{d} < 
\backslash
attrib{v}{d}
\end_layout

\end_inset

 when 
\begin_inset Formula $v$
\end_inset

 was first discovered by exploring edge 
\begin_inset Formula $(u,v)$
\end_inset

.
 
\end_layout

\begin_layout Itemize

\emph on
Cross edges
\emph default
 are all other edges.
 They can go between vertices in different dept-first trees or vertices
 in the same depth-first tree, as long as one vertex is not an ancestor
 of the other.
 Edge 
\begin_inset Formula $(u,v)$
\end_inset

 is a cross edge if 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
attrib{v}{color} 
\backslash
gets 
\backslash
const{black}$
\end_layout

\end_inset

 and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
attrib{u}{d} > 
\backslash
attrib{v}{d}
\end_layout

\end_inset

 when 
\begin_inset Formula $v$
\end_inset

 was first discovered by exploring edge 
\begin_inset Formula $(u,v)$
\end_inset

.
 
\end_layout

\begin_layout Standard
In undirected graphs, since 
\begin_inset Formula $(u,v)$
\end_inset

 and 
\begin_inset Formula $(v,u)$
\end_inset

 are the same edge we classify the edges as the first type in the classification
 list that applies.
 It can be shown that in a DFS of an undirected graph 
\begin_inset Formula $G$
\end_inset

, every edge of 
\begin_inset Formula $G$
\end_inset

 is either a tree edge or a back edge, which means that forward and cross
 edges never occur.
\end_layout

\begin_layout Standard
A directed graph is acyclic if and only if a DFS yields no back edges.
\end_layout

\begin_layout Paragraph
Parenthesis structure
\end_layout

\begin_layout Standard
In any DFS of a (directed or undirected) graph 
\begin_inset Formula $G=(V,E)$
\end_inset

, for any two vertices 
\begin_inset Formula $u$
\end_inset

 and 
\begin_inset Formula $v$
\end_inset

, exactly one of the following three conditions holds:
\end_layout

\begin_layout Itemize
the intervals 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

[
\backslash
attrib{u}{d},
\backslash
attrib{u}{f}]
\end_layout

\end_inset

 and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

[
\backslash
attrib{v}{d},
\backslash
attrib{v}{f}]
\end_layout

\end_inset

 are entirely disjoint, and neither 
\begin_inset Formula $u$
\end_inset

 nor 
\begin_inset Formula $v$
\end_inset

 is a descendant of the other in 
\begin_inset Formula $G_{\pi}$
\end_inset

.
\end_layout

\begin_layout Itemize
the interval 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

[
\backslash
attrib{u}{d},
\backslash
attrib{u}{f}]
\end_layout

\end_inset

 is contained entirely within the interval 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

[
\backslash
attrib{v}{d},
\backslash
attrib{v}{f}]
\end_layout

\end_inset

 and 
\begin_inset Formula $u$
\end_inset

 is a descendant of 
\begin_inset Formula $v$
\end_inset

 in 
\begin_inset Formula $G_{\pi}$
\end_inset

.
\end_layout

\begin_layout Itemize
the interval 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

[
\backslash
attrib{v}{d},
\backslash
attrib{v}{f}]
\end_layout

\end_inset

 is contained entirely within the interval 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

[
\backslash
attrib{u}{d},
\backslash
attrib{u}{f}]
\end_layout

\end_inset

 and 
\begin_inset Formula $v$
\end_inset

 is a descendant of 
\begin_inset Formula $u$
\end_inset

 in 
\begin_inset Formula $G_{\pi}$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Tree traversal
\end_layout

\begin_layout Standard
Since trees are a particular kind of graph we can use both BFS and DFS on
 them.
 There are however some notation consideration that need to be done.
\end_layout

\begin_layout Itemize
BFS is also called 
\emph on
level-order traversal
\emph default
 since, once we apply such an algorithm starting at the root of a tree,
 we visit every node on a level before going to a lower level.
 (since the neighbor of any node are simply its children and its parent
 which we have already visited)
\end_layout

\begin_layout Itemize
Once we implement 
\shape smallcaps
DFS-Visit
\shape default

\begin_inset Formula $(G,n)$
\end_inset

 we have three significant choices when picking the order in which we can
 visit the current node and its neighbors.
 This choice has practical consequences when we run DFS on a tree starting
 from the root.
 
\end_layout

\begin_deeper
\begin_layout Itemize

\emph on
Preorder visit
\emph default
: we access the node before visiting all of its neighbor
\end_layout

\begin_layout Itemize

\emph on
Inorder visit
\emph default
: we access the node after visiting some of its neighbor and before visiting
 some others (several policies can be used)
\end_layout

\begin_layout Itemize

\emph on
Postorder visit
\emph default
: we access the node 
\emph on
after
\emph default
 visiting all of its neighbor, while recursion is returning
\end_layout

\end_deeper
\begin_layout Itemize
Traversing a tree always costs 
\begin_inset Formula $\Theta(n)$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Topological Sort
\end_layout

\begin_layout Standard
A 
\emph on
topological sort
\emph default
 of a dag 
\begin_inset Formula $G=(V,E)$
\end_inset

 is a linear ordering of all its vertices such that if 
\begin_inset Formula $G$
\end_inset

 contains an edge 
\begin_inset Formula $(u,v)$
\end_inset

 then 
\begin_inset Formula $u$
\end_inset

 appears before 
\begin_inset Formula $v$
\end_inset

 in the ordering.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Topological-Sort}(G)$}
\end_layout

\begin_layout Plain Layout


\backslash
li call $
\backslash
proc{DFS}(G)$ to compute finishing times $
\backslash
attrib{v}{f}$ for each vertex $v$
\end_layout

\begin_layout Plain Layout


\backslash
li as each vertex is finished, insert it onto the front of a linked list
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return the linked list of vertices
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Time complexity
\end_layout

\begin_layout Standard
We can perform a topological sort in time 
\begin_inset Formula $\Theta(n+m)$
\end_inset

, since DFS takes 
\begin_inset Formula $\Theta(n+m)$
\end_inset

 time and it takes 
\begin_inset Formula $O(1)$
\end_inset

 time to insert each of the 
\begin_inset Formula $n$
\end_inset

 vertices onto the front of the linked list.
\end_layout

\begin_layout Subsubsection
Strongly connected components
\end_layout

\begin_layout Standard
The key idea behind this algorithm is that 
\begin_inset Formula $G$
\end_inset

 and 
\begin_inset Formula $G^{T}$
\end_inset

 have the same connected components, which means that 
\begin_inset Formula $u$
\end_inset

 and 
\begin_inset Formula $v$
\end_inset

 are reachable from each other in 
\begin_inset Formula $G$
\end_inset

 if and only if they are reachable from each other in 
\begin_inset Formula $G^{T}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Strongly-Connected-Components}(G)$}
\end_layout

\begin_layout Plain Layout


\backslash
li call $
\backslash
proc{DFS}(G)$ to compute finishing times $
\backslash
attrib{v}{f}$ for each vertex $v$
\end_layout

\begin_layout Plain Layout


\backslash
li compute $G^T$
\end_layout

\begin_layout Plain Layout


\backslash
li call $
\backslash
proc{DFS}(G^T)$, but in the main loop of 
\backslash
proc{DFS}, consider the vertices in order 
\end_layout

\begin_layout Plain Layout


\backslash
zi 
\backslash
> of decreasing $
\backslash
attrib{v}{f}$ (as computed in line 1)
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return the vertices of each tree in the depth-first forest formed in line
 3 as 
\end_layout

\begin_layout Plain Layout


\backslash
zi 
\backslash
> a separated strongly connected component
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Time complexity 
\end_layout

\begin_layout Standard
We can find the strongly connected components of a directed graph in 
\begin_inset Formula $O(n+m)$
\end_inset

, since the time needed to create 
\begin_inset Formula $G^{T}$
\end_inset

 is 
\begin_inset Formula $O(n+m)$
\end_inset

 and DFS runs in 
\begin_inset Formula $\Theta(n+m)$
\end_inset

.
\end_layout

\begin_layout Subsection
Minimum Spanning Trees
\end_layout

\begin_layout Standard
The following algorithms are a classic example of greedy algorithms.
 
\end_layout

\begin_layout Standard
The problem they try to solve is : given a connected, undirected graph 
\begin_inset Formula $G=(V,E)$
\end_inset

 with a weight function 
\begin_inset Formula $w:E\rightarrow\mathbb{R}$
\end_inset

, we wish to find a minimum spanning tree for 
\begin_inset Formula $G$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Kruskal's algorithm
\end_layout

\begin_layout Standard
Kruskal's algorithm: 
\end_layout

\begin_layout Itemize
finds a safe edge to add to the growing forest by finding, of all edges
 that connect any two trees in the forest, an edge 
\begin_inset Formula $(u,v)$
\end_inset

 of least weight.
\end_layout

\begin_layout Itemize
qualifies as a greedy algorithm because at each step it adds to the forest
 an edge of least possible weight.
\end_layout

\begin_layout Paragraph
Implementation
\end_layout

\begin_layout Standard
A classic implementation of Kruskal's algorithm uses the union-find data
 structure to maintain several disjoint sets of elements.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{MST-Kruskal}(G,w)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $A 
\backslash
gets 
\backslash
emptyset$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each vertex $v
\backslash
in 
\backslash
attrib{G}{V}$ 
\backslash
Do  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment initialize the data structure
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
proc{Make-Set}(v) 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li sort the edges of $
\backslash
attrib{G}{E}$ into nondecreasing order by weight $w$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each edge $(u,v)
\backslash
in 
\backslash
attrib{G}{E}$, taken in nondecreasing order by weight 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $
\backslash
proc{Find-Set}(u) 
\backslash
neq 
\backslash
proc{Find-Set}(v)$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li      $A 
\backslash
gets A
\backslash
cup 
\backslash
{(u,v)
\backslash
} $
\end_layout

\begin_layout Plain Layout


\backslash
li      $
\backslash
proc{Union}(u,v)$
\end_layout

\begin_layout Plain Layout

      
\backslash
End
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $A$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Time complexity (analysis)
\end_layout

\begin_layout Standard
The running time of Kruskal's algorithm clearly depends on the union-find
 data structure operations.
 We perform a total of 
\begin_inset Formula $n$
\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Make-Set}$
\end_layout

\end_inset

 operations (lines 2-3) and 
\begin_inset Formula $O(m)$
\end_inset

 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Union}$
\end_layout

\end_inset

 and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$
\backslash
proc{Find-Set}$
\end_layout

\end_inset

 operations (lines 5-8).
 The total time required to perform such operations is 
\begin_inset Formula $O((n+m)\alpha(n))$
\end_inset

 (see theorem on cost of union-find operations).
 
\end_layout

\begin_layout Standard
Recall that we assumed that 
\begin_inset Formula $G$
\end_inset

 is connected, which means that 
\begin_inset Formula $m\geq n-1$
\end_inset

 and that 
\begin_inset Formula $\alpha(n)=O(\log n)=O(\log m)$
\end_inset

.
 We can then write 
\begin_inset Formula $O((n+m)\alpha(n))=O(m\alpha(n))=O(m\log m)$
\end_inset

.
 
\end_layout

\begin_layout Standard
Now, recall that 
\begin_inset Formula $m<n^{2}$
\end_inset

 for any graph, which implies 
\begin_inset Formula $\log m=O(\log n^{2})=O(2\log n)=O(\log n)$
\end_inset

.
 We can then write 
\begin_inset Formula $O(m\log m)=O(m\log n)$
\end_inset

.
\end_layout

\begin_layout Paragraph
Time complexity (conclusion)
\end_layout

\begin_layout Standard
Provided that the edges are 
\emph on
already sorted
\emph default
 or can be sorted in linear time (for instance with radix sort), then the
 time complexity of Kruskal's algorithm is 
\begin_inset Formula $O(m\alpha(n))$
\end_inset

, 
\begin_inset Formula $O(m\log n)$
\end_inset

 otherwise.
 
\end_layout

\begin_layout Subsubsection
Prim's algorithm
\end_layout

\begin_layout Standard
Prim's algorithm:
\end_layout

\begin_layout Itemize
has the property that the edges in the set 
\begin_inset Formula $A$
\end_inset

 always form a single tree.
 The tree starts from an arbitrary root vertex 
\begin_inset Formula $r$
\end_inset

 and grows until the tree spans all the vertices in 
\begin_inset Formula $V$
\end_inset

.
\end_layout

\begin_layout Itemize
qualifies as greedy algorithm because at each step it adds to the tree 
\begin_inset Formula $A$
\end_inset

 an edge that contributes the minimum amount possible to the tree's weight
 and connects 
\begin_inset Formula $A$
\end_inset

 to an isolated vertex.
\end_layout

\begin_layout Paragraph
Implementation
\end_layout

\begin_layout Standard
A classic implementation of Prim's algorithm stores all the vertices 
\begin_inset Formula $v$
\end_inset

 that are not in the tree in a min-priority queue 
\begin_inset Formula $Q$
\end_inset

 based on a 
\begin_inset Formula $key$
\end_inset

 attribute which represents the minimum weight of any edge connecting 
\begin_inset Formula $v$
\end_inset

 to a vertex in the tree; by convention 
\begin_inset Formula $v=\infty$
\end_inset

 if there is no such edge.
\end_layout

\begin_layout Standard
The algorithm implicitly maintains the set 
\begin_inset Formula $A$
\end_inset

 as 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$A=
\backslash
{(v,
\backslash
attrib{v}{
\backslash
pi}):v
\backslash
in V - 
\backslash
{r
\backslash
} - Q 
\backslash
}$
\end_layout

\end_inset

; therefore, when the algorithm terminates the MST 
\begin_inset Formula $A$
\end_inset

 for 
\begin_inset Formula $G$
\end_inset

 is 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout

$A=
\backslash
{(v,
\backslash
attrib{v}{
\backslash
pi}):v
\backslash
in V - 
\backslash
{r
\backslash
} 
\backslash
}$
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{MST-Prim}(G,w,r)$}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each vertex $u
\backslash
in 
\backslash
attrib{G}{V}$ 
\backslash
Do  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment initialize the vertices
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{u}{key} 
\backslash
gets 
\backslash
infty$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{u}{
\backslash
pi} 
\backslash
gets 
\backslash
const{nil}$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $ 
\backslash
attrib{r}{key} 
\backslash
gets 0$  
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
>
\backslash
> 
\backslash
Comment initializes the root
\end_layout

\begin_layout Plain Layout


\backslash
li $ Q 
\backslash
gets 
\backslash
attrib{G}{V}$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
While $Q 
\backslash
neq 
\backslash
emptyset$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li    $u 
\backslash
gets 
\backslash
proc{Extract-Min}(Q)$
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
For each vertex $v
\backslash
in
\backslash
attrib{G}{Adj[u]}$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li       
\backslash
If $v 
\backslash
in Q$ and $w(u,v)<
\backslash
attrib{v}{key}$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li          $
\backslash
attrib{v}{
\backslash
pi} 
\backslash
gets u$
\end_layout

\begin_layout Plain Layout


\backslash
li          $
\backslash
attrib{v}{key} 
\backslash
gets w(u,v)$
\end_layout

\begin_layout Plain Layout

          
\backslash
End
\end_layout

\begin_layout Plain Layout

       
\backslash
End
\end_layout

\begin_layout Plain Layout

    
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset

 
\end_layout

\begin_layout Paragraph
Time complexity
\end_layout

\begin_layout Standard
The total time required for all calls to 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Extract-Min}
\end_layout

\end_inset

 is 
\begin_inset Formula $O(n\log n)$
\end_inset

, since the main loop executes 
\begin_inset Formula $n$
\end_inset

 times and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Extract-Min}
\end_layout

\end_inset

 operation takes 
\begin_inset Formula $O(\log n)$
\end_inset

 time.
\end_layout

\begin_layout Standard
The total time required by the inner loop is 
\begin_inset Formula $O(m\log n)$
\end_inset

, since the loop executes 
\begin_inset Formula $2m$
\end_inset

 times (length of the adjacency list) and the time required to restructure
 the heap (that needs to be done every time a key is modified) is 
\begin_inset Formula $O(\log n)$
\end_inset

.
\end_layout

\begin_layout Standard
Therefore the total time for Prim's algorithm is 
\begin_inset Formula $O((n+m)\log n)=O(m\log n)$
\end_inset

.
 (Recall that the graph is connected!)
\end_layout

\begin_layout Subsection
Single-Source Shortest Paths
\end_layout

\begin_layout Standard
In a 
\emph on
shortest-path problem
\emph default
 we are given a weighted, directed graph 
\begin_inset Formula $G=(V,E)$
\end_inset

, with weight function 
\begin_inset Formula $w:E\rightarrow\mathbb{R}$
\end_inset

 mapping edges to real-valued weights.
 The weight 
\begin_inset Formula $w(p)$
\end_inset

 of path 
\begin_inset Formula $p=\langle v_{1},v_{2},\ldots,v_{k}\rangle$
\end_inset

 is the sum of the weights of its constituent edges: 
\begin_inset Formula $w(p)=\sum_{i=1}^{k}w(v_{i-1},v_{i})$
\end_inset

.
 We define the 
\emph on
shortest-path weight 
\emph default

\begin_inset Formula $\delta(u,v)$
\end_inset

 from 
\begin_inset Formula $u$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 by 
\begin_inset Formula 
\[
\delta(u,v)=\begin{cases}
\min\{w(p):u\overset{p}{\rightsquigarrow}v\} & \text{if there is a path form \ensuremath{u}to \ensuremath{v}}\\
\infty & \text{otherwise}
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
A s
\emph on
hortest path
\emph default
 from vertex 
\begin_inset Formula $u$
\end_inset

 to vertex 
\begin_inset Formula $v$
\end_inset

 is then defined as any path 
\begin_inset Formula $p$
\end_inset

 with weight 
\begin_inset Formula $\delta(u,v)$
\end_inset

.
 There are several variants of the shortest-path problem including:
\end_layout

\begin_layout Description
Single-source
\begin_inset space ~
\end_inset

shortest
\begin_inset space ~
\end_inset

path: given a graph we want to find the shortest path from a given 
\emph on
source
\emph default
 vertex 
\begin_inset Formula $s$
\end_inset

 to all other vertices.
\end_layout

\begin_layout Description
Single-destination
\begin_inset space ~
\end_inset

shortest
\begin_inset space ~
\end_inset

path: given a graph we want to find the shortest path from a given 
\emph on
destination
\emph default
 vertex 
\begin_inset Formula $t$
\end_inset

 to all other vertices.
 We solve this problem solving single-source shortest path on 
\begin_inset Formula $G^{T}$
\end_inset

.
\end_layout

\begin_layout Description
Single-pair
\begin_inset space ~
\end_inset

shortest
\begin_inset space ~
\end_inset

path: given a graph we want to find the shortest path from 
\begin_inset Formula $u$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 for given vertices 
\begin_inset Formula $u$
\end_inset

 and 
\begin_inset Formula $v$
\end_inset

.
 We solve this problem by solving single-source shortest path with source
 
\begin_inset Formula $u$
\end_inset

.
 Moreover, all known algorithms for this problem have the same worst-case
 asymptotic running time as the best single-source algorithms.
\end_layout

\begin_layout Description
All-pairs
\begin_inset space ~
\end_inset

shortest
\begin_inset space ~
\end_inset

path: given a graph we want to find the shortest path from 
\begin_inset Formula $u$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

 for every pair of vertices 
\begin_inset Formula $u$
\end_inset

 and 
\begin_inset Formula $v$
\end_inset

.
 We solve this problem either solving single-source shortest path with source
 
\begin_inset Formula $u$
\end_inset

 for every choice of 
\begin_inset Formula $u$
\end_inset

 or we Floyd-Warshall algorithm (or equivalent).
\end_layout

\begin_layout Subsubsection
Cycles and negative-weight edges
\end_layout

\begin_layout Itemize
If the graph 
\begin_inset Formula $G=(V,E)$
\end_inset

 contains no 
\emph on
negative-weight cycles
\emph default
 reachable from the source 
\begin_inset Formula $s$
\end_inset

, then for all 
\begin_inset Formula $v\in V$
\end_inset

, the shortest path weight 
\begin_inset Formula $\delta(s,v)$
\end_inset

 remains well defined, even if it has a negative value.
 
\end_layout

\begin_layout Itemize
A shortest path cannot contain a positive-weight cycle, since removing the
 cycle from the path produces a path with the same source and destination
 vertices and a lower path weight.
\end_layout

\begin_layout Itemize
Since any acyclic path in a graph 
\begin_inset Formula $G$
\end_inset

 contains at most 
\begin_inset Formula $|V|$
\end_inset

 distinct vertices, it also contains at most 
\begin_inset Formula $|V|-1$
\end_inset

 edges.
 Thus, we can restrict out attention to shortest paths of at most 
\begin_inset Formula $|V|-1$
\end_inset

 edges.
\end_layout

\begin_layout Subsubsection
Path representation and relaxation
\end_layout

\begin_layout Standard
We represent shortest paths similarly to how we represented breadth-first
 trees; we maintain, for every vertex 
\begin_inset Formula $v$
\end_inset

, a predecessor 
\begin_inset Formula $v.\pi$
\end_inset

 that is either another vertex or 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
const{nil}
\end_layout

\end_inset

.
 This will produce, once the algorithms terminate, a predecessor subgraph
 
\begin_inset Formula $G_{\pi}$
\end_inset

 which represents the shortest-path tree.
\end_layout

\begin_layout Standard
We maintain an attribute 
\begin_inset Formula $v.d$
\end_inset

 for every vertex 
\begin_inset Formula $v$
\end_inset

 which is an upper bound on the weight of a shortest path from source 
\begin_inset Formula $s$
\end_inset

 to 
\begin_inset Formula $v$
\end_inset

.
 We call 
\begin_inset Formula $v.d$
\end_inset

 a shortest path estimate.
 
\end_layout

\begin_layout Standard
We initialize 
\begin_inset Formula $v.\pi$
\end_inset

 and 
\begin_inset Formula $v.d$
\end_inset

 with the following 
\begin_inset Formula $\Theta(n)$
\end_inset

 procedure.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Inintialize-Single-Source}(G,s)$}
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each vertex $v
\backslash
in 
\backslash
attrib{G}{V}$ 
\backslash
Do 
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{v}{d} 
\backslash
gets 
\backslash
infty$
\end_layout

\begin_layout Plain Layout


\backslash
li   $
\backslash
attrib{v}{
\backslash
pi} 
\backslash
gets 
\backslash
const{nil}$ 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li $ 
\backslash
attrib{s}{d} 
\backslash
gets 0$ 
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
The process of relaxing an edge 
\begin_inset Formula $(u,v)$
\end_inset

 consists of testing whether we can improve the shortest path to 
\begin_inset Formula $v$
\end_inset

 found so far by going through 
\begin_inset Formula $u$
\end_inset

 and, if so, updating 
\begin_inset Formula $v.d$
\end_inset

 and 
\begin_inset Formula $v.\pi$
\end_inset

.
 The following code performs the relaxation step on edge 
\begin_inset Formula $(u,v)$
\end_inset

 in 
\begin_inset Formula $O(1)$
\end_inset

 time.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Relax}(u,v,w)$}
\end_layout

\begin_layout Plain Layout


\backslash
li       
\backslash
If $
\backslash
attrib{v}{d} > 
\backslash
attrib{u}{d} + w(u,v)$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li          $
\backslash
attrib{v}{d} 
\backslash
gets 
\backslash
attrib{u}{d} + w(u,v)$
\end_layout

\begin_layout Plain Layout


\backslash
li          $
\backslash
attrib{v}{
\backslash
pi} 
\backslash
gets u$
\end_layout

\begin_layout Plain Layout

          
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection
The Bellman-Ford algorithm
\end_layout

\begin_layout Standard
The Bellman-Ford algorithm solves the single-source shortest path problem
 in the general case in which edge weights may be negative.
 
\end_layout

\begin_layout Standard
Given a weighted, directed graph 
\begin_inset Formula $G$
\end_inset

 with source 
\begin_inset Formula $s$
\end_inset

 and weight function, the algorithm returns a Boolean value indicating whether
 or not there is a negative-weight cycle that is reachable from the source.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Bellman-Ford}(G,w,s)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
proc{Inintialize-Single-Source}(G,s)$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $i 
\backslash
gets 1 
\backslash
To |
\backslash
attrib{G}{V}|-1 $ 
\backslash
Do 
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
For each edge $(u,v) 
\backslash
in 
\backslash
attrib{G}{E}$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li     $
\backslash
proc{Relax}(u,v,w)$ 
\backslash
End 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For each edge $(u,v) 
\backslash
in 
\backslash
attrib{G}{E}$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
If $
\backslash
attrib{v}{d} > 
\backslash
attrib{u}{d} + w(u,v)$ 
\backslash
Then
\end_layout

\begin_layout Plain Layout


\backslash
li     
\backslash
Return 
\backslash
const{false} 
\backslash
End 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $
\backslash
const{true}$ 
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Time complexity
\end_layout

\begin_layout Standard
The Bellman-Ford algorithm runs in time 
\begin_inset Formula $O(nm)$
\end_inset

, since the initialization in line 1 takes 
\begin_inset Formula $\Theta(n)$
\end_inset

 time, each of the 
\begin_inset Formula $|V|-1$
\end_inset

 passes over the edges in lines 2-4 takes 
\begin_inset Formula $\Theta(m)$
\end_inset

 time, and the for loop of lines 5-7 takes 
\begin_inset Formula $O(m)$
\end_inset

 time.
\end_layout

\begin_layout Subsubsection
Dijkstra's algorithm
\end_layout

\begin_layout Standard
Dijkstra's algorithm solves the single-source shortest path problem on a
 weighted graph 
\begin_inset Formula $G$
\end_inset

 for the case in which all edge weights are nonnegative.
 Therefore, we assume that 
\begin_inset Formula $w(u,v)\geq0$
\end_inset

 for each edge.
 
\end_layout

\begin_layout Standard
Dijkstra's algorithm maintains a set 
\begin_inset Formula $S$
\end_inset

 of vertices whose final shortest path weights from the source 
\begin_inset Formula $s$
\end_inset

 have already been determined.
 The algorithm repeatedly selects the vertex 
\begin_inset Formula $u\in V-S$
\end_inset

 with the minimum shortest path estimate, adds 
\begin_inset Formula $u$
\end_inset

 to 
\begin_inset Formula $S$
\end_inset

 and relaxes all edges leaving 
\begin_inset Formula $u$
\end_inset

.
 Because Dijkstra's algorithm always chooses the 
\begin_inset Quotes eld
\end_inset

lightest
\begin_inset Quotes erd
\end_inset

 (or 
\begin_inset Quotes eld
\end_inset

closest
\begin_inset Quotes erd
\end_inset

) vertex in 
\begin_inset Formula $V-S$
\end_inset

 to add to set 
\begin_inset Formula $S$
\end_inset

, we say that it uses a greedy strategy.
\end_layout

\begin_layout Standard
The following implementation uses a min-priority queue 
\begin_inset Formula $Q$
\end_inset

 of vertices keyed by their 
\begin_inset Formula $d$
\end_inset

 values.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Dijkstra}(G,w,s)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $
\backslash
proc{Inintialize-Single-Source}(G,s)$
\end_layout

\begin_layout Plain Layout


\backslash
li $S 
\backslash
gets 
\backslash
emptyset$
\end_layout

\begin_layout Plain Layout


\backslash
li $Q 
\backslash
gets 
\backslash
attrib{G}{V}$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
While $Q 
\backslash
neq 
\backslash
emptyset $ 
\backslash
Do 
\end_layout

\begin_layout Plain Layout


\backslash
li   $u 
\backslash
gets 
\backslash
proc{Extract-Min}(Q)$
\end_layout

\begin_layout Plain Layout


\backslash
li   $S 
\backslash
gets S
\backslash
cup 
\backslash
{u
\backslash
}$
\end_layout

\begin_layout Plain Layout


\backslash
li   
\backslash
For each vertex $v 
\backslash
in 
\backslash
attrib{G}{Adj[u]}$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li     $
\backslash
proc{Relax}(u,v,w)$ 
\backslash
End 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Time complexity
\end_layout

\begin_layout Standard
Because each vertex 
\begin_inset Formula $u$
\end_inset

 is added to the set 
\begin_inset Formula $S$
\end_inset

 exactly once the while loop in lines 4-8 is executed exactly 
\begin_inset Formula $|V|$
\end_inset

 times.
 Also, each edge is examined exactly once in the for of lines 7-8, which
 means that this loop iterates a total of 
\begin_inset Formula $|E|$
\end_inset

 times.
 
\end_layout

\begin_layout Standard
If we implement the priority queue using an array, each 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Insert}
\end_layout

\end_inset

 and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Relax}
\end_layout

\end_inset

 operation takes 
\begin_inset Formula $O(1)$
\end_inset

 time, and each 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Extract-Min}
\end_layout

\end_inset

 operations takes 
\begin_inset Formula $O(n)$
\end_inset

 time (because we have to scan the whole array).
 Thus, the running time of Dijkstra's algorithm is 
\begin_inset Formula $O(n^{2}+m)=O(n^{2})$
\end_inset

 (since 
\begin_inset Formula $m\leq n^{2}$
\end_inset

 in any graph).
\end_layout

\begin_layout Standard
Vice-versa, if we implement the priority queue using a min-heap we know
 that both 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Extract-Min}
\end_layout

\end_inset

 and 
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
proc{Relax}
\end_layout

\end_inset

 need 
\begin_inset Formula $O(\log n)$
\end_inset

.
 Thus, the total running time of Dijkstra's algorithm is 
\begin_inset Formula $O((n+m)\log n)$
\end_inset

, which is 
\begin_inset Formula $O(m\log n)$
\end_inset

 if all the vertices are reachable from the source.
 This running time improves upon the straightforward array implementation
 only if the graph is sufficiently sparse (i.e.
 
\begin_inset Formula $m=o(\frac{n^{2}}{\log n})$
\end_inset

.
\end_layout

\begin_layout Subsection
All-Pairs shortest Paths
\end_layout

\begin_layout Subsubsection
Iterated Dijkstra and Bellman-Ford's algorithms
\end_layout

\begin_layout Standard
We can solve an all-pair shortest path problem by running a single-source
 shortest paths algorithm 
\begin_inset Formula $n$
\end_inset

 times.
 
\end_layout

\begin_layout Standard
If all edged are nonnegative, we can use Dijkstra's algorithm.
 If we use the linked list implementation, the running time is 
\begin_inset Formula $O(n^{3}+nm)$
\end_inset

.
 If we use the min-heap implementation, instead, the running time is 
\begin_inset Formula $O(nm\log n)$
\end_inset

.
\end_layout

\begin_layout Standard
If we have negative-weight edges we need to iterate Bellman-Ford algorithms
 which yields a time complexity of 
\begin_inset Formula $O(n^{2}m)$
\end_inset

 which on a dense graph is 
\begin_inset Formula $O(n^{4})$
\end_inset

.
\end_layout

\begin_layout Subsubsection
Floyd-Warshall's algorithm
\end_layout

\begin_layout Standard
Unlike the majority of graph algorithms, Floyd-Warshall algorithm assumes
 that the input graph 
\begin_inset Formula $G=(V,E)$
\end_inset

 is represented using an adjacency matrix representation.
 For convenience, we assume that the vertices are numbered 
\begin_inset Formula $1,2,\ldots,n$
\end_inset

, so that the input is an 
\begin_inset Formula $n\times n$
\end_inset

 matrix 
\begin_inset Formula $W=(w_{ij})$
\end_inset

 representing the edge weights and defined as follows
\begin_inset Formula 
\[
w_{ij}=\begin{cases}
0 & \text{if }i=j\\
w(i,j) & \text{if }i\neq j\text{ and }(i,j)\in E\\
\infty & \text{if }i\neq j\text{ and }(i,j)\notin E
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
We
\emph on
 allow negative-weight edges
\emph default
, but we assume that the input graph contains 
\emph on
no negative-length cycles
\emph default
.
\end_layout

\begin_layout Standard
The output of of the algorithm is the 
\begin_inset Formula $n\times n$
\end_inset

 matrix 
\begin_inset Formula $D=(d_{ij})$
\end_inset

, where entry 
\begin_inset Formula $d_{ij}$
\end_inset

 contains the weight of a shortest path from vertex 
\begin_inset Formula $i$
\end_inset

 to vertex 
\begin_inset Formula $j$
\end_inset

.
 That is, if we let 
\begin_inset Formula $\delta(i,j)$
\end_inset

 denote the shortest path weight from vertex 
\begin_inset Formula $i$
\end_inset

 to vertex 
\begin_inset Formula $j$
\end_inset

, then 
\begin_inset Formula $d_{ij}=\delta(i,j)$
\end_inset

 at termination.
 
\end_layout

\begin_layout Standard
To solve the all-pair shortest path problem on an input adjacency matrix,
 we need to compute not only the shortest path weights but also the predecessor
 matrix 
\begin_inset Formula $\Pi=(\pi_{ij})$
\end_inset

, where 
\begin_inset Formula $\pi_{ij}$
\end_inset

 is 
\begin_inset Formula $\const{nil}$
\end_inset

 if either 
\begin_inset Formula $i=j$
\end_inset

 or there is no path from 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $j$
\end_inset

, and otherwise 
\begin_inset Formula $\pi_{ij}$
\end_inset

 is the predecessor of 
\begin_inset Formula $j$
\end_inset

 on some shortest path from 
\begin_inset Formula $i$
\end_inset

.
\end_layout

\begin_layout Paragraph
Implementation
\end_layout

\begin_layout Standard
The Floyd-Warshall algorithm takes a completely different approach and relies
 on the following observation.
 
\end_layout

\begin_layout Standard
For any pair of vertices 
\begin_inset Formula $i,j\in V$
\end_inset

, consider all shortest paths from 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $j$
\end_inset

 whose intermediate vertices are drawn from a subset 
\begin_inset Formula $\{1,2,\ldots,k\}$
\end_inset

, and let 
\begin_inset Formula $p$
\end_inset

 be a minimum-weight path from among them.
 
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $k$
\end_inset

 is not an intermediate vertex on path 
\begin_inset Formula $p$
\end_inset

, then all intermediate vertices of path 
\begin_inset Formula $p$
\end_inset

 are in the set 
\begin_inset Formula $\{1,2,\ldots,k-1\}$
\end_inset

.
 Thus a shortest path from vertex 
\begin_inset Formula $i$
\end_inset

 to vertex 
\begin_inset Formula $j$
\end_inset

 with all intermediate vertices in the set 
\begin_inset Formula $\{1,2,\ldots,k-1\}$
\end_inset

 is also a shortest path from 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $j$
\end_inset

 with all intermediate vertices in 
\begin_inset Formula $\{1,2,\ldots,k\}$
\end_inset

.
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $k$
\end_inset

 is an intermediate vertex on path 
\begin_inset Formula $p$
\end_inset

, then we decompose 
\begin_inset Formula $p$
\end_inset

 into 
\begin_inset Formula $i\overset{p_{1}}{\rightsquigarrow}k\overset{p_{2}}{\rightsquigarrow}j$
\end_inset

.
 
\begin_inset Formula $p_{1}$
\end_inset

 is a shortest path from 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $k$
\end_inset

 with all intermediate vertices in the set 
\begin_inset Formula $\{1,2,\ldots,k\}$
\end_inset

.
 Because vertex 
\begin_inset Formula $k$
\end_inset

 is not an intermediate vertex of path 
\begin_inset Formula $p_{1}$
\end_inset

, all intermediate vertices of 
\begin_inset Formula $p_{1}$
\end_inset

 are in the set 
\begin_inset Formula $\{1,2,\ldots,k-1\}$
\end_inset

.
 Since subpaths of shortest paths are shortest paths, 
\begin_inset Formula $p_{1}$
\end_inset

 is a shortest path from 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $k$
\end_inset

 with all intermediate vertices in the set 
\begin_inset Formula $\{1,2,\ldots,k-1\}$
\end_inset

.
 Similarly 
\begin_inset Formula $p_{2}$
\end_inset

 is a shortest path from vertex 
\begin_inset Formula $k$
\end_inset

 to vertex 
\begin_inset Formula $j$
\end_inset

 with all intermediate vertices in the set 
\begin_inset Formula $\{1,2,\ldots,k-1\}$
\end_inset

.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $d_{ij}^{(k)}$
\end_inset

be the weights of a shortest path from vertex 
\begin_inset Formula $i$
\end_inset

 to vertex 
\begin_inset Formula $j$
\end_inset

 for which all intermediate vertices are in the set 
\begin_inset Formula $\{1,2,\ldots,k\}$
\end_inset

.
 When 
\begin_inset Formula $k=0$
\end_inset

, a path from 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $j$
\end_inset

 has no intermediate vertices at all (i.e.
 it has at most one edge) and therefore 
\begin_inset Formula $d_{ij}^{(0)}=w_{ij}$
\end_inset

.
 Based on the previous observations we can define 
\begin_inset Formula $d_{ij}^{(k)}$
\end_inset

 recursively by
\begin_inset Formula 
\[
d_{ij}^{(k)}=\begin{cases}
w_{ij} & \text{if }k=0\\
\min(d_{ij}^{(k)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}) & \text{if }k\geq1
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
Because for any path, all intermediate vertices are in the set 
\begin_inset Formula $\{1,2,\ldots,n\}$
\end_inset

, the matrix 
\begin_inset Formula $D^{(n)}=(d_{ij}^{(n)})$
\end_inset

 gives the final answer: 
\begin_inset Formula $\delta(i,j)$
\end_inset

 for all 
\begin_inset Formula $i,j\in V$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status collapsed

\begin_layout Plain Layout


\backslash
begin{codebox}
\end_layout

\begin_layout Plain Layout


\backslash
Procname{$
\backslash
proc{Floyd-Warshall}(W)$}
\end_layout

\begin_layout Plain Layout


\backslash
li $n 
\backslash
gets 
\backslash
attrib{W}{rows}$
\end_layout

\begin_layout Plain Layout


\backslash
li $D^{(0)} 
\backslash
gets W$
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
For $k 
\backslash
gets 1 
\backslash
To n $ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li    let $D^{(k)} 
\backslash
gets (d^{(k)}_{ij})$ be a new $n
\backslash
times n$ matrix
\end_layout

\begin_layout Plain Layout


\backslash
li    
\backslash
For $j 
\backslash
gets 1 
\backslash
To n$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li       
\backslash
For $j 
\backslash
gets 1 
\backslash
To n$ 
\backslash
Do
\end_layout

\begin_layout Plain Layout


\backslash
li          $d^{(k)}_{ij} 
\backslash
gets 
\backslash
min(d^{(k-1)}_{ij}, d^{(k-1)}_{ik} + d^{(k-1)}_{kj})$
\end_layout

\begin_layout Plain Layout

    
\backslash
End 
\backslash
End 
\backslash
End
\end_layout

\begin_layout Plain Layout


\backslash
li 
\backslash
Return $D^{(n)}$
\end_layout

\begin_layout Plain Layout


\backslash
end{codebox}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Time complexity
\end_layout

\begin_layout Standard
Floyd-Warshall algorithm runs in 
\begin_inset Formula $\Theta(n^{3})$
\end_inset

 because of the triple nested loop.
\end_layout

\begin_layout Subsection
Longest path problem and other time complexity considerations
\end_layout

\begin_layout Itemize
We have seen that the shortest path problem, in all of its variants, can
 be solved in polynomial time (it is in P) in graphs without negative-weight
 cycles.
 
\end_layout

\begin_layout Itemize
If the graph
\emph on
 has
\emph default
 negative-weight cycles, the shortest path problem becomes NP-complete.
 This means we can still run Bellman-Ford algorithm on such a graph but
 we cannot guarantee it will produce a correct answer if a negative-weight
 cycle is reachable from the source, even if the algorithm can detect them.
\end_layout

\begin_layout Itemize
The 
\emph on
longest path problem
\emph default
 can be reduced to the shortest path problem, by exploiting the duality
 of optimizations (maximizing a positive value is the same as minimizing
 a negative value).
 If the input graph to the longest path problem is 
\begin_inset Formula $G$
\end_inset

, the shortest path on the graph 
\begin_inset Formula $H$
\end_inset

, which is exactly the same as 
\begin_inset Formula $G$
\end_inset

 but with edge weights negated, is the longest path on 
\begin_inset Formula $G$
\end_inset

.
 However, any positive-weight cycle in the original graph 
\begin_inset Formula $G$
\end_inset

 leads to a negative-weight cycle in 
\begin_inset Formula $H$
\end_inset

 and, therefore, solving the shortest path problem for 
\begin_inset Formula $G$
\end_inset

 is also NP-complete.
 
\end_layout

\begin_layout Itemize
If 
\begin_inset Formula $G$
\end_inset

 contains no cycles, then 
\begin_inset Formula $H$
\end_inset

 will have no negative-weight cycles, and we can use any of the algorithms
 we have seen to solve the shortest-path problem.
 Thus the longest path problem is easy on acyclic graphs(including dags).
\end_layout

\begin_layout Subsection
Oher graph algorithms
\end_layout

\begin_layout Subsubsection
Testing bipartitness
\end_layout

\begin_layout Standard
We can use BFS to do so.
 If at the end of BFS there are no intra-layer edges then the graph is bipartite.
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Section
\start_of_appendix
Lists and tables
\end_layout

\begin_layout Subsection
Growth rates of different functions
\end_layout

\begin_layout Standard
The following table summarizes the asymptotical growth rates of the most
 common classes of functions in algorithm analysis.
 They are listed in order from the 
\emph on
slower
\emph default
 to the 
\emph on
quicker
\emph default
 asymptotically growing.
\end_layout

\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="14" columns="4">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Name
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Growth rate
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Function class
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Example
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Constant 
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $c$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Inverse Ackermann
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(\alpha(n))$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Iterated logarithm
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(\log^{*}n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\log^{*}n$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Log-logarithmic
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $ $
\end_inset


\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none

\begin_inset Formula $\Theta(\log\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none
\begin_inset Formula $\log\log n$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Logarithmic
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\log(poly(n))$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\log n$
\end_inset

, 
\begin_inset Formula $\log n^{2}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Polylogaritmic
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(\log^{c}n)$
\end_inset

 with 
\begin_inset Formula $c>1$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $poly(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\log^{2}n$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Fractional power (or Sublinear)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(n^{c})$
\end_inset

 with 
\begin_inset Formula $0<c<1$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $n^{c}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $n^{\frac{2}{3}}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
--- Linear ---
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $n$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Linearitmic
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $n\log n$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Polynomial
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(n^{c})$
\end_inset

 with 
\begin_inset Formula $c>1$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $poly(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $n^{2}$
\end_inset

, 
\begin_inset Formula $n^{3}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Exponential
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(c^{n})$
\end_inset

 with 
\begin_inset Formula $c>1$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $c^{poly(n)}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $10^{n}$
\end_inset

, 
\begin_inset Formula $e^{n}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Factorial
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Theta(n!)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $n!$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $n!$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Double Exponential
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none
\begin_inset Formula $\Theta(c^{2^{poly(n)}})$
\end_inset

 
\family default
\series default
\shape default
\size default
\emph default
\bar default
\noun default
\color inherit
with 
\begin_inset Formula $c>1$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $c^{2^{poly(n)}}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $2^{3^{n}}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
Note that for any polylogaritmic function we can ignore the lower order
 terms when deriving the asymptotic growth rate.
 
\end_layout

\begin_layout Standard
Also note that sometimes we say that linear and linearitmic functions have
 a growth rate that is 
\emph on
polynomial
\emph default
: use your brain to extract the proper meaning of the word polynomial from
 the context!
\end_layout

\begin_layout Subsection
Complexities for basic data structures operations
\end_layout

\begin_layout Standard

\shape smallcaps
n/a
\shape default
 means that the operation in not applicable to the data structure.
\end_layout

\begin_layout Standard

\shape smallcaps
d
\shape default
 means that it depends, look at bottom of each table for explanation.
 
\end_layout

\begin_layout Standard
In addition to these tables check out 
\begin_inset CommandInset href
LatexCommand href
name "http://bigocheatsheet.com/"
target "http://bigocheatsheet.com/"

\end_inset

 for an excellent summary of complexities of basic data structures and algorithm
s.
\end_layout

\begin_layout Subsubsection
Linear data structures
\end_layout

\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="7" columns="6">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Data structure
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Implementation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Access
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Delete
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Peek
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
List (index known)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
array
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
linked list
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Stack
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
array
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
linked lists
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Queue
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
array
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
linked lists
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
Note how the costs for array and linked list operations refer to the case
 when the 
\begin_inset Quotes erd
\end_inset

position
\begin_inset Quotes erd
\end_inset

 is known, that is the index for the arrays and the pointer to an element
 for linked lists.
\end_layout

\begin_layout Subsubsection
Trees
\end_layout

\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="8">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Data structure
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Impl.
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insert
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Delete
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Search
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Build
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Max/Min
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pred./Suc.
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Heap
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
array
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
d
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Priority q.
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
heap
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
d
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
BST
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3-pointers
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(nh)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(h)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Bal.
 BST
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3-pointers
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
Note that min-heap (max-heap) support only min-priority queues (max-priority
 queues); therefore only 
\begin_inset Formula $\min(Q)$
\end_inset

 
\begin_inset Formula $(\max(Q))$
\end_inset

 is supported in 
\begin_inset Formula $O(1)$
\end_inset

 time.
\end_layout

\begin_layout Subsubsection
Disjoint-set data structure
\end_layout

\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="3" columns="5">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Data structure
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Implementation
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Make-Set
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Union
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Find-Set
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Union-Find
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Linked lists
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Omega(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Union-Find
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Trees
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\alpha(n))$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\alpha(n))$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Subsection
Sort, selection and search algorithms complexities
\end_layout

\begin_layout Standard
Complexities of the main sorting and selection algorithms.
\end_layout

\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="7" columns="6">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Algorithm
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Worst Case
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Best Case
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Avg.
 case
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
In place
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Notes
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Insertion sort
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n^{2})$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n^{2})$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Yes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Merge sort
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
No
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Heap sort
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Yes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Quick sort
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n^{2})$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Yes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Quick select
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n^{2})$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Binary search
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(1)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\shape smallcaps
n/a
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
using balanced BSTs
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Subsection
Graph algorithms complexities
\end_layout

\begin_layout Standard
Remember that, in any graph, 
\begin_inset Formula $m=O(n^{2})$
\end_inset


\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Therefore 
\begin_inset Formula $O(\log m)=O(\log n^{2})=O(2\log n)=O(\log n)$
\end_inset


\end_layout

\end_inset

.
 
\end_layout

\begin_layout Standard
\align center
\begin_inset Tabular
<lyxtabular version="3" rows="13" columns="4">
<features rotate="0" tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Algorithm
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Data struct.
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Running time
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Notes
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
BFS
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n+m)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
DFS
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n+m)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Topological Sort
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n+m)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Prim
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
min-heap
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O((n+m)\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none
\begin_inset Formula $O(m+n\log n)$
\end_inset

 with Fibonacci heap
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Kruskal
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
union-find
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(m\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Bellman-Ford
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
min-heap
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(nm)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Dijkstra
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
array
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n^{2}+m)=O(n^{2})$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Dijkstra
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
min-heap
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O((n+m)\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\noun off
\color none
\begin_inset Formula $O(m+n\log n)$
\end_inset

 with Fibonacci heap
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Iterated Dijkstra
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
array
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n^{3}+nm)=O(n^{3})$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Iterated Dijkstra
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
min-heap
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(nm\log n)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Iterated B-F
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
min-heap
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n^{2}m)$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Floyd-Warshall
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
array
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $O(n^{3})$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
Note also how in connected graphs we have 
\begin_inset Formula $m\geq n-1$
\end_inset

 and therefore 
\begin_inset Formula $O((n+m)\log n)=O(m\log n)$
\end_inset

.
\end_layout

\end_body
\end_document