\documentclass[12pt]{exam}
\newcommand{\hwnumber}{7}
\newcommand{\hwname}{Strbuf}

%%% begin hw-packages-and-macros.tex
\usepackage{amsmath}
\usepackage[left=1in, right=1in, top=1in, bottom=1in]{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{tikz}
\usetikzlibrary{shapes}
\usepackage{fancybox}
\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{\%}\ }
\renewcommand{\lshift}{\ \texttt{<<}\ }
\renewcommand{\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: Tuesday, April 16, 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 issues in C code, integer types, and
tries. You can either type up your solutions or write them
\textit{neatly} by hand in the spaces provided. You should submit your
work in class on the due date just before lecture or recitation
begins. Please remember to \textit{staple} your written homework
before submission.
\vspace{0.2in}

\noindent Update 1, April 9: Fixed a typo in question 2.

\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-theory7.tex}{15122-theory7.tex},

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


\newpage
\begin{questions}

\question{\textbf{C programming issues}}

For each of the following problems:
\begin{enumerate}
\item \textbf{state what is wrong with the code} and;
\item \textbf{show how to correct it}.
\end{enumerate}

Do not just try to compile it and write down the error
message. (Compiling and running the code may be useful, but all of
these examples will compile without error, and some will even run and
produce output, but they all contain conceptual errors that affect
correctness, causing either an exception or undefined behavior at
runtime.)  Read the code and explain what is being done wrong,
conceptually.\\
%
\\
%
Think about all the ways to incur undefined behavior in C, including
accessing unallocated or uninitialized memory, dereferencing
\verb"NULL", dividing by zero, and signed arithmetic overflow.

\bigskip
\bigskip

\begin{parts}
\part[1]

The \verb'strlen' function returns the length of a standard C string.
For example, the call \verb'strlen("foo")' will return 3. If the
\verb'char' array passed to \verb'strlen' is not a valid,
\verb|'\0'|-terminated C string, \verb'strlen' will cause undefined
behavior.\\
%
\\
%
The \verb'strcpy(arr,str)' function copies a string of length $n$
(the second argument \verb'str') into a \verb'char' array that has
length {\it strictly greater} than $n$ (the first argument
\verb'arr'). If the array is not big enough, \verb'strcpy' will cause
undefined behavior.\\
%

\begin{verbatim}
#include <stdio.h>
#include <string.h>

int main() {
  char w[strlen("C programming")];
  strcpy(w,"C programming");
  printf("%s\n", w);
  return 0;
}
\end{verbatim}
\begin{solution}
\vspace{1in}
\end{solution}

\bigskip
\bigskip

\newpage
\part[1]

\begin{verbatim}
#include "xalloc.h"

int main() {
  int* a = xmalloc(100*sizeof(int));
  for (int i=0; i<100; i++) {
    if (a[i] == 0) a[i]=i;
    else a[i]=0;
  }
  free(a);
  return 0;
}
\end{verbatim}
\begin{solution}
\vspace{1in}
\end{solution}

\bigskip
\bigskip

\part[1]

\begin{verbatim}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
  char name[strlen("wordpress")];
  strcpy(name,"wordpress"+1);
  printf("%s\n", name);
  free(name);
  return 0;
}
\end{verbatim}
\begin{solution}
\vspace{1in}
\end{solution} ~\\

\bigskip
\bigskip

\newpage
\part[1]

\begin{verbatim}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "xalloc.h"

int main() {
  char *letter_data = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  char *a = xcalloc(16, sizeof(char));
  for (int i = 0; i < 16; i++) {
    a[i] = letter_data[i];
  }
  printf("The first sixteen letters are: %s\n", a);
  free(a);
  return 0;
}
\end{verbatim}

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

\bigskip
\bigskip

\part[1]
This code fragment shows a C function that is called from another
function. You can assume the precondition will be satisfied.
\begin{verbatim}
#include "contracts.h"
#include "xalloc.h"

// Returns an array of length n that must be freed by the caller
int *square_ar(int n)
{
  REQUIRES(n >= 0);
  int *A = xcalloc(n, sizeof(int));
  for (int i = 0; i < n; i++)
    A[i] = i * i;
  return A;
}
\end{verbatim}
\begin{solution}
\vspace{0.9in}
\end{solution}

\bigskip
\bigskip

\newpage
\part[1] This code fragment shows a C function that is called from another
function.
\begin{verbatim}
#include <stdio.h>
#include <string.h>
#include "contracts.h"
#include "xalloc.h"

char *rev_str(char *str) {
  char *rev = xcalloc(strlen(str)+1, sizeof(char));
  for (int i = strlen(str); i >= 0; i--) {
    rev[strlen(str) - i] = str[i];
  }
  printf("The reversed string is: %s\n", rev);

  ENSURES(strlen(rev) == strlen(str));
  return rev;
}
\end{verbatim}
\begin{solution}
\vspace{1in}
\end{solution}

\bigskip
\bigskip

