\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<alist[midpoint]:
                return binarySearch(alist[:midpoint],item)
            else:
                return binarySearch(alist[midpoint+1:],item)
\end{verbatim}


\end{document}
