\documentclass[11pt,fleqn]{article}
\usepackage{latexsym,epsf,epsfig}
\usepackage{amsmath,amsthm}
\begin{document}
\newcommand{\mbf}[1]{\mbox{{\bfseries #1}}}
\newcommand{\N}{\mbf{N}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\def\floor#1{\lfloor #1 \rfloor}
\section*{CS 70 homework 3 solutions}
Your full name: PUT YOUR NAME HERE
\newline
Your login name: PUT YOUR LOGIN NAME HERE
\newline
Homework 2
\newline
Your section number: PUT YOUR SECTION NUMBER HERE
\newline
Your list of partners: LIST YOUR PARTNERS HERE
\newline
\begin{enumerate}
\item
The Fibonacci numbers are defined as follows:
\begin{eqnarray*}
F_0 &=& 0 \\
F_1 &=& 1 \\
F_n &=& F_{n-2} + F_{n-1} \mbox{ for } n>1
\end{eqnarray*}
\begin{enumerate}
\item List the first ten Fibonacci numbers ($F_0$ through $F_9$).
YOUR ANSWER GOES HERE.
\item Consider the following Scheme procedure that, given {n}, returns $F_n$.
\begin{verbatim}
(define (fib n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2)))) ) )
\end{verbatim}
Let $T_n$ be the number of addition operations required
in the computation of {\tt (fib n)}. List the values $T_0$ through $T_9$.
YOUR ANSWER GOES HERE.
\item State and prove a relationship between the $T$ numbers and the $F$
numbers.
YOUR ANSWER GOES HERE.
\item Prove that $F_{n+1} F_{n-1} - F_n^2 = (-1)^n.$
YOUR ANSWER GOES HERE.
\end{enumerate}
\newpage
\item
Chocolate often comes in rectangular bars marked off into
smaller squares. It is easy to break a larger rectangle into
two smaller rectangles along any of the horizontal or vertical
lines between the squares.
Suppose I have a bar containing $k$ squares
and wish to break it down into its individual squares.
Prove that {\em no matter which way I break it}, it will take
exactly $k-1$ breaks to do this.
YOUR ANSWER GOES HERE.
\newpage
\item
A CS 70 student, attempting to write a guessing game,
implements the following pseudocode.
\begin{tabbing}
xxxx\=xxxx\= \kill
print "Think of an integer between 1 and 100 (inclusive), and I will guess it.";\\
$lowestPossible$ = 1;\\
$highestPossible$ = 100;\\
while (we're not done)\\
\>$mid = \floor{(lowestPossible+highestPossible)/2}$;\\
\>print "Is it ", $mid$, "?";\\
\>if user says yes, we're done\\
\>otherwise\\
\>\>print "Is it bigger than ", $mid$, "?";\\
\>\>if user says yes, set $lowestPossible$ to $mid$\\
\>\>otherwise set $highestPossible$ to $mid$;
\end{tabbing}
\begin{enumerate}
\item
The CS 70 student is intending to maintain the following loop invariant:
the number to be guessed is somewhere in the interval $[lowestPossible, highestPossible]$.
Is this invariant maintained in each iteration of the loop?
Explain why or why not.
YOUR ANSWER GOES HERE.
\item
List all numbers between 1 and 100, inclusive, that the algorithm
fails to guess, and describe what happens for each.
YOUR ANSWER GOES HERE.
\item
Suppose we make two changes in the algorithm: first, initialize $highestPossible$ to 101;
second, update $lowestPossible$ to $mid+1$ if the user's value is bigger than $mid$.
The modified code maintains a loop invariant that is stronger
than the invariant described in part a.
Describe the loop invariant in the modified code, and briefly explain your answer.
YOUR ANSWER GOES HERE.
\item
Using your updated invariant,
give an induction proof that the modified algorithm works correctly.
YOUR ANSWER GOES HERE.
\end{enumerate}
\newpage
\item
Given a set of $N$ numeric values, we can find the maximum element using $N-1$ comparisons
and then find the minimum element using $N-2$ more comparisons (skipping the maximum element),
for a total of $2N-3$ comparisons.
Consider the following algorithm:
\begin{tabbing}
xxxx\=xxxx\= \kill
if there are two elements in the set, then \\
\>with one comparison determine the larger and the smaller,\\
\>\>and store them in variables $larger$ and $smaller$;\\
\>return the pair $[larger, smaller]$;\\
otherwise\\
\>divide the set of elements in half;\\
\>make a recursive call to find the largest and smallest elements in the first half;\\
\>make a recursive call to find the largest and smallest elements in the second half;\\
\>set $larger$ to the larger of the two largest elements (found with one comparison);\\
\>set $smaller$ is the smaller of the two smallest elements (found with one comparison);\\
\>return the pair $[maximum, minimum]$;\\
\end{tabbing}
\begin{enumerate}
\item
Prove that, for $N$ a power of 2, that the above algorithm always requires
less than $3N/2$ comparisons (ignoring whatever comparisons are necessary
to divide the set in half).
YOUR ANSWER GOES HERE.
\item
Identify the reason that this algorithm works faster than the straightforward method
outlined above.
YOUR ANSWER GOES HERE.
\end{enumerate}
\newpage
\item
A {\it rooted binary tree} either is empty, or consists of a {\it root}
and zero, one, or two disjoint {\it subtrees} (which are also rooted binary trees).
A {\it leaf} is a rooted binary tree with a root and no subtrees.
\begin{enumerate}
\item
Prove that, in a rooted binary tree with $L$ leaves,
that \[\sum_{k=1}^L 2^{-d(k)} \leq 1\]
where $d(k)$ is the depth of leaf $k$.
The depth of the root of a tree is 0, and the depth of any other node
is 1 plus the depth of its parent.
YOUR ANSWER GOES HERE.
\item
Completely describe all trees for which \[\sum_{k=1}^L 2^{-d(k)} = 1\]
and prove your claim.
This will involve two proofs, one that verifies that the trees you describe
satisfy the equality, and one that shows that for all other trees,
the given sum is less than 1.
YOUR ANSWER GOES HERE.
\end{enumerate}
\end{enumerate}
\end{document}