\documentclass[12pt]{article}
\usepackage{times}
\usepackage{fancyheadings}
\pagestyle{fancy}
\textwidth=6.5in
\oddsidemargin=0in
\setlength{\headwidth}{\textwidth} % This shouldn't be needed.  ??
\lhead{\footnotesize CS 1723, Data Structures, Assignment 9, \today}
\rhead{\footnotesize Page \thepage~~of~~\pageref{'thatsall'}}
\lfoot{} \chead{} \cfoot{} \rfoot{}

\newcommand{\ttb}{\fontfamily{pcr}\fontseries{b}\fontshape{n}%
  \fontsize{11}{13pt}\selectfont}  %Courier bold at 11pt
\newcommand{\longst}{\rule[-3mm]{0mm}{2mm}}

\newcommand{\st}{\rule[-.8mm]{0mm}{2mm}}
\newcommand{\mywidth}{6.5in}
\newcommand{\myrightmar}{0.2in}
\newcommand{\myleftmar}{0.4in}
\newcommand{\myparsep}{2mm}
\newcommand{\mynegvertsp}{-0.35in}
\newcommand{\myvspace}{-0.2in}
\textwidth \mywidth
\parindent 10mm
\parskip 3mm
\columnsep=6mm %%%10mm
\topmargin=0in
\textheight=8in
\oddsidemargin=0in
\evensidemargin=0in

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% make everything sloppy
\sloppy

%\thispagestyle{empty}

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

%\vspace{0.4in}

{\large\bf
   CS 1723,  Data Structures \\
    Fall Semester, 1998\longst  \\
    Programming Assignment 9\longst } \\
 {\large\it  Sorting Algorithms \\
   Due November 30, 1998}
\end{center}

\noindent
{\bf The Assignment:}
For this assignment, you are to write program(s) that will measure execution (CPU) 
times of various sort algorithms.  You can measure these times using the 
{\tt clock()} function as shown in the handout that timed the C builtin sort {\tt qsort()}.  
(Include {\tt <time.h>} for {\tt clock()}.  You should call {\tt clock()} just before sorting 
and just after sorting, so that you don't include the time to generate the random 
numbers or the time to check that the array is sorted.  The difference divided by 
1000000 is the CPU time in seconds.  Give your values at least in 1/100s of a 
second.  You can also measure times by some other method.  Preferred is to do the 
measurement on runner, but failing that you can use any machine.)

\noindent
{\bf Each sort algorithm should:}
\vspace{-0.1in}
\begin{enumerate}
\item Generate {\tt M} random real numbers and store them in an array 
  {\tt double a[M]}.  
(Careful!  The array must be an array of {\tt double}s, not {\tt int}s.  If you used an 
array of {\tt int}s and the random number generator {\tt drand48()}, then all 
numbers would come out 0.  In this case you might have an erroneous sort 
function that seemed to work OK.)
\item By some method, sort the {\tt M} numbers into increasing order.  Note that at the 
end of this step the numbers would usually still be stored in {\tt a}, but not 
necessarily.
\item If they are not already there, store the numbers in the array {\tt a}.
\item Run the \verb+check_sorted()+ function on the array {\tt a} that will check that the
numbers are indeed sorted into increasing order.
\end{enumerate}

\noindent
{\bf Choice of {\tt M}:}
For high-performance sorts, {\tt M} should be at least 100000.  For the 
low-performance sort, choose {\tt M} so that the sort will complete in a reasonable time 
(a minute or an hour).

\noindent
{\bf Choice of sort:}
You are to do one low-performance sort, perhaps insertion or 
selection sort.  Then you are to do each of the various sorts we are studying:
heapsort (as discussed in class and in the handout, not from the text)
tree sort (can be adapted from the white book, or class notes), and
quicksort (presented in class; also in the white book).
Thus you should do four (4) sorts altogether, one low-tech sort, and three high-
performance sorts.  Turn a listing that gives timing results of the sorts.  Everything 
can be combined into one program, with a printed table that identifies the sorts 
and gives their times.

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