\documentclass[12pt]{exam}
\newcommand{\hwnumber}{3}
\newcommand{\hwname}{Claclab}

%%% 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}
\usepackage[T1]{fontenc}
\usepackage{listings}

\newcommand{\fillinlistings}{
    \lstset{ %
    language=C, numbers=left, numberstyle=\footnotesize, stepnumber=1,
    numbersep=4pt, showspaces=false, showstringspaces=false, tabsize=4,
    breaklines=true, breakatwhitespace=false,
    basicstyle=\normalsize\fontfamily{fvm}\selectfont, columns=flexible,
    mathescape=true, escapeinside={(*}{*)},
    morekeywords={alloc, allocarray, assert},
    otherkeywords={@requires, @ensures, @loop_invariant, @assert}
    }
}
\newcommand{\normallistings}{
    \lstset{ %
    language=C, numbers=left, numberstyle=\footnotesize, stepnumber=1,
    numbersep=4pt, showspaces=false, showstringspaces=false, tabsize=4,
    breaklines=true, breakatwhitespace=false,
    basicstyle=\footnotesize\fontfamily{fvm}\selectfont, columns=flexible,
    mathescape=true, escapeinside={(*}{*)},
    morekeywords={alloc, allocarray, assert},
    otherkeywords={@requires, @ensures, @loop_invariant, @assert}
    }
}

\newcommand{\semester}{Spring 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} Homework~\hwnumber~Theory [Update 1]
}}

 \vspace{0.2in}

 \large{Due: Thursday, February 21, 2013, at the {\bf beginning} of lecture}
\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 The written portion of this week's homework will give you some
practice working with sorting algorithms, stacks, and queues.
You can either type up your solutions or write them
\textit{neatly} by hand, and you should submit your work in class on the
due date just before lecture begins. Please remember to \textit{staple}
your written homework before submission.
\vspace{0.2in}

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

