\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{times,url}
\newcommand{\profs}{Professors Ron Rivest and Srini Devadas}
\newcommand{\subj}{6.006}
\newlength{\toppush}
\setlength{\toppush}{2\headheight}
\addtolength{\toppush}{\headsep}
\newcommand{\htitle}[3]{\noindent\vspace*{-\toppush}\newline\parbox{6.5in}
{\textit{Introduction to Algorithms: 6.006}\hfill\name\newline
Massachusetts Institute of Technology \hfill #3\newline
\profs\hfill Handout #1\vspace*{-.5ex}\newline
\mbox{}\hrulefill\mbox{}}\vspace*{1ex}\mbox{}\newline
\begin{center}{\Large\bf #2}\end{center}}
\newcommand{\handout}[3]{\thispagestyle{empty}
\markboth{Handout #1: #2}{Handout #1: #2}
\pagestyle{myheadings}\htitle{#1}{#2}{#3}}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
\newcommand{\name}{INSERT NAME HERE}
\begin{document}
\handout{4}{Problem Set 1}{September 11, 2007}
\setlength{\parindent}{0pt}
\newcommand{\solution}{
\medskip
{\bf Solution:}
}
\newcommand{\collaborators}[1]{
\qquad {\bf Collaborators:} #1
}
This problem set is due {\bf September 25} at {\bf 11:59PM}.
Solutions should be turned in through the course website in PS or PDF
form using LaTeX. The course website has links to a number of editors
that are useful for writing in LaTeX.
It is recommended that you download the LaTeX source for this problem
set which includes placeholders for solutions.
\begin{enumerate}
\item Asymptotic Notation
\collaborators{LIST COLLABORATORS HERE} %Write `none' if solved alone.
Decide whether these statements are {\bf True} or {\bf False}. You
must briefly justify all your answers to receive full credit.
\begin{enumerate}
\item $f(n) = \Omega(g(n)) \implies g(n) = O(f(n))$
\solution INSERT ANSWER HERE
\item $f(n) = O(g(n)) \land f(n) = \Omega(h(n)) \implies g(n)
= \Theta(h(n))$
\solution INSERT ANSWER HERE
\item $f(n) = O(g(n)) \land g(n) = \Omega(f(n)) \implies f(n) =
\Theta(g(n))$
\solution INSERT ANSWER HERE
\end{enumerate}
\item Binary Search
\collaborators{LIST COLLABORATORS HERE} %Write `none' if solved alone.
In \emph{Problem Solving With Algorithms And Data Structures
Using Python} by Miller and Ranum, two examples are given of a
binary search algorithm. Both functions take a sorted list of
numbers, \texttt{alist}, and a query, \texttt{item}, and return true
if and only if $\texttt{item} \in \texttt{alist}$. The first
version is iterative (using a loop within a single function call)
and the second is recursive (calling itself with different
arguments). Both versions can be found on the last page of this
problem set.
Let $n = \texttt{len(alist)}$.
\begin{enumerate}
\item What is the runtime of the iterative version in terms of $n$, and why?
\solution
INSERT ANSWER HERE
\item What is the runtime of the recursive version in terms of $n$,
and why?
\solution
INSERT ANSWER HERE
\item Explain how you might fix the recursive version so that it
has the same asymptotic running time as the iterative version (but
is still recursive).
\solution
INSERT ANSWER HERE
\end{enumerate}
\item Set Intersection
\collaborators{LIST COLLABORATORS HERE} %Write `none' if solved alone.
Python has a built in \texttt{set} data structure. A \texttt{set} is
a collection of elements without repetition.
In an interactive Python session, type the following to create an
empty set:
\texttt{s = set()}
To find out what operations are available on sets, type:
\texttt{dir(s)}
Some fundamental operations include \texttt{add}, \texttt{remove},
and \texttt{\_\_contains\_\_} and \texttt{\_\_len\_\_}. Note that
\texttt{\_\_contains\_\_} and \texttt{\_\_len\_\_} are more commonly
called with the syntax \mbox{\texttt{element in set}} and \texttt{len(set)}.
All four of these operations run in constant time.
For this problem, we will be analyzing the runtime of \texttt{intersection},
\texttt{intersection\_update}, \texttt{union}, and \texttt{update},
on two sets, $s$ and $t$.
\begin{enumerate}
\item What do each of those four operations do? Use the Python
\texttt{help} command. Refer to http://docs.python.org/ as
necessary.
\solution
\begin{tabular}{|c|p{270pt}|} \hline
\texttt{intersection} & INSERT ANSWER HERE \\ \hline
\texttt{intersection\_update} & INSERT ANSWER HERE \\ \hline
\texttt{union} & INSERT ANSWER HERE \\ \hline
\texttt{update} & INSERT ANSWER HERE \\ \hline
\end{tabular}
\item Using $\Theta$ notation, how long do you conjecture each of the four
operations will take in terms of $|s|$, $|t|$, $|s \cup t|$, and
$|s \cap t|$? Give reasons.
\solution
\begin{tabular}{|c|p{270pt}|} \hline
\texttt{intersection} & INSERT ANSWER HERE \\ \hline
\texttt{intersection\_update} & INSERT ANSWER HERE \\ \hline
\texttt{union} & INSERT ANSWER HERE \\ \hline
\texttt{update} & INSERT ANSWER HERE \\ \hline
\end{tabular}
\item Now try these operations out using a variety of values for
$|s|$, $|t|$, $|s \cup t|$, and $|s \cap t|$. You may wish to use
the Python modules \texttt{profile} or the more lightweight
\texttt{timeit}. A good description of how to use \texttt{timeit} is
available at \\
http://www.diveintopython.org/performance\_tuning/timeit.html
Describe your methods and results. Try to give a simple but
reasonably accurate formula that fits your experimental
results. Discuss any discrepancies between your conjectures in part
(b) and your experimental results.
\solution
INSERT ANSWER HERE
\end{enumerate}
\end{enumerate}
\newpage
Iterative Version:
\begin{verbatim}
def binarySearch(alist, item):
first = 0
last = len(alist)-1
found = False
while first<=last and not found:
midpoint = (first + last)/2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return found
\end{verbatim}
Recursive Version:
\begin{verbatim}
def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)/2
if alist[midpoint]==item:
return True
else:
if item