\documentstyle{report}

\pagestyle{myheadings}
\def\headlineaux{\sc Math 322: C Programming and Unix
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\setlength{\textwidth}{6.25in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\newcommand{\assignmentNumber}{3}
\newcommand{\outdate}{22 September, 1994} 
\newcommand{\duedate}{6 October, 1994}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Problem Set \assignmentNumber \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Out: \outdate
     \\ Due: \duedate\end{flushright}}}}


\subsection*{Goals}

To learn records and pointers in C.
(Note that 2 weeks are given for this assignment.)

\subsection*{Reading Assignment}

Read Chapters 5, 6, 8 and 9 from {\sc A Book on C.}

\subsection*{Programming Assignment}

Write a program which converts text to Morse code and
Morse code to text. Let us give the program this 
user interface,
\begin{verbatim}
   morse [-D|-E] [-|filename]
\end{verbatim}
where,
\begin{verbatim}
         -D  switch to tell morse to DECODE 
         -E  switch to tell morse to ENCODE
         -   switch to tell morse to ignore filename and use stdin
         filename  file to encode or decode.
         output to stdout.
\end{verbatim}
furthermore, if the guileless user calls \verb.morse. without any
arguments, the program will print a helpful \verb.Usage. line then exit.
The input will convert lowercase characters to uppercase,
treat uppercase characters as themselves, 
and consider all other characters as whitespace.
The output will transcribe a dot as a period, a dash as an
underscore and will separate characters and words with whitespace,
either a blank or a newline.
Output line length should be controlled to standard limits.
Here is the output from {\em officer pup},
\begin{verbatim}
     ___ .._. .._. .. _._. . ._. .__. .._ .__.
\end{verbatim}

Encode and decode using this tree representation of the morse code,
\begin{verbatim}
                   <-dot/dash->
                  ______/\______
                 /              \
                E                T
              /   \            /   \
             /     \          /     \
            I       A        N       M
           / \     / \      / \     / \
          S   U   R   W    D   K   G   O
         / \ /   /   / \  / \ / \ / \
         H V F   L   P J  B X C Y Z Q 
\end{verbatim}
Since we are excellent programmers, we will approach the
problem of initializing this tree in the proper manner.
Write a subroutine taking a {\em tree description string} and
returning a tree described by the string.
A tree description string, TDS, has this formal definition,
\begin{verbatim}
    letter ::= @ | A | B | ... | Z
    TDS ::= ( TDS letter TDS ) 
            | ( letter TDS ) 
            | ( TDS letter )
            | ( letter )
\end{verbatim}
This represents a tree according to the formula,
\begin{verbatim}
     ( T1 l T2 )  =>        l
                          /   \
                         T1   T2  ( subtrees might be omitted )
\end{verbatim}
Where l is a character, and T1 and T2 are subtrees which, according
to the TDS definition, can either or both be omitted. If omitted the
subtree is empty.
Then call this subroutine on the TDS for the morse code tree,
\begin{verbatim}
   (((((H)S(V))I((F)U))E(((L)R)A((P)W(J))))@((((B)D(X))N((C)K(Y)))T(((Z)G(Q))M(O))))
\end{verbatim}

\noindent
{\sc Hint:} Build this tree using left-child, right-child
and parent pointers. As usual, an empty child is a Null pointer,
as is the parent of the root node. Traverse the tree filling in
the array \verb.access_table. with pointers into the tree,
\verb.access_table[0]. pointing to the 
tree node for '@', \verb.access_table[1]. pointing to the tree node for 'A',
and so on. For example,
\begin{verbatim}
    struct tree { 
        struct tree * left, * right, * parent ;
        int data ; } ;

    void init_decode_table( struct tree * t, struct tree * access_table[] )
    {
        if (t!=NULL) {
              init_decode_table( t->left, access_table ) ;
              access_table[t->data-'@'] = t ;
              init_decode_table( t->right, access_table ) ;
        }
    }
\end{verbatim}
Encode by using \verb.access_table. to jump to a starting
node in the tree, then emit characters
as you climb towards the root. Decode by ingesting characters as
you descend the tree starting from the root.

Good luck.
\end{document}