\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}

\head{1390}{Algorithms}{Winter 1999}{11 February 1999}{17}

\begin{center}
{\Large {\bf Clarifications on Programming Assignment 1}}
\end{center}
\bigskip

\begin{itemize}
\item
You should assume that $n$ is a multiple of $k$.  This will tremendously
simplify matters since we do not have to worry about floors and ceilings.  
Thus, for example, since $n$ will be set to $5000$ for the tests, the
possible values of k are 2, 5, 10, 20, 25, 40, \ldots, 100, \ldots, 1000, 2500.

\item
The first sentence of the assignment says: ``The $k$th quantiles of an
$n$-element list are a set of $k - 1$ elements from the list that divide the
sorted list into k equal-sized sets (to within $1$).''  The phrase ``to within
$1$'' may be somewhat confusing.

What it means is that each of the $k$ sets must have either $(n/k) - 1$
elements or $(n/k)$ elements.  (Note that since we have assumed $n$ to be a
multiple of $k$, $(n/k)$ is an integer.)

\item
Your program will be evaluated on the basis of the number of {\bf comparisons}
it performs.  You need to count only those comparisons in which {\bf at least
one of the operands is an input element}.  The operations that will be
considered as comparison operations are $=$, $<$, $>$, $\le$, and $\ge$.

Thus, for example, you need not count the comparison $i < n$, where $i$ is a
running index.  Note, however, that if an input element is stored in a
temporary variable which is then compared, this does count as a comparison.

\item
You should {\bf not}\/ make any assumptions about the input elements other
than what is stated in the assignment; that is, they are distinct integers.

\item
You may write your program in any standard programming language as long as the
grader will be able to compile it.  In particular, any of C, C++, and Java is
fine.
\end{itemize}
\end{document}
