\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Spring 2004\\
\rm
Homework 4b\\
Due on 2/17/04 (beginning of class)\\
\end{center}
\begin{enumerate}
\item \textbf{[75 Points] Implementing B-Trees!}
In this assignment you will implement B-Trees.  In particular, your
implementation should assume that $t=2$.  Your code should have a
\texttt{Node} element similar to the one suggested in the
lecture notes.  Your program should support the operations
\texttt{insert(x)}, which inserts the integer \texttt{x}  into the tree,
and \texttt{find(x)} which returns a boolean indicating whether or not
\texttt{x}
is in the tree.  For insertion, use the one-phase method described in class
(in which insertion is done in a single pass down the tree).  In addition,
your program should have a method called
\texttt{height()} which returns the height of the tree.  (A tree with a
single node has height 0.)
Please do this programming exercise without looking at the book.
For one thing, the book's pseudocode isn't particularly clean or clear.
In addition, this is the first chance you'll have had to write your own
code given high-level ideas presented in class---I suggest you start by
writing your own pseudo-code. If you're careful at the design stage, you
might be able to get away with very little debugging.

You should turn in a copy of your code and a sample run of a test program
which inserts the
even numbers from 0 to 20 (in order) into the tree.
Next, invoke the \texttt{height()} method and print the height of your
tree.
Then, the test program tests to see if
each number from 0 to 20 (odd and even) is in the tree and prints ``true''
or ``false'' for
each such query.

You have several options when turning in a sample run of your program:
\begin{enumerate}
\item Use script (do \texttt{man script} to learn more). 
Do not create such a script inside an emacs buffer because it 
won't print correctly! In fact, I don't recommend {\tt script}
because there are a variety of situations in which it won't print
correctly.
\item Run your program in an emacs {\tt shell} buffer interactively. Cut and paste
the parts of the interaction that show your program running into another 
buffer, save as a text file, and then print this.
\item Once you're sure your program works the way you'd like,
you could use redirection to generate text files.
\end{enumerate}



\end{enumerate}
\end{document}