\part[1]
This code fragment constructs a string of length \verb"n" with the
character \verb"c" repeated that many times. The function given here
will likely be called from other functions many times over.
\begin{verbatim}
char *strcdup(int n, char c) {
  char dup[n+1];
  int i;
  for (i = 0; i < n; i++)
    dup[i] = c;
  dup[i] = '\0';
  char *A = dup;
  return A;
}
\end{verbatim}
\begin{solution}
\vspace{1in}
\end{solution}

\bigskip
\bigskip

\newpage
\part[1]

This code fragment shows a C function that is used inside the library
implementation of queues. Assume that \verb'is_queue' returns true.

\begin{verbatim}
#include <stdlib.h>
#include "contracts.h"
#include "xalloc.h"

int queue_size(queue Q) {
  REQUIRES(is_queue(Q));
  list *L = xmalloc(sizeof(struct list_node));
  int size = 0;
  for (L = Q->front; L != Q->back; L = L->next) {
    size++;
  }
  free(L);
  return size;
}
\end{verbatim}

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

\bigskip
\bigskip


\newpage
\part[1]

This code fragment is intended to free a struct and also print out
the contents of the struct if the second argument \verb'also_print' is
\verb'true'. You can assume that the pointer passed to the function
points to a heap-allocated memory block and that the strings do not
need to be freed.

\begin{verbatim}
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "xalloc.h"

struct record_header {
  int num;
  char* name;
};
typedef struct record_header record;

void free_also_print(record *p, bool also_print)
{
  REQUIRES(p != NULL);
  if (also_print) {
    printf("Number: %d \n", p->num);
    printf("Name: %s \n", p->name);
    free(p);
  }
  free(p);
  return;
}
\end{verbatim}
\begin{solution}
\vspace{1in}
\end{solution}


\end{parts}

\clearpage
\question{\textbf{Casting}}

In C, we frequently have to cast types on the basis on their sign and
size.  Doing so can change the bit-patterns and their interpreted
values.  This question will test your understanding of how casting
works.\\
%
\\
%
Suppose that we are working with the expected
implementation-defined implementation of unsigned and signed (2's
compliment) \verb'char' (8 bits, one bite), \verb'short' (16 bits, two
bytes), and \verb'int' (32 bits, four bytes). Also assume that
\verb'char' is a \verb'signed char', though this is
implementation-defined.

\begin{parts}

\part[7]

We begin with the
following declarations:

\begin{quote}
\begin{verbatim}
short x = -6;
unsigned short y = 246;
char z = -2;
unsigned char w = 250;
\end{verbatim}
\end{quote}

Fill in the table below. In the third column, always use two hex
digits to represent a \verb'char' (signed or unsigned), four hex
digits to represent a \verb'short', and eight hex digits to represent
an \verb'int'.

\begin{center}
\begin{tabular}{ | l | l | l | }
\hline
{\bf C expression} & {\bf Decimal value} & {\bf Hexadecimal} \\\hline
& & \\
\verb'x' & -6 & \verb'0xFFFA'\\\hline
& & \\
\verb'(unsigned short)x' & 65530 & \verb'0xFFFA'\\\hline
& & \\
\verb'(int)x' & -6 & \verb'0xFFFFFFFA             '\\\hline
& & \\
\verb'y' & 246 & \verb'0x00F6' \\\hline
& & \\
\verb'(short)y' & & \\\hline
& & \\
\verb'(unsigned int)y' & & \\\hline
& & \\
\verb'z' & -2 & \\\hline
& & \\
\verb'(unsigned char)z' & & \\\hline
& & \\
\verb'(int)z' & & \\\hline
& & \\
\verb'w' & 250 & \\\hline
& & \\
\verb'(char)w' & & \\\hline
& & \\
\verb'(unsigned short)w' & & \\\hline
\end{tabular}
\end{center}

\clearpage
\part[3]

Say 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'.

Write a C function that takes a length-4 \verb'char' array named
\verb'A' and squeezes 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 lose points.

\begin{solution}
\begin{verbatim}
int squeeze(char *A) {
  // requires that A have length >= 4






























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

\newpage
\question{\textbf{Tries and tries again}}


DO NOT BE CONFUSED by the deceptive appearance of a festive holiday
message! As a ternary search trie, this data structure contains mostly
nonsense words:

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

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

As in lecture, 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.

\begin{parts}

\part[1] What are the {\it first four} (4) strings contained in this TST,
alphabetically?

\begin{solution}
\vspace{.5in}
\end{solution}

\part[1] What are the {\it last four} (4) strings contained in this TST,
alphabetically?
\begin{solution}
\vspace{.5in}
\end{solution}

\part[1] How many strings are there total?
\begin{solution}
\vspace{.5in}
\end{solution}

\newpage
\part[3]
The ternary search trie below contains real words. Add the words
\verb'adage', \verb'on', \verb'sage', \verb'ski', \verb'slow', and
\verb'so' to this data structure.

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

\end{parts}



\end{questions}

\end{document}
