\documentclass[12pt]{exam}
\newcommand{\hwnumber}{4}

%%% begin hw-packages-and-macros.tex
\usepackage{amsmath}
\usepackage[left=1in, right=1in, top=1in, bottom=1in]{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{color}
\usepackage[all]{xy}
\usepackage{wrapfig}
\usepackage{fancyvrb}

\newcommand{\semester}{Fall 2013}

\newcommand{\Cnought}{C$0$}
\newcommand{\modulo}{\ \texttt{\%}\ }
\newcommand{\lshift}{\ \texttt{<<}\ }
\newcommand{\rshift}{\ \texttt{>>}\ }
\newcommand{\cgeq}{\ \texttt{>=}\ }
\newtheorem{task}{Task}
\newtheorem{ectask}{Extra Credit Task}
\newtheorem{exercise}{Exercise}

\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{5.65in}
\vspace{#1}
\end{framed}}

\pagestyle{head}

\headrule \header{\textbf{15-122 Homework \hwnumber}}{}{\textbf{Page
\thepage\ of \numpages}}

\pointsinmargin \printanswers

\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}
%%% end hw-packages-and-macros.tex

\begin{document}

\addpoints
\begin{center}
\textbf{\large{15-122 : Principles of Imperative Computation, \semester
\\  \vspace{0.2in} Written Homework~\hwnumber
}}

 \vspace{0.2in}

 \large{Due: Thursday, September 26, 2013 at 10pm}
\end{center}

\vspace{0.5in}

\hbox to \textwidth{Name:\enspace\hrulefill}


\vspace{0.2in}

\hbox to \textwidth{Andrew ID:\enspace\hrulefill}

\vspace{0.2in}

\hbox to \textwidth{Recitation:\enspace\hrulefill}


\vspace{0.5in}

\noindent 
In this homework assignment, we will examine asymptotic complexity,
searching and sorting.

\vspace{0.2in}

\begin{center}
\gradetable[v][questions]
\end{center}

