notation.tex

\chapter*{Common Notations}
\addcontentsline{toc}{chapter}{Common Notations}

\newlength{\secondcol}
\setlength{\secondcol}{\textwidth}
\addtolength{\secondcol}{1.3in}

\begin{tabular}{p{1.2in}@{\hspace{.1in}}p{\secondcol}}
$\log x$ & The logarithm (base 2) of $x$ \\
$\lg x$ & The logarithm (in some unspecified constant base) of $x$ \\
$\ln x$ & The natural logarithm of $x$ \\[2ex]

$|S|$ & The size of the set $S$ \\
$S_1\cup S_2$ & The union of sets $S_1$ and $S_2$ \\
$S_1\cap S_2$ & The intersection of sets $S_1$ and $S_2$ \\[2ex]

$A,B$ & The sequence obtained by concatenating the sequences $A$ and $B$\\[2ex]

$\Pr\{E\}$ & The probability of event $E$ \\
$\Pr\{E_1\mid E_2\}$ & The probability of event  $E_1$ given $E_2$ \\
$\E[X]$ & The expected value of the random variable $X$ \\[2ex]

$H(D)$ & The entropy of the distribution $D$ \\
$H(s_1,\ldots,s_n)$ & The empirical entropy of the sequence $s_1,\ldots,s_n$\\[2ex]

$A(q,S)$ & The solution of a query $q$ on the set $S$ \\
$A(q,S_1)\Box A(q,S_2)$ & The solution of query $q$ on $S_1\cup S_2$ \\[2ex]

$T(v)$ & The subtree of tree $T$ rooted at node $v$ \\[2ex]

$s_1\circ s_2$ & The concatenation of strings $s_1$ and $s_2$ \\[2ex]
\end{tabular}