\documentclass[12pt]{article}
\usepackage{fullpage,fancyhdr}
% \usepackage{amsmath,amssymb}
\usepackage{algorithm,algpseudocode}

\def\R{({\bf Regular})}
\def\Ex{({\bf Exercise})}
\def\EC{({\bf Extra Credit})}

\pagestyle{empty}
\markright{\,\hfill Intro. to Algorithms \hfill}

\begin{document}
\begin{center}
{\Large SPRING 2017: {\bf COT 5407}
{\sc Intro. to Algorithms}}\\
{\sc Sample Solutions}
\end{center}

\paragraph{Honesty statement:}
\begin{quote}
  {\sc I have adhered to the collaboration policy for this class. In
    other words, everything written down in this submission is my own
    work. For problems where I received any help, I have cited the source,
    and/or named the collaborator.}
\end{quote}

\hfill {\bf Signed and Acknowledged}, {\sc Johny B Good}

% \section*{Problems}

\begin{enumerate}
\item[1.] \R\ We discussed the {\bf invariant} for {\sc SelectionSort}
  in class. You can find the pseudocode and invariants for {\sc
    InsertionSort} and {\sc MergeSort} in Chapter 2 of your text
  (Cormen, et al.) [CLRS]. Write down precise {\bf invariants} for
  {\sc BubbleSort} (see p40 of text) and {\sc Merge} (not {\sc
    MergeSort}) (see p31 of text).

  \noindent {\bf Solution 1}: Invariant for {\sc Merge} can be found
  on p32 of [CLRS]. It states:
  \begin{quote}
    At the start of each iteration of the for-loop of lines 12 through
    17, the subarray $A[p..(k-1)]$ contains the $k-p$ smallest
    elements of $L[1 .. (n_1+1)]$ and $R[1 .. (n_2+1)]$ in sorted
    order. Moreover, $L[i]$ and $R[j]$ are the smallest elements of
    their arrays that have not been copied back into $A$.
  \end{quote}
  The proof (not asked for in the problem) is in the text p32-34. 

  Invariant for {\sc BubbleSort} (pseudocode on p40 of [CLRS]) is:
  \begin{quote}
    At the start of each iteration of the for-loop for $i$ (lines 1
    through 4), the subarray $A[1 .. (i-1)]$ contains the $i-1$ smallest
    elements of $A$ in sorted order.
  \end{quote}
  Proof is not required for this problem. Proof requires you to show
  {\bf Initialization} at start of iteration $i=1$ (trivial!) and {\bf
    Maintenance}, i.e., at start of arbitrary iteration $i$. A more
  detailed invariant is possible by adding something about the
  for-loop for $j$ on lines 2-4. 

\vfill 

\noindent {\bf Always start a fresh problem on a fresh page. Since you
  do not need to print out your solutions, we will not be killing any
  trees in the process.}

\pagebreak

\item[3.] \R\ Most sorting algorithms work correctly even if all items
  are not unique, i.e., there are repeats. A sorting algorithm is
  called {\bf stable} if numbers with the same value appear in the
  output array in the same order as they do in the input array. Which
  of the algorithms {\sc SelectionSort}, {\sc InsertionSort} and {\sc
    BubbleSort} are stable? If they are not stable give a small
  example with at most 4 items to prove your answer.

  \noindent {\bf Solution 3}: Consider an input array $A$ with 3 items
  $[2_1, 2_2, 1]$ in that order. The array has two copies of the
  number 2. In order to distinguish them we label them as $2_1$ and
  $2_2$, where $2_1$ appears before $2_2$ in the input array. If you
  apply algorithm {\sc XxxSort} (refer to pseudocode on page XX of
  [CLRS]) then because of $\cdots$ and line {\tt mm-nn} in pseudocode,
  the output would be $\cdots$ proving that {\sc XxxSort} is not a
  stable sorting algorithm.

\pagebreak

\item[X.] \R\ Design an algorithm to $\cdots$

  \noindent {\bf Solution X}: 

  \noindent {\bf Basic Idea}: The basic idea behind my solution is the
  following observation. We know that $\cdots$. Thus
  $\cdots$. However, $\cdots$. In order to take care of this problem,
  we do the following $\cdots$. The following pseudocode for {\sc
    FictionFlight} provides the details of the idea.

  \noindent {\bf Pseudocode}: 

\begin{algorithm}[H]
  \caption{\sc FictionFlight}
\begin{algorithmic}[1]
  \State Assume bird starts at $(r_R,c_R)$ of grid
  \State $s \leftarrow$ {\rm length\ of\ command\ seq\ } $S$
  \State $D[0,0,r_R,c_R] = $ {\sc true} 
  \State $(prevR,prevC) = (r_R,c_R)$
  \For {$t = 1$ {\bf to} $s$}
  \State $D[0,t, {\textsc move}(s[t],prevR,prevC)] = $ {\sc true}
  \State $(prevR,prevC) = \textsc{move}(s[t],prevR,prevC)$
  \Comment This trick is explained above
  \EndFor
  \For {$e = 1$ {\bf to} $numRows \times numCols$}
  \For {$t = 1$ {\bf to} $s$}
  \For {$r = 1$ {\bf to} $numRows$}
  \For {$c = 1$ {\bf to} $numCols$}
  \State $D[e,t,r,c] = D[e-1, t-1, r, c]\ {\bf or}\ D[e-1, t-1, \textsc{ngbr}(r,c)]$
  \EndFor
  \EndFor
  \EndFor
  \If{($D[e,s,r_E,c_E) =$ {\sc true})}
  \State Return $e$
  \EndIf
  \EndFor
\end{algorithmic}
\end{algorithm}

\noindent {\bf Correctness}: This is not a formal proof of
correctness. However, the algorithm must be correct because it uses
the {\sc Xx} algorithm from the book (page Zz) and algorithm {\sc
  move} (discussed in Lec W of class) with a minor modification, and
hence must be correct.

  \noindent {\bf Time Complexity Analysis}: The pseudocode suggests
  that the time complexity can be written down using the following
  recurrence:
  \[ T(n) = 2T(n/2) + O(n) \] 
  Solving this recurrence using case 2 of the Master Theorem gives us 
  \[ T(n) = \Theta(n\log n) \]
\end{enumerate}

\end{document}
