\documentclass[oneside,12pt]{article}   
\usepackage{latex-macros/course}

%\showsolutions             
%\hidesolutions             

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% new macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ms}[1]{\mathop{\text{#1}}}
\providecommand{\leaves}{\ms{leaves}}
\providecommand{\nodes}{\ms{nodes}}
\providecommand{\numnodes}{\ms{numnodes}}
\providecommand{\dep}{\ms{depth}}
\providecommand{\root}{\ms{root}}
\providecommand{\makeb}{\ms{makeboth}}
\newcommand{\makeleft}{\ms{makeleft}}
\newcommand{\makeright}{\ms{makeright}}
\newcommand{\FBT}{\text{FBT}}
\newcommand{\external}{\textit{GView}}
\newcommand{\internal}{\textit{SView}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% exampreamble %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand{\exampreamble}{
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llll}
  Ashish    & Carole   & Christos & Eric \\
  George    & Jack     & Nick     & Tina   
  \end{tabular}
  \end{center}
  \begin{itemize}

  \item This quiz is \textbf{closed book}.  There is an Appendix that
  repeats some key definitions.

  \item 
  There are four (4) problems totaling 100 points.  Problems are
  labeled with their point values.
  \item 
  Put your name on the top of {\bf every} page -- \emph{these
  pages may be separated for grading}.
  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.
  \item 
  You may assume any of the results presented in class or in the
  lecture notes.
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
  \item 
  GOOD LUCK!
  \end{itemize}}




\begin{document} 
\quiz{2}                      



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Graphs %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[20]
\begin{problemparts}

\problempart[3] 
Prove that if every simple cycle in a simple graph is
2-colorable, then the whole graph is 2-colorable.  You may cite
without proof any of the results from class, Course Notes and 
Problem Sets.  

\solution{
We know from Problem Set~4 that a graph is 2-colorable iff all of its 
simple cycles are of even length.  In particular, a simple cycle is
2-colorable iff its length is even.  So if all cycles in a graph are
2-colorable, they are in fact of even length, and the whole graph is
2-colorable.}

\instatements{\vfill}

\problempart[7]  
Draw a small counter-example to the following false theorem
\begin{falsethm*}
If every simple cycle in a simple graph is 3-colorable, then the whole 
graph is 3-colorable.
\end{falsethm*}

\solution{
A simple cycle of odd length is obviously 3-colorable, and one of even
length is 2-colorable.  In particular, \emph{all} graphs that are 
simple cycles are 3-colorable.  Hence any graph that is not 3-colorable is
a counter-example, \eg $K_4$, the \emph{complete} graph on four nodes.}

\instatements{\vfill\pagebreak}

\problempart[10] We know that a graph containing $K_4$ (the complete
subgraph on 4 vertices) is not 3-colorable.

\begin{enumerate}
\item Give an example of a graph that {\em does not contain} $K_4$, but
is still not 3-colorable.
\item {\em Briefly}, but carefully, explain why it is not 3-colorable.
\end{enumerate}

\solution{
Such a graph is shown in Figure~\ref{4colg}.

\begin{figure}[htb]
\begin{center}
\input{figures/4colgr.latex}
\end{center}
\caption{Graph requiring 4 colors.}
\label{4colg}
\end{figure}

The outer pentagon is an odd cycle and requires at least 3 colors.
The inner point is connected to every point on the pentagon, so it needs 
a 4th color.

In fact any wheel with an odd outer cycle requires 4 colors.
}

\instatements{\vfill\pagebreak}

\end{problemparts}
\end{problem}



\instatements{\newpage}
        

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% State machines %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem}[26]
The Massachusetts Turnpike Authority is concerned about the integrity of
the new
\href{http://theory.lcs.mit.edu/classes/6.042/spring02/BrdgCrne-14.htm}
{Leonard Zakim bridge}.  Their consulting architect has warned that the
bridge may collapse if more than 500 cars are on it at the same time.  The
Authority has also been warned by their traffic consultants that the rate
of accidents from cars speeding across bridges has been increasing.

Both to lighten traffic and to discourage speeding, the Authority has
decided to make the bridge \emph{one-way} and to put tolls at \emph{both}
ends of the bride (don't laugh, this is Massachusetts).  A car pays \$3.00
at the entry toll booth and another \$3.00 at the exit toll booth.  To be
sure that there are never too many cars on the bridge, the Authority will
let a car onto the bridge only if \emph{the difference between the amount
of money currently at the entry toll booth minus the amount at the exit
toll booth is strictly less than~\$1500}.

The Authority has asked their engineering consultants to verify that this
policy will keep the number of cars from exceeding 500.  The consultants
have decided to model this scenario with a state machine whose states are
triples of natural numbers, $(A,B,C)$, where
\begin{itemize}
\item $A \in \naturals$ is an amount of money at the entry booth,
\item $B \in \naturals $ is an amount of money at the exit booth, and
\item $C \in \naturals$ is a number of cars on the bridge.
\end{itemize}
Since the toll booth collectors may need to start off with some amount of
money in order to make change, and there may also be some number of
``official'' cars already on the bridge when it is opened to the public,
the consultants must be ready to analyze the system started at \emph{any}
state, not necessarily with a start state $(0,0,0)$.

\begin{problemparts}
\problempart[4] Give a mathematical description of the Authority's rules
for letting cars on and off the bridge by specifying a transition relation
between states of the form $(A,B,C)$ above.

\solution{
State $(A,B,C)$ goes to state
\begin{enumerate}
\item[(i)]
$(A+3,B,C+1)$, providing that $A-B<1500$.  This transition models
the case where a car enters the bridge.

\item[(ii)]
$(A,B+3,C-1)$, providing that $C\geq 1$.  This transition models
the case where a car leaves the bridge.
\end{enumerate} 

We could also have
\begin{enumerate}
\item[(iii)]
$(A+3,B+3,C)$, if $A-B<1,500$ and $C\geq 1$,
\end{enumerate}
to model the case where a car enters the bridge at the same time when
another car leaves the bridge.  But it is easy to see that this special
case can be modeled with two transitions of types~(i) and ~(ii).
}
 
\instatements{\vfill\pagebreak}

\problempart[8]
Characterize each of the following derived variables
\[
\renewcommand{\arraystretch}{2}
\begin{array}{|c|c|} \hline
%A  		  & \qquad \\\hline % SI
A+B 		  & \qquad\qquad\\\hline % SI
A-B 		  & \\\hline % N
1501 A-B	  & \\\hline % N
3C-A            & \\\hline % ?
C-\dfrac{A}{3} - \dfrac{B}{3} &   \\\hline
C-\dfrac{A}{3} + \dfrac{B}{3} &   \\\hline
\end{array}
\]
as one of the following
\begin{center}
\begin{tabular}{|ll|} \hline
constant              & C  \\  
strictly increasing   & SI \\
strictly decreasing   & SD \\
weakly increasing but not constant & WI \\
weakly decreasing but not constant & WD \\
none of the above     & N  \\\hline
\end{tabular}
\end{center}
by entering the corresponding code next to the variable.


\solution{
In every transition, at least one of $A$ and $B$ increases. So their
sum is strictly increasing, but each of $A-B$ and $1501A-B$ can
fluctuate arbitrarily.  

The differences $3C-A$ and $C-A/3-B/3$ don't change under transitions
of type~(i), but decrease under transitions of type~(ii); so they are
weakly decreasing. On the other hand, $C$ and $A/3-B/3$ simultaneously
increase (when a car enters the bridge) or decrease (on exit) by~1,
which makes their difference (last row) a constant. 

The completed table follows.
\[
\renewcommand{\arraystretch}{2}
\begin{array}{|c|c|} \hline
%A  		  & \qquad \\\hline % SI
A+B 		  & SI\\\hline % SI
A-B 		  & N \\\hline % N
1501 A-B	  & N \\\hline % N
3C-A            & WD \\\hline % ?
C-\dfrac{A}{3} - \dfrac{B}{3} & WD  \\\hline
C-\dfrac{A}{3} + \dfrac{B}{3} & C  \\\hline
\end{array}
\]}


\instatements{\newpage}


\problempart[14] The engineering consultants plan to use the Invariant
Method to prove that the bridge will never collapse under the assumption
that the bridge opens to the public with no cars on it and no money at the
toll booths.  That is, the start state is $(0,0,0)$.

They realize that in such a proof, they musn't confuse the following
properties of predicates, $P$, on states:
\begin{itemize}

\item[R] $P$ happens to be true in all the states \emph{reachable} from the
start state $(0,0,0)$.

\item[I] $P$ is \emph{invariant}, that is, if $P((A,B,C))$ is true, and
there is a transition from $(A,B,C)$ to $(A',B',C')$, then $P((A',B',C'))$
is true.

\item[G] $P$ guarantees the bridge won't collapse, that is, if
$P((A,B,C))$ is true, and there is a sequence of zero or more transitions
from $(A,B,C)$ to $(A',B',C')$, then $C' \leq 500$.
\end{itemize}

For example, the predicate $[A-B \leq 1500]$ has property R, but not
property I or G because there is an (unreachable) state, namely,
$(1499,0,500)$ in which $1499-0 \leq 1500$ but this state has a
transition to $(1502,0,501)$ where the property fails and the bridge
collapses. 

Indicate for each of the following predicates, exactly which of properties
R,I, and G it has.

\begin{enumerate}

\item  \label{item1}
$C \leq 500$ \hfill\brule{1in} 
\solution{\textbf{R}.

\textbf{R}: by~\ref{item6}.\ below;
\textbf{not I, G}: Since $(0,0,400) \to (303,0,501)$.
}
\instatements{\vspace{0.3in}}


%\item \label{item2}
% $A-B\leq 1502$.\hfill\brule{1in} \vspace{0.3in}
%
%\solution{RI, not G.}

\item \label{item3}
$A \geq B$.\hfill\brule{1in}
\solution{\textbf{R}.

\textbf{R}: by~\ref{item6}.\ below; 
\textbf{not I, G}: Because $(0,0,502) \to (0,3,501)$.}
\instatements{\vspace{0.3in}}

\item \label{item4}
$A - B= 3 C$.\hfill\brule{1in}

\solution{\textbf{IR}.

\textbf{I}: A transition can either increase both sides of
the equality by~3 (type~(i)), or decrease both sides
by~3 (type(ii)); in both cases, the transition preserves the
equality. \textbf{R}: Since it is I and it is true at the start
state. \textbf{not G}: Provides no bounds on~$C$, \eg $(1503,0,501)$
satisfies the property.}
\instatements{\vspace{0.3in}}

\item \label{item5}
$A-B < 3 C$.\hfill\brule{1in}

\solution{\textbf{I}.

\textbf{I}: As in~\ref{item4}., a transition either increases or
decreases both sides by~3, so that the inequality is
preserved. 
\textbf{not R}: Since  it is clearly  false at the start state, which
is reachable. 
\textbf{not G}: Provides no bounds on~$C$.  
}
\instatements{\vspace{0.3in}}

\item \label{item6}
$A-B= 3C      \;\;\land\;\;  A-B \leq 1500$.\hfill\brule{1in}
\solution{\textbf{RIG}.

\textbf{I}: Suppose the property holds in some state, that is, $A-B=3C$
and $A-B\leq 1500$ and a transition takes us to $(A',B',C')$.  Then
$A'-B'=3C'$, as well (same argument as in~\ref{item4}.).  To see why
$A'-B'\leq 1500$ is also true, check the two cases: if $A-B=1500$, then no
more cars can enter (a type~(i) transition is not allowed), hence the only
possible next step is for a car to exit (which decreases the difference
and preserves the inequality); if $A-B<1500$, then $A-B\leq 1497$ (since
$A-B=3C$, so the difference is a multiple of~3), so no transition can
raise the difference above~1500.  In both cases, $A'-B'\leq 1500$.

\textbf{R}: Because it is I and true at the start state.

\textbf{G}: Because it is I and implies $C\leq 500$.}
\instatements{\vspace{0.3in}}

\item \label{item7}
$A-B \leq 3 C     \;\;\land\;\;  C \leq 500$.\hfill\brule{1in}
\solution{\textbf{R}.

\textbf{R}:  by~\ref{item6}.\ above; 
\textbf{not I,G}: Since $(0,0,400) \to (303,0,501)$.}
\instatements{\vspace{0.3in}}

\end{enumerate}

\instatements{\vfill\pagebreak}

\end{problemparts}
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Asymptotics %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[24]

\newcommand{\asymptotics}{
\renewcommand{\arraystretch}{2}
\begin{array}{|cc|c|c|c|c|c|c|}
\hline
f(n) & g(n) & f=O(g) & f=o(g) & g=O(f) & g=o(f) & f\sim g 
\\\hline\hline
%% \sim versus \theta
6n+6 & n 
& \y & \n & \y & \n &  \n \\\hline
%% poly versus log
n^4\ln n & n^{4.01} 
& \y & \y & \n & \n &  \n \\\hline
%% Harmonic is \sim lnn (not just \theta)
2\ln(n^3)+2 & \sum_{i=1}^{n} 6/i 
& \y & \n & \y & \n &  \y \\\hline
%% Stirling and O()
n! & \bigl(\dfrac{n}{e}\bigr)^n 
& \n & \n & \y & \y &  \n \\\hline
\iffalse
%% trick
8^{\ln n}  & n^3  
& \y & \y & \y & \y &  \y \\\hline
%% sums of powers
\sum_{i=1}^{n} i^3 &  \sum_{i=1}^{n} i
& \n & \n & \y & \y &  \n \\\hline
\fi
%% integral method
\sum_{i=n}^\infty {1/{i^2}} & 1/2
& \y & \y & \n & \n &  \n \\\hline
%% trick: constant versus polynomial
\sum_{i=1}^{10} {i^2} & n^3 
& \y & \y & \n & \n &  \n \\\hline
\end{array}}

Indicate which of the following holds for each pair of functions
$f(n)$ and $g(n)$ in the table below.  Note that $\ln$ denotes the
natural logarithm.
\begin{equation*}
\newcommand{\y}{}
\newcommand{\n}{}
\asymptotics
\end{equation*}

\solution{
The first row follows easily by the definitions of the asymptotic
notations. 

The second row is really a comparison between $\ln n$ and 
$n^{0.01}$, which is a logarithmic versus polynomial comparison: every  
logarithmic is little-oh of any polynomial. 

The third row is a comparison of $6\ln n$ versus $6 H_n$; but we know
that $H_n\sim\ln n$, and hence $6\ln n\sim 6H_n$, as well. 

For the fourth row, note that 
\[
\frac{(n/e)^n}{n!} \leq 
\frac{1}{\sqrt{2\pi n} e^{1/(12n+1)}} \leq
\frac{1}{\sqrt{2\pi n}} \to 0,
\]
so $(n/e)^n = o(n!)$.

In the fifth row: for every $n\geq 2$, $f(n)$ is bounded above by
$$
\int_{n-1}^\infty \frac{1}{i^2}di = 
\frac{-1}{i} \Bigr|_{n-1}^\infty = 
0 - \frac{-1}{n-1} =
\frac{1}{n-1}.
$$
So, as $n\to\infty$, the value of $f$ tends to~0. This makes $f$
little-oh of any constant. In particular, it is $o(1/2)$.


Finally, $f$ of the last row is clearly a constant. Hence, it
is~$o(n^3)$.  

The complete table follows.
	
\newcommand{\y}{+}
\newcommand{\n}{-}
\begin{equation*}
\asymptotics
\end{equation*}
}

\instatements{\newpage}

\end{problem}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Structural induction %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[30]
In class and in the Course Notes we have introduced the notion of a
\emph{full binary tree} and we have also defined the functions
$\numnodes(\cdot)$ and $\dep(\cdot)$ that return the \emph{number of
nodes} and the \emph{depth} of such a tree, respectively. (You can
look up the exact definitions in the Appendix.)
 
Use \emph{structural induction} to prove that in a full binary
tree~$t$, 
\[
\numnodes(t) + 1 \leq 2^{\dep(t)+1}.
\]
You may \emph{not} cite the result for binary trees given in lecture
slides, unless you prove it. 
\end{problem}

\solution{
For the base case, we have that $t$ is a single node. Hence, by the
definition of the two functions, we know
\[
\numnodes(t) = 1  \qquad\text{and}\qquad \dep(t) = 0
\]
which implies 
\[
\numnodes(t) + 1 = 1 + 1 = 2 = 2^1 = 2^{0+1} = 2^{\dep(t)+1}.
\]

For the inductive step, assume $t=\makeb(t_1,t_2)$ for some full
binary trees $t_1$ and $t_2$ for which  
\begin{align}
\label{eq:ind-1}
\numnodes(t_1) + 1 &\leq 2^{\dep(t_1)+1},
\\
\label{eq:ind-2}
\numnodes(t_2) + 1 &\leq 2^{\dep(t_2)+1}.
\end{align}
To prove that $\;\numnodes(t) + 1 \leq 2^{\dep(t)+1}$, we let
$$
d=\max\set{\dep(t_1),\dep(t_2)}
$$ 
and we calculate:
\begin{align*}
\numnodes(t) + 1
&= 
\bigl( 1 + \numnodes(t_1) + \numnodes(t_2) \bigr) + 1
&&\text{(def.\ of $\numnodes(\cdot)$)}
\\
&= 
\bigl( \numnodes(t_1) + 1 \bigr) 
+ 
\bigl( \numnodes(t_2) + 1 \bigr) 
&&
\\
&\leq
2^{\dep(t_1)+1} + 2^{\dep(t_2)+1}
&&\text{(eqs.~\eqref{eq:ind-1} and~\eqref{eq:ind-2})}
\\
&\leq
2^{d+1} + 2^{d+1}
&&\text{(def.\ of $d$)}
\\
&=
2\cdot2^{d+1}
&&
\\
&=
2^{(d+1)+1}
\\
&=
2^{\dep(t)+1},
&&\text{(def.\ of $\dep(\cdot)$)}
\end{align*}
which concludes the induction.
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Appendix %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\instatements{
\newpage
\section*{Appendix}
\appendix 

\section{Graphs}

\begin{definition*}
A \emph{simple graph} is a pair of sets $G=(V,E)$ such that $E$ is a 
set of two-element subsets of~$V$. Elements of $V$ are called
\emph{vertices} or \emph{nodes}; elements of $E$ are called
\emph{edges}. 
\end{definition*}

(So, a simple graph is an undirected graph with no self-loops and no
multiple edges.)

\begin{definition*}
A simple graph is called \emph{complete} iff for every two distinct
vertices $u,v\in E$, the edge $\set{u,v}$ is in~$E$.
\end{definition*}

\begin{definition*}
A \emph{path} in a simple graph $G=(V,E)$ is any sequence 
$$
\set{v_0,v_1}, \set{v_1,v_2}, \dots, \set{v_{l-1},v_l}
$$
of $l\geq 1$ elements of $E$; we say this is a path of length $l$ from
$v_0$ to $v_l$. The path is \emph{simple} if $v_0,v_1,\dots,v_l$ are
distinct. The path is a \emph{simple cycle} if $v_0,v_1,\dots,v_{l-1}$
are distinct and $v_0=v_l$. 
\end{definition*}

\begin{definition*}
A simple graph $G=(V,E)$ is \emph{connected} iff for every pair of
distinct vertices $u,v\in V$ there is a path from $u$ to $v$ in~$G$.
\end{definition*}

\begin{definition*}
For any $k\geq 2$, a \emph{$k$-coloring} of a simple graph $G=(V,E)$
is mapping from $V$ to a set of $k$ colors such that no two adjacent
vertices are mapped to the same color. A simple graph is said to be
\emph{$k$-colorable} iff there is a $k$-coloring for that graph. 
\end{definition*}

\section{Full Binary Trees} 

\begin{definition*}
The set, \FBT, of \emph{Full Binary Trees} is defined recursively as
follows: 
\begin{enumerate}
\item\label{rt} 
A single node, $r$, is in \FBT.
\item \label{mb} 
If $t_1$, $t_2$ are in $\FBT$, then $\makeb(t_1,t_2)$ is also
in~$\FBT$.  
\end{enumerate}
\end{definition*}

In this definition, $\makeb(t_1,t_2)$ returns the structure formed from
$t_1$, $t_2$ and a single new node, $n$, with an arrow labeled
``left'' from $n$ to $t_1$ and another arrow labeled ``right'' from
$n$ to $t_2$, as shown in Figure~\ref{fig:btree}. 
Figure~\ref{fig:fbtree} shows an example of a full binary tree. 

\begin{figure}[ht]
\begin{center}
\input{figures/makeboth.latex}
\end{center}
\caption{The structure returned by $\makeb(t_1,t_2)$, where $t_1$,
$t_2$ are full binary trees.}
\label{fig:btree}
\end{figure}


\begin{figure}[ht]
\begin{center}
\input{figures/fbtree.pic}
\end{center}
\caption{A full binary tree.}
\label{fig:fbtree}
\end{figure}

\begin{definition*}
The \emph{number of nodes} of a tree $t\in\FBT$ is defined recursively
as follows: 
\begin{itemize}
\item If $t$ is a single node, then $\numnodes(t)\eqdef 1$.
\item If $t$ is $\makeb(t_1,t_2)$ for some $t_1,t_2\in\FBT$, then
$$
\numnodes(t) \eqdef 1 + \numnodes(t_1) + \numnodes(t_2).
$$
\end{itemize}
\end{definition*}
For example, the number of nodes of the tree in
Figure~\ref{fig:fbtree} is~13. 

\begin{definition*}
The \emph{depth} of a tree $t\in\FBT$ is defined recursively as
follows: 
\begin{itemize}
\item If $t$ is a single node, then $\dep(t)\eqdef 0$.
\item If $t$ is $\makeb(t_1,t_2)$ for some $t_1,t_2\in\FBT$, then 
$$
\dep(t) \eqdef 1+ \max\set{\dep(t_1),\dep(t_2)}.
$$
\end{itemize}
\end{definition*}
For example, the depth of the tree in Figure~\ref{fig:fbtree} is~4.  


\section{Asymptotic Notation}

\begin{definition*}
For functions $f,g:\reals\to\reals$, we say $f$ is
\emph{asymptotically equal} to $g$, in symbols
\[
f(x) \sim g(x),
\]
iff
\[
\lim_{x \rightarrow \infty} f(x)/g(x) = 1.
\]
\end{definition*}

\begin{definition*}
For functions $f,g: \reals \to \reals$, we say $f$ is \emph{asymptotically
smaller} than $g$, in symbols
\[
f(x) = o(g(x)),
\]
iff
\[
\lim_{x \rightarrow \infty} f(x)/g(x) = 0.
\]
\end{definition*}

\begin{definition*}[Using Limits]
Given functions $f, g : \reals \mapsto \reals$, with $g$ nonnegative, we
say that\footnote{$\limsup_{x \rightarrow \infty} h(x) \eqdef \lim_{x
\rightarrow \infty} \text{lub}_{y \geq x} h(y).$}
\[
f = O(g)
\]
iff
\[
\limsup_{x \rightarrow \infty} \abs{f(x)}/g(x) < \infty.
\]
\end{definition*}

\begin{definition*}[Standard]
Given functions $f, g : \reals \mapsto \reals$, we say that
\[
f = O(g)
\]
iff there exists a constant $c \geq 0$ and an $x_0$ such that for all $x \geq
x_0$, $\abs{f(x)} \leq c g(x)$.
\end{definition*}

\begin{definition*}
\[
f = \Theta(g) 
\quad\text{iff}\quad  
f=O(g) \land g=O(f).
\]
\end{definition*}

\begin{lemma*}[Stirling's Formula]
\[
n! \sim \left(\frac{n}{e}\right)^n \sqrt{2 \pi n},
\]
\end{lemma*}

}



\end{document}                            
