\documentclass{article}
%\usepackage{}

\begin{document}

\noindent CS140: Exam 1 \hfill Name \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \\
\noindent 2/8/01

\vspace{.2 in}


\vspace{.5 in}

\noindent I started this exam at \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}

\vspace{.5 in}

\noindent I finished this exam at \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
\vspace{1.5 in}

You have three hours to work on this exam.  You should return the exam to my office
within 20 minutes of your finish time.  The exam should be submitted no later than
11:59 PM on Sunday, October 6, 2001.  


You may use a one page cheat sheet but no text or other notes during this
exam.  You may not discuss the questions with anyone.
You may not use a calculator during the exam.
Your answers will be judged for clarity, conciseness, and correctness.  
The space provided should be adequate for your solutions.  

The exam consists of four problems and 11 pages.  Make sure your exam is complete.
Write your name, start time and stop time in the spaces provided.

\pagebreak

\vspace{1 in}
\begin{enumerate}





\item
(20 points)
Following are the recursive definitions of five functions:


\begin{description}
\item[ $f_1$ and $f_2$:]

$f_1(1)=f_2(1) = 1$
and for $n>1$
\begin{displaymath} 
\begin{array}{llll}
\mbox{for $n$ even: } & f_1(n) = f_2(n-1) &\mbox{and} & f_2(n)=2^{f_2(n-1)} \\
\mbox{for $n$ odd: } & f_1(n) = 2^{f_1(n-1)} &\mbox{and} & f_2(n)=f_1(n-1) \\
\end{array}
\end{displaymath}


\item [$f_3$ and $f_4$:]

$f_3(1)=f_2(1) = 1$
and for $n>1$
\begin{displaymath} 
\begin{array}{llll}
\mbox{for $n$ even: } & f_3(n) = f_4(n-1) &\mbox{and} & f_4(n)=2{f_4(n-1)} \\
\mbox{for $n$ odd: } & f_3(n) = 2{f_3(n-1)} &\mbox{and} & f_4(n)=f_3(n-1) \\
\end{array}
\end{displaymath}

\item [$f_5$:]

$f_3(1)= 1$
and for $n>1$
\begin{displaymath} 
\begin{array}{llll}
\mbox{for $n= \lceil \lceil n \rceil \rceil $ : } & f_5(n)=2*f_5(n-1) \\
\mbox{for $n \not = \lceil \lceil n \rceil \rceil $ : } & f_5(n)=f_5(n-1) \\
\end{array}
\end{displaymath}
\end{description}


\begin{enumerate}
\item
Which of these functions is $O(n)$?
\vspace .2 in

\item
Which of these functions is $\Omega(n)$?
\vspace .2 in

\item
Which of these functions is $O(2^n)$?
\vspace .2 in


\item
Which of these functions is $\Omege(2^n)$?
\vspace .2 in


\item
Which of these functions is $O(2\uparrow \uparrow n)$?
\vspace .2 in


\item
Which of these functions is $\Omege(2 \uparrow \uparrow n)$?
\vspace .2 in

\item

\pagebreak
\item

(20 points)
Identify each of the following statements as either true or false.
The functions $f(n), g(n)$ and $h(n)$ used in these problems
are monotonically increasing, positive valued functions on the natural numbers.

\begin{enumerate}
\item
For every $n$ there is some input of size $n$ for which algorithm ${\cal A}$ makes  $cn$
steps.  We can therefore conclude that  ${\cal A}$ is $\Omega(n)$.
\vspace{.8 in}
\item
For every $n$ there is some input of size $n$ for which algorithm ${\cal A}$ makes  $cn$
steps.  We can therefore conclude that  ${\cal A}$ is $O(n)$.
\vspace{.8 in}
\item
$f(n)=O(g(n))$ if and only if $g(n)=\Omega(f(n))$.
\vspace{.8 in}
\item
If $f(n)=O(g(n))$ and $f(n)=\Omega(h(n))$ then $h(n)=O(g(n))$.
\vspace{.8 in}
\item
If $f(n)=o(g(n))$ then $g(n)=\omega(g(n))$.
\vspace{.8 in}
\item
If $f(n)=O(g(n))$ then $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=c$ for some constant $c$.
\vspace{.8 in}
\item
If $2^{f(n)}=O(2^{g(n)})$ then $f(n)=O(g(n))$.
\vspace{.8 in}
\item
If $f(n)$ is a polynomial then $f(2n)=\theta(f(n))$.
\vspace{.8 in}
\item
For every pair of function $f(n)$ and $g(n)$, $f(n)=O(g(n))$ or
$g(n)=O(f(n))$ (or possibly both hold).
\vspace{.8 in}
\item
$\log^k(n) = O(n^{\epsilon})$ for any $k>0$ and $\epsilon>0$.
\vspace{.8 in}
\item
CS140 is fun!
\vspace{.8 in}
\end{enumerate}
\pagebreak