\vspace{0.2in}
\begin{center}
  \Large{Write your answers \textit{neatly} on this PDF (or fill out
    the
    \href{http://www.cs.cmu.edu/~rjsimmon/15122-f13/hw/15122-written4.tex}{TeX
      handout}), and then submit the stapled printout to the handin
    box Thursday before lecture or on Thursday afternoon outside of
    Tom Cortina's office (GHC 4117).}
\end{center}

\newpage
\begin{questions}

\question{\textbf{Runtime Complexity.}} Consider the following
function that sorts the integers in an array, using \texttt{swap}
and \texttt{is\_sorted} from \texttt{arrayutil.c0}.

\begin{verbatim}
void sort(int[] A, int n)
  //@requires 0 <= n && n <= \length(A);                                        
  //@ensures is_sorted(A, 0, n);                                                
  {
    for (int i = 0; i < n; i++)
      //@loop_invariant 0 <= i && i <= n;                                       
      //@loop_invariant le_segs(A, 0, n-i, A, n-i, n);                          
      //@loop_invariant is_sorted(A, ____, _____);                                   
      {
        int s = 0;
        for (int j = 0; j < n-i-1; j++)
          //@loop_invariant 0 <= j && j <= n-i-1;                               
          //@loop_invariant ge_seg(A[j], A, 0, j);                              
          //@loop_invariant s > 0 || (s == 0 && is_sorted(A, 0, j));            
          {
            if (A[j] > A[j+1]) {
                swap(A, j, j+1);  // function that swaps A[j] and A[j+1]        
                s = s + 1;
            }
          }
        if (s == 0) return;
      }
  }
\end{verbatim}


\begin{parts}
\part[1] Complete the missing loop invariant for the first (\texttt{i}) loop.
\begin{solution}
\begin{verbatim}
//@loop_invariant is_sorted(A, _____________, ______________);
\end{verbatim}
\end{solution}

\part[1] The asymptotic complexity of this sort depends on the number of comparisons made between pairs of array elements. Let $T(n)$ be the worst-case number of such comparisons made when \texttt{sort(A, n)} is called. Give a closed form expression for $T(n)$.
\begin{solution}
\vspace{1in}
\end{solution}

\newpage
\part[1] Using big-$O$ notation, what is asymptotic complexity of $T(n)$?  This is the worst-case runtime complexity of \texttt{sort}.
\begin{solution}

\quad \quad \quad \quad $T(n) \in O( $ \quad \quad \quad \quad $)$
\vspace{0.1in}
\end{solution}


\part[2] Using your answer from the previous part,
show that $T(n) \in O(f(n))$ using the formal definition of big $O$.
That is, find a $c > 0$ and $n_0 \geq 0$ such that for every $n \geq n_0$, $T(n) \leq
cf(n)$. Show your work.
\begin{solution}
\vspace{3.9in}
\end{solution}

\part[1] Using big-$O$ notation, what is the best case asymptotic complexity of this sort as a function of $n$.
\begin{solution}

\quad \quad \quad \quad $O( $ \quad \quad \quad \quad $)$
\vspace{0.1in}
\end{solution}


\end{parts}


\newpage

\question{\textbf{Timing Code}}
\begin{parts}
The following run times were obtained when using two different algorithms on a data set of size n. You are asked to determine asymptotic complexity of the algorithms based on this time data. Determine the asymptotic complexity of each algorithm as a function of n. Use big-O notation in its tightest form and
briefly explain how you reached the conclusion. 

\part[1]
\begin{verbatim}
n              Execution Time
1000           0.564 milliseconds
2000           2.271 milliseconds
4000           8.992 milliseconds
8000           36.150 milliseconds
\end{verbatim}

\begin{solution}
\quad \quad \quad \quad $O( $ \quad \quad \quad \quad $)$
\vspace{2in}
\end{solution}

\part[1]
\begin{verbatim}
n              Execution Time
1000           0.043 milliseconds  -  CORRECTION
1000000        43.68 milliseconds
1000000000     43.9 seconds
\end{verbatim}

\begin{solution}
\quad \quad \quad \quad $O( $ \quad \quad \quad \quad $)$
\vspace{2in}
\end{solution}

\end{parts}

\newpage

\question{\textbf{Computing Overlaps}}

\begin{parts}
In this problem, we will study the Overlap Problem, which is the task of computing the number of shared elements between two arrays.  The problem requires an array \verb|A[]| of $m$ integers and a second array \verb|B[]| of $n$ integers.  We require the integers of \verb|A[]| and \verb|B[]| to be \emph{distinct}, meaning no integer will occur more than once in \verb|A[]| (or in \verb|B[]|), though some integers may occur once in each of \verb|A[]| and \verb|B[]|.  

Assume \texttt{linsearch(x, A, i, j)} returns the index of the first occurrence of integer \texttt{x} in integer array \verb|A[i,j)| or -1 if \texttt{x} is not found. This function does not require that the elements be in sorted order.

Consider the following function which counts the number of integers which are in both of \verb|A[]| and \verb|B[]|.

\begin{verbatim}
/*  1 */   int overlap(int[] A, int m, int[] B, int n)
/*  2 */   //@requires 0 <= m && m <= \length(A);
/*  3 */   //@requires 0 <= n && n <= \length(B);
/*  4 */   // placeholder for future requirement (part b)
/*  5 */   // placeholder for future requirement (part d)
/*  6 */   {
/*  7 */       int count = 0;
/*  8 */       int i = 0;
/*  9 */       while (i < m)
/* 10 */       //@loop_invariant  0 <= i;
/* 11 */       {
/* 12 */           if (linsearch(A[i], B, 0, n) != -1) {
/* 13 */               count = count + 1;
/* 14 */           }
/* 15 */           i = i + 1;
/* 16 */       }
/* 17 */       return count;
/* 18 */   }
\end{verbatim}

\part[1]
Uisng big-$O$ notation, what is the worst-case runtime of this algorithm?  Your answer should be in terms of $m$ and $n$.

\begin{solution}

\quad \quad \quad \quad $O( $ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $)$
\vspace{0.1in}
\end{solution}

\newpage

\part[2]
Suppose we add a third precondition to the function on line 4 as follows:
\begin{verbatim}
/*  4 */   //@requires is_sorted(B, 0, n);
\end{verbatim}
Using this additional requirement, explain how to modify the function to solve the Overlap Problem asymptotically faster than it currently does. (State which line(s) change and what the change(s) should be.)
\begin{solution}
\vspace{1.5in}
\end{solution}

\part[1]
Using big-$O$ notation, what is the worst-case runtime complexity of your revised algorithm?
Your answer should be in terms of $m$ and $n$.
\begin{solution}
\quad \quad \quad \quad $O( $ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad $)$
\vspace{0.1in}
\end{solution}

\part[3]
Suppose we add a fourth precondition to the function on line 5 as follows:
\begin{verbatim}
/*  5 */   //@requires is_sorted(A, 0, m);
\end{verbatim}
So now we require that both arrays are sorted prior to execution of this function. Describe an $O(m+n) = O(max(m,n))$ algorithm to solve the Overlap Problem. You should NOT write code; simply explain how the new algorithm works in a clear, concise manner.  Justify in one sentence that the runtime complexity is $O(m + n)$. (HINT: The algorithm should be very similar to something you've seen in class already.)
\begin{solution}
\vspace{2.5in}
\end{solution}

\end{parts}



\end{questions}
\end{document}


