\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