\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{21 January 1999}{6}

\begin{center}
\Large{\bf Problem Set 2 (due February 1)}
\end{center}

\bigskip

{\bf 1.  Asymptotic Notation} (5 $\times$ 4 = 20 points) 

For each of the following statements, indicate whether it is true or
false.  Briefly justify your answers.
\begin{itemize}
\item[(a)] 
$n^{3/2} = O(n \lg n)$.

\item[(b)]
Given that $T(1) = 1$, a valid solution to the recurrence $T(n) =
2T(n-1)$ is $T(n) = \Theta(2^n)$.

\item[(c)]
The statement ``The worst-case running time of algorithm $A$ is
$O(n)$'' implies the following: there exist positive constants $c$ and
$n_0$ such that for every input $I$ of size $n \ge n_0$, the running
time of $A$ on input $I$ is at most $c n$.

\item[(d)]
The statement ``The best-case running time of algorithm $A$ is
$O(n)$'' implies the following: there exist positive constants $c$ and
$n_0$ such that for every $n \ge n_0$, there exists an input of size
$n$ for which the running time of $A$ is at most $c n$.

\item[(e)]
The statement ``The worst-case running time of algorithm $A$ is
$\Omega(n)$'' implies the following: there exist positive constants
$c$ and $n_0$ such that for every input $I$ of size $n \ge n_0$, the
running time of $A$ on input $I$ is at least $c n$.
\end{itemize}

{\bf 2.}  Problem 7--1 (10 + 10 = 20 points)

{\bf 3.  Searching through two unsorted lists} (12 points)

Given two unsorted lists $S_1$ and $S_2$ of $n$ numbers each, and a
number $x$, describe an $O(n \lg n)$ algorithm for finding whether
there exists a pair of elements, one from $S_1$ and one from $S_2$,
that add up to $x$.  (For partial credit, give a $\Theta(n^2)$
algorithm for this problem.)

{\bf 4.} Exercise 6.3--3 (8 points)

{\bf 5.  The effect of group size on the running time of the selection
algorithm} (5 + 5 = 10 points)

In the algorithm {\sc Select} described in Section~10.3 of the text,
the input elements are divided into groups of 5.  Will the algorithm
work in linear time if they are divided into groups of 3? How about
groups of 7?

{\bf 6. Selection from two sorted lists} (10 bonus points)

Design and analyze an efficient algorithm to select the median from a
set of $m+n$ keys given in the form of two sorted lists, one of length
$m$ and the other of length $n$.  For convenience, you may assume that
the $m+n$ keys are all distinct.  ({\em Hint:}\/ A running time of
$O(\log(\min\{m,n\}))$ is achievable.)
\end{document}
