\documentclass[12pt]{article}
\usepackage{times}
\usepackage{fancyheadings}
\pagestyle{fancy}
\usepackage{pifont} % for fancy bullets

\newcommand{\headerfont}{\fontfamily{phv}\fontseries{b}\fontshape{n}%
\fontsize{10}{12pt}\selectfont}
\newcommand{\ttb}{\fontfamily{pcr}\fontseries{b}\fontshape{n}%
\fontsize{12}{14pt}\selectfont}
\newcommand{\largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}%
\fontsize{14}{16pt}\selectfont}
\newcommand{\Largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}%
\fontsize{19}{21pt}\selectfont}
\newcommand{\Largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}%
\fontsize{19}{21pt}\selectfont}
\newcommand{\largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}%
\fontsize{14}{16pt}\selectfont}

\newcommand{\mywidth}{6.0in}
\newcommand{\lefthead}{CS1723: Data Structures, Assignment 1}
\newcommand{\st}{\rule[-.8mm]{0mm}{2mm}}
\newcommand{\longst}{\rule[-3mm]{0mm}{2mm}}
\newcommand{\outerbaselinesep}{12.5pt}
\topmargin 0.0in
\oddsidemargin 0.25in
\evensidemargin 0.25in
\textwidth \mywidth
\textheight 8.5in
\parindent 0mm %10mm
\parskip 2.5mm

\fboxrule=0.3mm

%%%%%%%%% Headings %%%%%%%%%%%%%%%%%%%%%%%
\setlength{\headwidth}{\textwidth} % This shouldn't be needed.  ??
%\setlength{\headrulewidth}{0pt} % to eliminate rule under header

