\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{color}

\addtolength{\textwidth}{2in}
\addtolength{\textheight}{2in}
\addtolength{\topmargin}{-1in}
\addtolength{\evensidemargin}{-1in}
\addtolength{\oddsidemargin}{-1in}

\begin{document}

\section{CSC 528 Assignment \#3}

\begin{enumerate}
\item
Prove that 
\[
\nu x\  =\  x - \left\lfloor \frac{x}{2} \right\rfloor - \left\lfloor \frac{x}{4} \right\rfloor
- \left\lfloor \frac{x}{8} \right\rfloor - \cdots
\]
\item
Determine the structure of an infinite binary tree $\mathcal{T}$ with the following property:
  the first $n$ nodes of $\mathcal{T}$ are a binary tree that maximizes the number of leaves at the
  lowest level in the tree (over all trees with $n$ nodes).
The tree should have some similarities to the infinite sideways heap.
[It's not required, but you may want to think about how hard it would be
to navigate in this tree.]
\item
In his lecture, Knuth describes an application of the \textsf{nca} problem to the ``minimum in range problem"
  (or something like that).
Illustrate the binary search tree construction with the input sequence 27182818284 
  (another well-known sequence).
Now do exercise 150 in 7.1.3.
\item
Prove the following equation from Knuth's lecture, where $i \le j$:
\[
\max\{ \rho(i), \rho(i{+}1), \ldots, \rho(j) \} = \lambda(j\ \& \ {-}i).
\]
If you are stuck, see exercise 138 in 7.1.3.
\end{enumerate}


\end{document}