\documentstyle[12pt,macpsfig,amssymb]{article}
\input{macros-course}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}
 
\setcounter{page}{0}

\begin{document}

\handout{pq1}{Practice Quiz 1}{October 22, 1997}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%DISCLAYMER
\begin{large}
This practice quiz contains problems from quizes of past semesters.  
There is some new material covered this semester that is
not covered in this practice quiz.  
Also, expect the actual quiz to be much shorter (7 to 10 problems).
\end{large}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 1
\problem

Use induction to prove that
 \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
 whenever $n$ is a natural number.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
\problem 

Why can't you find an integer $x$ for which
\[384\cdot x = 1 \pmod{566}?\]



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 3
\problem
Prove the set identity

\begin{math}
((A-B) \cup (B-A))^{c} = (A^{c} \cup B) \cap (A \cup B^{c})
\end{math}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 4
\problem 

Use the following tables to describe the properties of the
various functions.  Write yes or no in each box.  Don't
give proofs (it'd be too hard to squeeze them into the boxes).  
{\bf Pay careful attention} to the specified domains and ranges.

\begin{itemize}
\item $f:\naturals \rightarrow \naturals,\
f(x)=5x$.
\item   $g: \reals^+ \rightarrow \naturals,\ g(x)=\lfloor x \rfloor$.
\item $h: \reals \rightarrow \reals^{+},\ h(x)=e^x$.   
\end{itemize}
Give an inverse if one exists (under the given domain and range).

\smallskip
\begin{tabular}{l|c|c|c|c|}
function & injective & surjective & inverse\\
\hline
$f(x)=5x$ &           &           &\\
\hline
$g(x) = \lfloor x \rfloor$ & & &\\
\hline
$h(x)=e^x$ & & & \\
\hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem 

Consider the following algorithm, which takes natural numbers
$a$ and $b$, and returns an ordered pair of natural numbers.
\begin{tabbing}
else \= else \= else \= else \=\kill
Algorithm Div$(a,b)$\\
\\
if $(a<b)$\\
\> return $(0,a)$\\
else\\
\> $(q,r) \leftarrow $Div$(a-b,b)$\\
\> return $(q+1,r)$\\
\end{tabbing}

\begin{problemparts}
\problempart Prove Div terminates in at most $a$ steps.

\problempart
Prove that Div returns the quotient and remainder of $a$ on
division by $b$.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 6
\problem 

David is located at position $(1,0)$ on the two-dimensional
$(\naturals \times \naturals)$ $x$-$y$ plane.  His house is located at
the origin.  David wants to go home.  But it is windy, and each time David
takes a one-unit step east or west, he also gets blown a one-unit step
north or south (he can pick which).

\begin{tabular}{c|c|c|c|c|c|c|cc} 
\multicolumn{3}{r|}{$y$ }\\
\multicolumn{3}{c|}{ }\\
\cline{2-6}
&&&&&\\
\cline{2-6}
&&&&&\\
\cline{2-6}
$x$&&&&&\\
\cline{1-6}
&&&&&\\
\cline{2-6}
&&&&&\\
\cline{2-6}
&&&&&\\
\cline{2-6}
\multicolumn{3}{c|}{ }\\
\multicolumn{3}{c|}{ }\\
\end{tabular}

\begin{problemparts}
\problempart On the grid above, mark with X's all the points that David
can reach in one step. Mark with O's the points that David can
reach in two steps.  (The axes labeled $x$ and $y$ intersect at David's
house.)

\problempart Give an informal explanation for why David can never get home.

\newpage

\problempart Describe a state machine that represents David's motion, and
list its transitions.

\problempart Prove that David can never get home.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 7

\problem

Consider the following algorithm that takes an array (list) $A[1\ldots n]$ of
numbers such that $A[1]<A[2]<\cdots<A[n]$, and a number $q$, and is
supposed to find $q$ if it is present in the list.

\begin{tabbing}
else \= else\= else\= else \=\kill

Find$(A,n,q)$\\
\\
$i \leftarrow 1$\\
$j \leftarrow n+1$\\
While $(j-i > 1)$\\
\> choose some $k$ with $i<k<j$\\
\> if $A[k] \le q$\\
\>  \> $i \leftarrow k$\\
\> else\\
\>  \> $j \leftarrow k$\\
Return $i$
\end{tabbing}

\begin{problemparts}
\ppart prove this function terminates

\end{problemparts}

Now suppose that $q=A[r]$ for some $r$. 

\begin{problemparts}
\ppart State an invariant of the while loop relating
$i,j$, and $r$.  The invariant should be ``obviously provable by
induction'' but you need not prove it.

\ppart Assuming the invariant, prove that Find returns $r$.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 8
\problem 

An infinite sequence of natural numbers $a_1, a_2, a_3$, \ldots is
defined in such a way that $a_1 = 14, a_2 = 35$, and each later
$a_i$, $i \geq 3$, is obtained using one of the following rules:\\

\vspace{.01in}
{\bf Rule A} Choose any two preceding elements of the sequence and define $a_i$
to be their sum. \\

\vspace{.01in}
{\bf Rule B} Choose any number $k \geq 1$ of preceding elements of the sequence,and define $a_i$ to be their product divided by $7^{k-1}$. \\
\vspace{.01in}
Use the well-ordering principle to prove that every element in the
sequence is a  multiple of $7$. 
({\it Hint:  In case you have forgotten, the well-ordering principle says
that every nonempty set of naturals has a smallest element.})

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 9
\problem

Prove that among any set of 150 natural numbers, there must be three
numbers, $a$, $b$, and $c$, such that all the pairwise differences,
$a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 10
\problem

For each of the following sets, either use diagonalization to prove
that the set is uncountable, or else use dovetailing or another
technique to show that the set is countable. \\
(If an answer to one part of the question follows from an answer you
have already given to another part, then you need only indicate this
-- you don't need to give a direct proof of the part that follows.) \\

\bparts
\ppart The set $E$ of all the even natural numbers.
\ppart The set of all subsets of $E$.
\ppart The set of all finite subsets of $E$.
\ppart The set of all even-size finite subsets of $E$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 11
\problem 

Give tight ($\Theta$) bounds for 

$$ \sum_{i=1}^n \frac{1}{\sqrt{i}}$$

You do not need to prove your answer formally, but you should show how you
derived it.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 12
\problem

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $O$, $\Omega$, $\Theta$, $o$ or $\omega$, depending
on whether $f(n)= O(g(n))$, $f(n) = \Omega(g(n))$, $f(n) =
\Theta(g(n))$, $f(n) = o(g(n))$ or $f(n) = \omega(g(n))$. If there is
more than one relation between $f(n)$ and $g(n)$, write only the
strongest one (a relation $X$ is stronger than another relation $Y$ if
$X$ implies $Y$ but the converse does not hold). The first line is an
example solution. Note: $\lg n = \log_2 n$.\\ 
\

\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
\begin{array}{rcrl}
2n         &=& \stackrel{\textstyle}{\blank} & (n) \\
%{\textstyle \Theta}{\blank} & (n) \\
&&&\\
\lg (n^3)  &=& \stackrel{\textstyle}{\blank} & (\lg n)\\
&&&\\
n!         &=& \stackrel{\textstyle}{\blank} & (4^n)\\
&&&\\
2^{\log_3 n} &=& \stackrel{\textstyle}{\blank} & (n^2)\\
&&&\\
\sum_{i=1}^{n}{1/i} &=& \stackrel{\textstyle}{\blank} & (1)\\
&&&\\
n^{4.01}   &=& \stackrel{\textstyle}{\blank} & (n^4 \lg n)\\
&&&\\
\sum_{i=n}^\infty {1/{i^2}} &=& \stackrel{\textstyle}{\blank} & (1)\\
&&&\\
{n \choose 10}&=& \stackrel{\textstyle}{\blank} & (n^{10}) \\
&&&\\
8^{\lg n}  &=& \stackrel{\textstyle}{\blank} & (n^3)
\end{array}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 13
\problem
Find asymptotic bounds for the following recurrences. You may assume
that $T(n)= \Theta(1)$ for $n \leq 1$ in each part.\\
\bparts

\ppart $T(n)= 2T(\floor{n/2})+\Theta(n)$\\
\ppart $T(n) = 4T(\floor{n/2+ \sqrt n})+ \Theta(n^2)$\\
\ppart $T(n) = T(\lceil n/3 \rceil)+2T(\floor{n/4})+\Theta(n)$\\
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 14
\problem

In the following problem there is no direct connection between the two parts.\\

\bparts 

\ppart Suppose that each pair of a genetically engineered species of
rabbits left on an island produces two new pairs of rabbits at the age
of one month and six new pairs of rabbits at the age of two months and
every month afterwards. None of the rabbits ever die or leave the
island.  Find a recurrence relation for the number of {\em pairs} of
rabbits on the island $n$ months after one newborn pair is left on
the island. Do not solve the recurrence relation.\\
\\

\ppart Solve the following inhomogeneous recurrence relation:\\
\begin{displaymath} 
f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2
\end {displaymath}

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems}

\end{document}




















% LocalWords:  Div David's