\newcommand{\currhead}{CS 1723, Assignment 1: The 3/2 Problem, \today}
\lhead{\footnotesize \currhead}
\rhead{\footnotesize Page \thepage~~of~~\pageref{'thatsall'}\hspace{0.4mm}}
\lfoot{} \chead{} \cfoot{} \rfoot{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%
% main font declaration
%\timesroman
%%%%%%%%%%%%%%%%%%%%%%%%%

%\thispagestyle{empty}

\begin{center}
%{\largebold The University of Texas at San Antonio \\
%Computer Science Program \\
%San Antonio, Texas  78249} \\

%\vspace{0.2in}

{\largebold
   CS 1723,  Data Structures \\
    Fall Semester, 1998  \\
    Programming Assignment 1, Due September 4, 1998 } \\
 {\largeboldital  The 3/2 Problem}
\end{center}

\baselineskip=\outerbaselinesep

{\bf The Assignment:}
There is a famous game one can play with integers: start with any
positive integer $n$, and carry out the following replacement step:

\hspace*{1in} {\bf if} $n$ is odd {\bf then} replace $n$ by $(3n+1)/2$ \\
\hspace*{1in} {\bf else if} $n$ is even {\bf then} replace $n$ by $n/2$.

This step is repeated over and over again.
For example, if we start with $n=17$, the game produces the
following sequence of integers, which I call a {\em run}, of
{\em length} 10:

\hspace*{1in} 17, 26, 13, 20, 10, 5, 8, 4, 2, 1

In this case and in every other case that individuals have tried,
the sequence ends in 1.  (Notice that 1 is replaced by 2 and then by
itself, so nothing
more happens after one of these sequences gets to 1.)
Researchers conjecture that the sequence converges to 1 for
any starting positive integer $n$, but no one has been able to
prove this.

For this assignment, you are to write a program to investigate
this game.  More specifically, you should

\begin{list}{dummy}{\parsep=1mm \itemsep=1mm}
\item [\ding{97}] Produce the runs for starting integers $n$ from 1 to 100 000
  (but don't print the results!).  Your program should
  use {\tt scanf} to read in the limiting value of 100 000 from {\tt stdin}.
  You should assume that all runs will end in 1, and in fact
  you can write the program so that it would go into an infinite
  loop if a 1 was never produced in a run.
\item [\ding{97}]For these 100 000 runs, keep track of the number of
times each {\em run length} occurs, and keep track of the
{\em maximum value} that occurs in all runs of a given length.
(It turns out that the longest run has length 221, for $n \leq 100~000$.)
\item [\ding{97}]Use {\tt printf} to print the results on {\tt stdout}.
You should print three numbers to a line: the run length,
the number of times that run length occurred, and the maximum
value that came up in all runs of that length.
Do not print a line if there were no runs of that length.
\item [\ding{97}]You can keep track of the data in a table which
is, in C terms, an arrays of {\tt struct}s where each {\tt struct}
consists of two {\tt int}s: the count and the maximum value.
\end{list}

{\bf Your C Program:}
You may organize the program as a single file.

Early in the program you will need a struct declaration of the form:

\begin{verbatim}
        #define MAXS 230 /* runs < 230, n < 100000 */
        struct Entry_tag {
                int counts; /* num times run occurred */
                int max_val; /* max val, runs of this length */
        };  /* struct declaration */
\end{verbatim}

This tells C what the name {\tt Entry\_tag} refers to.

In the function {\tt main} you can declare the actual array of
{\tt struct}s as follows:

\begin{verbatim}
        struct Entry_tag s[MAXS];  /* table to hold run data */
\end{verbatim}

Your program should use the following four functions, in addition
to {\tt main()}, and the list of prototypes below should
appear early in your C source file, but it must appear after
the {\tt struct} declaration:

\begin{verbatim}
        void run(int, int *, int *);
        int next_value(int);
        void stats(int, int, struct Entry_tag s[]);
        void print_stats(struct Entry_tag s[]);
\end{verbatim}

\begin{list}{dummy}{\parsep=1mm \itemsep=1mm}
\item [\ding{77}] Here {\tt run(n, \&length, \&maxi)} produces the run for the integer
{\tt n} and returns the run length in the {\tt length} parameter
and the maximum value of the run in the {\tt maxi} parameter.
\item [\ding{77}] The function {\tt next\_value} should be used by {\tt run}
to generate the successor to a given integer, using the rule
at the beginning of this writeup.
\item [\ding{77}] A call to {\tt stats(length, maxi, s)} will enter the given
run length and maximum value into the table used by this program.
\item [\ding{77}] Finally, a call to {\tt print\_stats(s)} will print out the results,
as stored in the table.
\end{list}

Notice that the table is passed as a parameter.  The C code would
be slightly simpler if it used a global declaration for this table,
without needing to pass it to the two functions as a parameter,
but there are important reasons to avoid global variables.

As an alternative method, you could use the following equivalent declaration of
the table.  (But don't mix up the different methods.  This is more in the
style of the D \& S book, but C programmers tend to prefer the first
style above.)

\begin{verbatim}
        #define MAXS 230 /* runs < 230, n < 100000 */
        typedef struct {
                int counts; /* num times run occurred */
                int max_val;/* max val, runs of this length */
        } Entry_type;
\end{verbatim}

Now the declaration of the array of {\tt struct}s would have
the form:

\begin{verbatim}
        Entry_type s[MAXS]; /* table to hold run data */
\end{verbatim}

without the extra keyword {\tt struct}.  Similarly the two prototypes
with the table as parameter would have the form:

\begin{verbatim}
        void stats(int, int, Entry_type s[]);
        void print_stats(Entry_type s[]);
\end{verbatim}

For a value of {\tt i} (= run length) between 0 and 229, the two fields in
this table can be accessed by: {\tt s[i].counts}, and
{\tt s[i].max\_val}.  (We won't use the index {\tt i == 0}.)

{\bf The  {\ttb make} Utility:}
Create a new directory {\tt assign1} for your program, using
{\tt mkdir}.  Name your source file {\tt th.c}.  Create a
file named {\tt makefile} with the following contents:

\begin{verbatim}
        # makefile for the 3/2 program
        th:     th.c
                cc -p -g -o th th.c
        lint:   th.c
                lint -m -u th.c
\end{verbatim}

Be careful, the third and fifth lines of this file must
start with a {\em single tab character}.
After creating your source file (using the editor {\tt vi}),
first type

\hspace*{17mm}{\tt {\ttb runner\%} make lint}

to check out the program.  Then type

\hspace*{17mm}{\tt {\ttb runner\%} make}

to compile the program.  The {\tt make} utility will invoke the
C compiler ({\tt cc}) with options {\tt -p} to produce profiling
information, {\tt -g} to include a run-time symbol table for
debugging with the {\tt dbx} utility, and {\tt -o th} to name the
executable file {\tt th}.

Execute this program with

\hspace*{17mm}{\tt {\ttb runner\%} th\\
\hspace*{17mm}100000}

{\bf Required Output:}
Your output should look roughly as follows, but with the
extra lines included and your own name printed.
My program that produced this output assumed that runs terminated
when a 1 was reached, and that initial value $n = 1$ produced a
run of length 1.  I included the final 1 in the length of all runs.
If you make different assumptions, you'll get slightly different
output below, but that doesn't matter.

\begin{verbatim}
     Three/halves program written by <your name here>.
     Limit value for n: 100000
     Run length:   1, Count:     1, Maximum value:         1
     Run length:   2, Count:     1, Maximum value:         2
     Run length:   3, Count:     1, Maximum value:         4
     ... (Many lines omitted)
     Run length: 211, Count:     3, Maximum value: 296639576
     Run length: 212, Count:     1, Maximum value: 296639576
     Run length: 214, Count:     1, Maximum value:  53179010
     Run length: 215, Count:     1, Maximum value:  53179010
     Run length: 222, Count:     1, Maximum value:  10966508
\end{verbatim}

{\bf Execution Profile:}
The execution of this program also produces information regarding
the function calls---information stored in the file {\tt mon.out}.
Then the {\tt prof} utility will use this information to produce
an {\em execution profile}, showing the number of times each
function was called and the CPU time consumed by each function.
Use the command:

\hspace*{17mm}{\tt {\ttb runner\%} prof th}

{\bf The {\ttb dbx} Utility{\rm ---}Location of Segmentation Faults:}
Finally, you should try to use the debugger in case of a
{\em segmentation fault} (= address out or range).
Add the following line to your {\tt print\_stats} function:

\hspace*{17mm}{\tt s[1000000].counts = 1;}

This statement tries to access a memory location far beyond your own
permitted portion of memory.  It will produce a segmentation fault
and a core dump.  The example below shows a run, with the fault error
message and the use of {\tt dbx} to locate the fault.  (Here
{\ttb boldface} represents characters supplied by the system.)

\hspace*{17mm}{\tt {\ttb runner\%} dbx th\\
\hspace*{17mm}{\ttb ... lots of stuff printed ...}\\
\hspace*{17mm}{\ttb (dbx)} run\\
\hspace*{17mm}{\ttb Running: th }\\
\hspace*{17mm}{\ttb (process id 2268)}\\
\hspace*{17mm} 100000\\
\hspace*{17mm}{\ttb ... all the normal output...}\\
\hspace*{17mm}{\ttb Signal SEGV ...}\\
\hspace*{17mm}{\ttb "th.c" ...}\\
\hspace*{17mm}{\ttb (dbx)} where\\
\hspace*{17mm}{\ttb =$>$[1] print\_stats(), line 61 in "th.c"}\\
\hspace*{17mm}{\ttb   [2] main(), line 32 in "th.c"}\\
\hspace*{17mm}{\ttb (dbx)} quit\\
\hspace*{17mm}{\ttb runner\%} rm core}

At the ``where'', the debugger will tell you the line number of
the fault's location (line 61 in this case),
and the line number from which the function
containing the fault was called (line 32), and so on if there is
a deeper nesting of calls.

{\bf What To Turn In:} You should turn in a {\em single} listing containing
your {\em source file} ({\tt th.c} in this case), 
your output, and the profile information, all concatenated together.
(You do not need to turn in
anything related to your experimentation with the segmentation fault.)
One way to produce such a listing is the following:

\hspace*{17mm}{\tt {\ttb runner\%} make\\
\hspace*{17mm}{\ttb runner\%} th >th.output\\
\hspace*{17mm}100000\\
\hspace*{17mm}{\ttb runner\%} prof th >th.profile\\
\hspace*{17mm}{\ttb runner\%} cat th.c th.output th.profile >th.print\\
\hspace*{17mm}{\ttb runner\%} lp -d SCF1 th.print}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{'thatsall'}
\end{document}