\vspace{0.2in}
\begin{center}
  \Large{You {\it must} use this printout, include this cover sheet,

    and staple the whole thing together before turning it in.
  
    Either type up the assignment using
    \href{http://www.cs.cmu.edu/~rjsimmon/15122-s13/hw/15122-theory3.tex}{15122-theory3.tex},

    or print this PDF and write your answers \textit{neatly} by
    hand.}
\end{center}


\newpage
\begin{questions}

\question{\textbf{Stacks and Queues}}

\textit{This question focuses on using interface functions for stacks and queues.  The division between an implementation (the details of a data structure's low-level
details) and an interface (how a client is able to interact with the data structure) is one of the most crucial distinctions in computer science.}\\
\\
Consider the following interfaces for \texttt{queue} and \texttt{stack} that store
elements of the type \texttt{elem}: 

\begin{quote}
\begin{verbatim}
/* Queue Interface */
queue queue_new();             /* O(1) */
bool queue_empty(queue Q);     /* O(1) */
void enqueue(elem e, queue Q); /* O(1) */
elem dequeue(queue Q)          /* O(1) */
  //@requires !queue_empty(Q);
  ;

/* Stack Interface */
stack stack_new();             /* O(1) */
bool stack_empty(stack S);     /* O(1) */
void push(elem e, stack S);    /* O(1) */
elem pop(stack S)              /* O(1) */
  //@requires !stack_empty(S);
  ;
\end{verbatim}
\end{quote}

\textbf{For this question, assume that we do not know how these data
  structures are implemented.} That is,
we don't know if the programmer used arrays or linked lists, or something
else---just that they somehow implemented the functions shown above, and that
they have the same observable behavior as a typical stack or queue.\\
\\
As a client, you can only use the interface functions specified above to interact with these data structures.  

\begin{parts}

\newpage

\part[2] 
Write a function \texttt{stack\_reverse(stack S)} that uses a
\textit{queue} to reverse the order of elements on the stack S that is
passed in.  

Include proper annotations in your code.

\begin{solution}
\begin{quote}
\begin{verbatim}
void stack_reverse(stack S)




{


















}   
\end{verbatim}
\end{quote}
\end{solution}
\newpage

\part[3]
Write a function \texttt{stack\_reverse(stack S)} that uses
\textit{stacks} to reverse the order of elements on the stack S that is
passed in. 

Include proper annotations in your code.

\begin{solution}
\begin{quote}
\begin{verbatim}
void stack_reverse(stack S)
   



{





















}   
\end{verbatim}
\end{quote}
\end{solution}
\end{parts}

\newpage


\question{\textbf{Quacks.}}  \textit{This question focuses on writing
  code to implement a particular data structure according to some
  given specifications.  This involves making the implementation:}
\begin{enumerate}
\item \textit{Generic (it does not make any assumptions regarding
  the data the client wishes to place in the data structure)}
\item \textit{Accurate (it does not violate any of the data
  structures properties)}
\item \textit{Safe (it rejects any malformed input that the client
  may enter)}
\end{enumerate}

After learning about queues and stacks in 15-122, Fred Hacker decided he'd try
to combine the data structures to get the best of both worlds.

Consider the following interface for a data structure that Fred calls
a {\tt quack}. 
\begin{quote}
\begin{verbatim}
bool quack_empty(quack Q);            /* O(1) */
bool quack_new();                     /* O(1) */
void enqueue(elem e, quack Q);        /* O(1) */
elem dequeue(quack Q);                /* O(1) */
void push(elem e, quack Q);           /* O(1) */
elem pop(quack Q);                    /* O(1) */
bool quack_equal(quack Q1, quack Q2); /* O(n) */
\end{verbatim}
\end{quote}

Quacks accept elements of the type {\tt elem}, which is just a generic
type name -- if we wanted to put {\tt int}s in the {\tt quack} we
would use {\tt typedef int elem}.  The actual type of {\tt elem} is
provided by the \textit{client}; the implementation of quacks should
\textit{not} rely upon the concrete details of {\tt elem}.

Fred decided to use a linked list to implement his {\tt quack}.
The linked list he used is defined with these {\tt struct}s:

\begin{quote}
\begin{verbatim}
struct list_node {
  elem data;
  struct list_node *next;
};
typedef struct list_node node;
struct quack_header {
  node *head;
  node *tail;
};
typedef struct quack_header* quack;
\end{verbatim}
\end{quote}

Fred thinks he'll be able to make lots of money off of his {\tt quack}
data structure, so he's kept its implementation secret.  All we know
is that his implementation uses the above {\tt struct}s to store its
data and that each function has the runtime specified in the
interface, that it acts like a stack when only \verb'push' and
\verb'pop' are used, and that it acts like a queue when only
\verb'enqueue' and \verb'dequeue' are used.

Your task is to implement Fred's {\tt quack} before he can release it, so
\emph{you} can make any money that it's worth.

\textbf{In your implementation, do not use an extra node at the end of the list as we've done in class for our implementation of queues and stacks.}

\begin{enumerate}
\item In other words, if {\tt tail} is not {\tt NULL}, then
  \verb'tail->data' should contain actual data that we want to store,
  and \verb'tail->next' should be {\tt NULL}.
\item If {\tt tail} is {\tt NULL}, then {\tt head} must also be {\tt
  NULL} and the {\tt quack} is empty.
\item In the case where there is only one thing in the {\tt quack},
  \textit{both} {\tt head} and {\tt tail} should point to it.
\end{enumerate}

Your quack implementation, in other words, will look like this when
there are four elements in the quack. (The \verb'head' and \verb'tail'
must be assigned as shown below for relevant quack operations to have O(1)
time; you should consider why this must be the case.)
\[\includegraphics[trim=0 250 0 0,width=.6\textwidth]{quack.pdf}\]


You may assume you have the functions, which you may use for any pre/post conditions:
\begin{itemize}
    \item {\tt bool is\_quack(quack Q)}, which checks that the given
      {\tt quack} is valid (it makes sure it's not {\tt NULL}, that
      everything in the {\tt quack} is as it should be, that there are
      no cycles in the list, that \verb'Q->head' is \verb'NULL' if
      \verb'Q->tail' is \verb'NULL' and vice-versa, etc.)
    \item {\tt bool elem\_equal(elem e1, elem e2)}, which compares two
      elements of type {\tt elem} and checks if they are equal or not.
      This is a \textit{client-side function}, along with the type
      \texttt{elem}.
    \item {\tt elem peek\_last(quack Q)}, which returns the last
      element of {\tt Q} and does NOT modify it.
    \item {\tt elem peek\_first(quack Q)}, which returns the first
      element of {\tt Q} and does NOT modify it.
\end{itemize}

In the following sub-parts, you will write the code necessary to implement quacks as per the description given above.  Bear the following points in mind: 

\begin{enumerate}
\item You must include all necessary pre-conditions/post conditions to guarantee that the operations work as specified above.  Refer to the code given in lecture on the implementation of stacks and queues to get idea of what contracts to write.  
\item Your functions must have the runtime performance specified in the interface.
\item Try to write the code on paper, with the aid of diagrams, instead of using
{\tt coin} or {\tt c0}, as you will be expected to write code on the exams without
access to either of these tools.
\end{enumerate}

% \include{quackassign}
\begin{parts}

\newpage

\part[1]
Write the \texttt{quack\_empty} function that returns true if and only if
the given \texttt{quack} is empty. \emph{Your function should NOT modify the {\tt quack} that is passed in.} 
\begin{solution}
\begin{quote}
\begin{verbatim}
bool quack_empty(quack Q)



    
{



}
\end{verbatim}
\end{quote}
\end{solution}

\part[1] 
Write a \texttt{quack\_new} function that returns a valid, empty {\tt quack}
\begin{solution}
\begin{quote}
\begin{verbatim}
quack quack_new()


{



 



}
\end{verbatim}
\end{quote}
\end{solution}

\newpage
\part[2]
Write an \texttt{enqueue} function which, given a
\texttt{quack Q}, adds the element {\tt e} to the {\tt tail} of the {\tt quack}.  Include a contract that guarantees that the element {\tt e} has been added to the end of the quack.  
\begin{solution}
\begin{quote}
\begin{verbatim}
void enqueue(elem e, quack Q)




{
    

















}
\end{verbatim}
\end{quote}
\end{solution}

\newpage

\part[2]
Write a \texttt{dequeue} function  which, given a non-empty {\tt quack}, removes 
the element at the {\tt head} of the {\tt quack} and returns it.  
\begin{solution}
\begin{quote}
\begin{verbatim}
elem dequeue(quack Q)




{








}
\end{verbatim}
\end{quote}
\end{solution}

\newpage

\part[2]
Write a {\tt push} function which, given a {\tt quack} and an element
{\tt e}, adds {\tt e} to the {\tt head} of the {\tt quack}.  Include a
contract that guarantees that the element {\tt e} has been added to
the front of the quack.

\begin{solution}
\begin{quote}
\begin{verbatim}
void push(elem e, quack Q)



{







}
\end{verbatim}
\end{quote}
\end{solution}


\part[1]
Write a {\tt pop} function  which, given a nonempty {\tt quack}, pops an element off the {\tt head} of the {\tt quack} and returns it.\\
\emph{Hint: it should be possible to write this function in one simple line of code
    using functions you have already written.}
\begin{solution}
\begin{quote}
\begin{verbatim}
elem pop(quack Q)



{




}
\end{verbatim}
\end{quote}
\end{solution}

\newpage
\part[2]
Write a {\tt quack\_equal} function which checks if two quacks are equal (ie they have the same number of elements and the elements are equal and are arranged in the 
same order.\\
\emph{Your function should not assume anything about the type of data stored in the quacks.  You can assume that both quacks have data of type {\tt elem}.  Your function may NOT modify the original quacks passed in} 
\begin{solution}
\begin{quote}
\begin{verbatim}
bool quack_equal(quack Q1, quack Q2)






{





    
    
    
    
    
    
    









}
\end{verbatim}
\end{quote}
\end{solution}
\end{parts}

\newpage


\normallistings
\question{\textbf{Mergesort}} 
%
This question concerns the implementation of \verb|mergesort|; an
implementation is given below.  The effect of \verb|copy_array| in
line~\verb|49| is to copy the array \verb|B|$[0, {\it length})$ into
  \verb|A|$[{\it lower}, {\it upper})$.  \verb'A' is changed so that
    \verb|A[lower + i] == B[i]| for each \verb|i < length|.



\begin{lstlisting}
void mergesort (int[] A, int lower, int upper) 
//@requires 0 <= lower && lower <= upper && upper <= \length(A); 
//@ensures is_sorted(A, lower, upper); 
{ 
  if (upper-lower <= 1) return; 
  int mid = lower + (upper-lower)/2;

  mergesort(A, lower, mid); 
  //@assert is_sorted(A, lower, mid);

  mergesort(A, mid, upper); 
  //@assert is_sorted(A, mid, upper);

  merge(A, lower, mid, upper);
  return;
}

void merge (int[] A, int lower, int mid, int upper)
/*@requires 0 <= lower && lower <= mid
         && mid <= upper && upper <= \length(A);*/
//@requires is_sorted(A, lower, mid);
//@requires is_sorted(A, mid, upper);
//@ensures is_sorted(A, lower, upper);
{
  int length = upper - lower;
  int[] B = alloc_array(int, length);
  int i1 = lower;
  int i2 = mid;
 
  for(int k = 0; k < length; k++)
    //@loop_invariant 0 <= k && k <= length;
    //@loop_invariant lower <= i1 && i1 <= mid;
    //@loop_invariant mid <= i2 && i2 <= upper;
    //@loop_invariant (i1 - lower) + (i2 - mid) == k;
    //@loop_invariant is_sorted(B, 0, k);
    /*@loop_invariant k == 0 ||
                            ((i1 == mid || A[i1] >= B[k-1])
                              && (i2 == upper || A[i2] >= B[k-1]);*/
    {
      if(i2 == upper || (i1 < mid && A[i1] <= A[i2])) {
        B[k] = A[i1];
        i1++;
      } else {
        B[k] = A[i2];
        i2++;
      }
    }
  //@assert is_sorted(B, 0, length);
  copy_array(A, lower, upper, B, 0, length);
}
\end{lstlisting}


In part (a) of this question we will reason operationally about the
\verb'mergesort', and in part (b) we will reason logically about
safety.

\begin{parts}


\part[4] Suppose we have the array \verb|A[]| below, and call
\verb|mergesort(A, 0, 8)|.  Step through the execution of
\verb|mergesort(A, 0, 8)|, and write down the contents of \verb|A[]|
after each \verb|merge| call terminates.  Thus, the first line should
contain \verb|A[]| immediately after the first \verb|merge| call
terminates, the second line should contain \verb|A[]| immediately
after the second \verb|merge| call terminates, and so on.  Note that
\verb|mergesort| does not always call \verb|merge|, and that even when
\verb|merge| is called on a smaller subarray of \verb|A[]|, you should
fill in the \textbf{entire} contents of \verb|A[]|.  Finally, the
number of lines provided may be more than the number of times
\verb|merge| is called; any excess lines should be left blank.

\newcommand{\bx}[1]{\makebox[3em][c]{$#1$}}

\[\renewcommand{\arraystretch}{2}
\begin{array}{|c||c|}
\hline
\verb|merge|\text{ \#} & \verb|A[]| \\
\hline
\bx{} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{7} & \bx{5} & \bx{0} & \bx{3} & \bx{4} & \bx{1}  & \bx{2} & \bx{6} \\\hline\end{array} \\[1ex]
\hline
\bx{1} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\hline
\bx{2} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\hline
\bx{3} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\hline
\bx{4} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\hline
\bx{5} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\hline
\bx{6} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\hline
\bx{7} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\hline
\bx{8} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\hline
\bx{9} & \begin{array}{|c|c|c|c|c|c|c|c|}\hline \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} & \bx{} \\\hline\end{array} \\[1ex]
\end{array}
\]


\newpage
%\input{theory3-proofquestion}

\part[5] 
%
The \verb'merge' function contains both a number of array
accesses.
For the following array accesses, list the facts that establish the safety of
that array access, as well as the line that immediately provides each
of those facts. You do not need to give the intermediate reasoning,
just the raw facts that would allow you to establish safety and the
lines of code that immediately justify those facts. Do not include any
extra or unnecessary facts.

\begin{solution}

\begin{itemize}
\item Line \verb|37|, \verb|A[i1]|

\verb|0 <= lower| (line \verb|19|)\\
\verb|lower <= i1| (line \verb|32|)\\
\verb|i1 <= mid| (line \verb|32|)\\
\verb|i1 != mid| (line \verb|37|)\\
\verb|mid <= upper| (line \verb|20|)\\
\verb|upper <= \length(A)| (line \verb'20')

\item Line \verb|37|, \verb|B[k-1]|

\vspace{1.5in}

\item Line \verb|38|, \verb|A[i2]|

\vspace{1.5in}

\item Line \verb|38|, \verb|B[k-1]| (same as the justification from
  line \verb|37|)

\item Line \verb|40|, \verb|A[i1]|

\vspace{1.5in}

\item Line \verb|40|, \verb|A[i2]|

\verb|0 <= lower && lower <= mid| (line \verb|19|)\\
\verb|mid <= i2 && i2 <= upper| (line \verb|33|)\\
\verb|i2 != upper| (line \verb|40|)\\
\verb|upper <= \length(A)| (line \verb|20|)

\item Line \verb|41|, \verb|B[k]|

\verb|0 <= k| (line \verb|31|)\\
\verb|k < length| (line \verb|30|)\\
\verb|length| = \verb|\length(B)| (line \verb|26|)


\item Line \verb|41|, \verb|A[i1]|

\vspace{1.5in}

\item Line \verb|44|, \verb|B[k]| (same as the justification from line
  \verb|41|)

\item Line \verb|44|, \verb|A[i2]|

\vspace{1.5in}

\end{itemize}
\end{solution}

% \input{recurrence.tex}

\end{parts}
\end{questions}
\end{document} 