\item
(30 points)
Company X maintains a database on a list of integers $x_1, x_2, \ldots , x_n$.  A user
can query the database with a pair of indices $[i,j]$, where $1 \le i \le j \le n$, and the
database will return the product of the integers from $x_i$ to $x_j$ (inclusive); i.e. 
$\prod_{k=i}^j x_k$.  Notice that on 
a query $[i,i]$ the database simply returns the value of $x_i$. If a user submits a
query $[i,j]$ where $j<i$ or $i<1$ or $j>n$ the database returns an error message.
\begin{enumerate}
\item
(2 points)
Suppose the current list in the database is $\{1, 5, -3, 1\}$.
\begin{enumerate}
\item
What is the database response to the query $[1,3]$?
\vspace{.5 in}
\item
What is the database response to the query $[3,4]$?
\vspace{.5 in}
\end{enumerate}
\item
(3 points)
Company X hires you to work on the database.  They happen to mention that the
integers in their list are all {\em odd} but during a demo you notice that the
response to the query $[1,n]$ is an even number.  You know there must be an even
integer in the list because
(fill in the blanks with odd or even)
\begin{enumerate}
\item
The product of two odd integers is always \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~}.
\vspace{.2 in}

\item
The product of an even integer and an odd integer is always \underline{~~~~~~~~~~~~~~~~~~~~~~~~~~} .
\vspace{.2 in}
\item
The product of two even integers is always \underline{~~~~~~~~~~~~~~~~~~~~~~~~~}.
\vspace{.2 in}
\end{enumerate}
\pagebreak
\item
(10 points)
You explain to the CEO that there must be at least one even integer in their list.
``Must be an input error,'' he says.  ``I'm sure I didn't make more than one error
while entering the data.  But what a disaster!  It will take $n$
queries to find that even number.  And it will take
weeks to make $n$ queries.   Our IPO
is tomorrow! We are doomed!''

You say ``But dude.  I can find that even integer with far fewer than $n$ queries.''

``In worst case?'' he asks.

``Oh, yes even in worst case.'' you say.

``If you can do that you'll save the day!''

\begin{enumerate}
\item
How many queries do you need to find an even number in the database?  (Your answer
should be exact.  You can assume that $n=2^m$.)
\vspace{.5 in}
\item
Prove your answer by giving an algorithm and analyzing the number of queries it makes.
\end{enumerate}
\pagebreak
\item
(15 points)
The CEO is momentarily impressed but then says ``Wait.  Maybe there is even a better way
to do this.  Perhaps I can get one of those super-smart HMC profs to come over and 
find that even number with only a constant number of queries.''

``Dude!'' you say.  ``Those profs aren't nearly as smart as I!  And they can't find
an even number any faster (in worse case) than I can.  In fact, I can even prove they can't
do it faster.''

OK dude.  Prove it.  (Use an adversary argument to prove a lower bound on the number
of queries needed to find an even integer in the list.)
\end{enumerate}


\pagebreak



\item
(30 points)
Algorithm ${\cal A}$ is recursive.  On an input size of 1 or less the algorithm does a 
constant amount of work.  For input size of $n>1$, the algorithm makes two recursive
calls;  one on size $\frac{n}{4}$ and the other on size $\frac{3n}{4}$.  (Algorithm
${\cal A}$ is able to work on fractional input sizes so we don't have to worry about
floors and ceilings.)  $\cal A$ then does an additional
$cn$ steps to compute its output.  In other words the recurrence relation for the
running time of $\cal A$ is $T(n)=T(n/4) + T(3n/4) + cn$.

\begin{enumerate}
\item
(5 points)
Draw the work tree for the case when $n=(\frac{4}{3})^2=\frac{16}{9}$.  Use fractional input sizes and 
recall that the
algorithm halts if the input is 1 or less.
(You should notice that some root-to-leaf paths in the work tree are shorter than 
others. )
\pagebreak
\item
(6 points)
Now consider the work tree for $n=(\frac{4}{3})^m$, where $m \ge 2$.  Let $P$ denote the
shortest root-to leaf path in this tree.  Let $R$ denote the longest path.
\begin{enumerate}
\item
What are the input sizes associated
with the nodes along $P$, starting at the root?
\vspace{1 in}

\item
Which level contains the leaf of $P$? (The root is at level $0$.)
\vspace{1 in}

\item
What are the input sizes associated with the nodes along $R$, starting at
the root?
\vspace{1 in}


\item
Which level contains the leaf of $R$?
\vspace{1 in}
\end{enumerate}
\pagebreak

\item
(4 points)
Let ${\ell}$ denote the level containing the leaf of path $P$.
Prove that for any level $j$, where $0 \le j \le {\ell}$,
the total work done by the nodes at level $j$ is $cn$. 
\vspace{3.8  in}
\item
(8 points)
Using big-O notation, 
give the best upper bound you can for the running time of $\cal A$.
Prove your answer.
\pagebreak
\item
(7 points)
Let $f(n)$ be the bound you found in the previous question.
If you answered the previous part correctly then, in fact,
 $T(n)=\theta(f(n))$.  Prove this fact.





\end{enumerate}

\end{enumerate}

\end{document}
