\documentclass[12pt]{exam}
\newcommand{\hwnumber}{11}
\newcommand{\hwname}{Memory Management and AVL Trees}

%%% 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}{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 Written 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~[Update 2]
}}

 \vspace{0.2in}

 \large{Due: Thursday, November 21, 2013 by 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 The written portion of this week's homework will give you some
practice working with more C programming issues and tries.
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{Write your answers \textit{neatly} on this PDF (or fill out
    the
    \href{http://www.cs.cmu.edu/~rjsimmon/15122-f13/hw/15122-written10.tex}{TeX
      handout}), and then submit the stapled printout to the handin
    box Thursday before lecture or on Thursday afternoon or Friday outside of
    Tom Cortina's office (GHC 4117).}
\end{center}


\newpage
\begin{questions}

\question{\textbf{Typecasting and Function Pointers in C}}


Suppose that we are working with the expected
implementation-defined implementation of unsigned and signed (2's
compliment) \verb'short' (16 bits, two
bytes) and \verb'int' (32 bits, four bytes). 

\begin{parts}

\part[3]

We begin with the following declarations:

\begin{quote}
\begin{verbatim}
short w = -15;
unsigned short x = 65521;
int y = -65521;
\end{verbatim}
\end{quote}

\vspace{0.25in}
Fill in the table below. In the third column, always use four hex
digits to represent a \verb'short', and eight hex digits to represent
an \verb'int'.  You might find these numbers useful: $2^{16} = 65536$ and $2^{32} = 4294967296$.
\vspace{0.25in}

\begin{solution}

\begin{center}
\begin{tabular}{ | l | l | l | }
\hline
{\bf C expression} & {\bf Decimal value} & {\bf Hexadecimal} \\\hline
& & \\
\verb'w' & -15 & \verb'0xFFF1'\\\hline
& & \\
\verb'(unsigned short)w' & 65521 & \verb'0xFFF1'\\\hline
& & \\
\verb'(int)w' & -15 & \verb'0xFFFFFFF1             '\\\hline
& & \\
\verb'x' & 65521 &  \\\hline
& & \\
\verb'(int)x' & & \\\hline
& & \\
\verb'(int)(short)x' & & \\\hline
& & \\
\verb'y' & -65521 &  \\\hline
& & \\
\verb'(unsigned int)y' & & \\\hline
\end{tabular}
\end{center}

\end{solution}

\newpage
\part[2]
Consider the following C definition for the factorial function:

\begin{verbatim}
int factorial(int n)
{
    REQUIRES (n >= 0);
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}
\end{verbatim}

\vspace{0.25in}
Use \texttt{typedef} to define a C type named \texttt{int2int} that represents a function pointer that requires an int as its parameter and returns an int as its return type.
\begin{solution}
\begin{verbatim}

typedef ____________________________________________________;
\end{verbatim}
\end{solution}
\vspace{0.25in}
Let the variable \texttt{f} be of type \texttt{int2int}. (That is, \texttt{f} is a function pointer to a function that has one parameter of type \texttt{int} and returns a result of type \texttt{int}.) Show how to initialize \texttt{f} with the address of the \texttt{factorial} function given above using the address-of operator.

\begin{solution}

\begin{verbatim}

int2int f = ___________________________________________________;
\end{verbatim}
\end{solution}

\vspace{0.25in}
Write a C instruction that prints out 10! using the variable \texttt{f} defined above. Use an explicit derefencing operation on \texttt{f} to get to the factorial function.

\begin{solution}
\begin{verbatim}

printf( "10! = %d\n", _________________________________________);
\end{verbatim}
\end{solution}

\vspace{0.25in}
Suppose we wanted to set \texttt{x} equal to 8! using the function above. Is the following valid in C? (Yes or No)

\begin{verbatim}
int x = f(8);
\end{verbatim}

\begin{solution}

\end{solution}


\newpage
\part[2]

Suppose we have a (signed) \verb'char' array of length 4 and we want to
store that array in a single (4-byte) \verb'int' by storing the
\verb'char' array \verb'{1, 2, 3, 4}', for example, as
\verb'0x01020304'. Remember that \verb'char' is an integer
type in C. 

Write a C function that takes a length-4 \verb'char' array named
\verb'F' and condenses it into a single \verb'int' as outlined
above. Do not cast directly between signed and unsigned types of
different sizes, and make sure your solution works for \verb'char'
arrays containing negative values.

Your solution should be clear and straightforward; convoluted code
will not receive full credit.

\begin{solution}
\begin{verbatim}
int condense(char *F) {































}
\end{verbatim}
\end{solution}

\end{parts}





\newpage
\question{\textbf{Ternary Search Tries}}

\begin{parts}

Consider the TST shown below. 

\[\includegraphics[trim=0 50 0 0,width=0.85\textwidth]{trie.pdf}\]

%\begin{center}
%\includegraphics[scale=.65]{tst3.png}
%\end{center}

As in the lecture notes, the dotted lines connect a node to its \verb'middle'
child, and solid lines connect a node to its \verb'left' and
\verb'right' children. An X in the top left indicates that this node ends
a valid word. There could be a link to a corresponding value, like
a word definition, for example.

[Update 1, clarification.] The lecture notes and accompanying code
describe a desirable invariant of TSTs: that if the middle child is
\verb'NULL', the node has to end a valid word. This TST does not have
this property due to the topmost \verb'm' and \verb'e' nodes, but it
is not a necessary invariant for safety or correctness. (The insertion
and lookup algorithms work even without that invariant.)

\part[2] List all of the valid words stored in the TST above, in alphabetical order.

\begin{solution}
\vspace{1.5in}
\end{solution}

\newpage
\part[3]
Add the words
\verb'me', 
\verb'rake', 
\verb'hope', 
\verb'hot', 
\verb'top', and
\verb'act'
to the TST given on the previous page, one at a time, in the order given.


\begin{solution}
\[\includegraphics[trim=0 0 0 0,width=\textwidth]{trie.pdf}\]
\vspace{3in}
\end{solution}

\part[3] For this question, review the published code for tries from lecture.

  It is possible to implement \verb|trie_lookup| as an iterative
  function rather than a recursive one. Fill in the blanks so that the
  function shown below correctly implements lookup in a TST. 

  The lines involving the variables \verb|lower| and \verb|upper| are
  used only to prove that the loop invariant (written in the
  incorrect location as an assertion in the code below) is
  preserved. You should not use \verb|lower| or \verb|upper| when
  filling in the blanks.

\begin{solution}
\begin{verbatim}
elem trie_lookup(trie TR, char *s) {
    REQUIRES(is_trie(TR));
    REQUIRES(s != NULL);    
    tnode *T = TR->root;
    int charmin = 0;
    int charmax = (int)CHAR_MAX + 1;
    int lower = charmin;
    int upper = charmax;

    while (T != ___________________________________) {
       ASSERT(is_tnode(T, lower, upper)); // Loop invariant
       if (*s == T->c) {
           if (*(s+1) == '\0') {

               return ___________________________________________;
           } else {
               lower = charmin;
               upper = charmax;
               s++;

               T = ______________________________________________;
           }
       } else if (_____________________________________________) {
           lower = T->c;

           T = __________________________________________________;

       } else {
           upper = T->c;

           T = __________________________________________________;
       }
    }
    return NULL;
} // Update 2: missing '}' before the 'else if' case
\end{verbatim}
\end{solution}





\end{parts}


\end{questions}
\end{document} 
