\documentstyle[12pt,fullpage]{article}
%\textwidth 15cm
%\textheight 22cm
\topmargin -1cm
\oddsidemargin -0.2cm
\begin{document}
\parskip
\baselineskip
\bigskip

\begin{center}
{\Large {\bf Data Structures}}
\end{center}
\begin{center}
{\Large {\bf Exercise 1, part 3}}
\end{center}
{\bf Submition deadline: April 3}
\begin{enumerate}
\item Write programs to execute SchoolMult, BlockMult and CleverMult described in the class.
The programs should be written in Java language.
The input of each program is two positive numbers of arbitrary length : you CAN NOT assume that
the input is legal; thus you also should perform checking the input.
The output is the product of these two numbers and the number of
\begin{description}
\item{a.} comparisons.
\item{b.} recursive calls.
\item{c.} calls to SUM.
\end{description}
\item Is it true that the solution of $T(n) = 2T(\lfloor \frac{n}{2} \rfloor) + n$ is
$O(n\log{n})$? $\Omega(n\log{n})$? $\Theta(n\log{n})$? Prove your answer.
\item Give aymptotic upper and lower bounds for $T(n)$ in each of the following reccurences.
Assume that $T(n)$ is the constant for $n \leq 2$.
Make your bounds as tight as possible, and prove your answers.
\begin{description}
\item $T(n) = 2T(\frac{n}{4}) + \sqrt{n}$.
\item $T(n) = T(\sqrt{n}) + 1$.
\item $T(n) = 7T(\frac{n}{2}) + n^2$.
\item $T(n) = T(\frac{9n}{10}) + n$.
\item $T(n) = T(n-1) + n$.
\end{description}
\item This problem examines the implication of three parameter-passing strategies:
\begin{itemize}
\item An array is passed by a pointer. Time $= \Theta(1)$.
\item An array is passed by copying. Time $= \Theta(N)$, where $N$ is the size of the array.
\item An array is passed by copying only the subrange that might be accessed
by the called procedure.
Time $= \Theta(p-q+1)$ is the subarray $A[p \ldots q]$ is passed.
\end{itemize}
\begin{description}
\item{(a)} Consider the recursibe binary search algorithm for finding
a number in a sorted array.
Give reccurences for the worst-case running times of binary search when arrays are passed
usin each of the three methods above, and give good upper bounds on the solutions of the reccurences.
\item{(b)} Redo part (a) for the Merge-sort explained in class.
\end{description}
\end{enumerate}
\begin{center}
{\Huge {\bf Good Luck!}}
\end{center}
\end{document}