\documentstyle[12pt]{cmu-art}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0em}

\newcommand{\subtitle}[1]{{\flushleft{\large\bf #1}}\\}
\newenvironment{denseenumerate}% like enumerate but with less separation
	{\begin{enumerate}\setlength{\itemsep}{0pt}\setlength{\parsep}{0pt}}% 
	{\end{enumerate}}
\newenvironment{denseitemize}% like itemize but with less separation
	{\begin{itemize}\setlength{\itemsep}{0pt}\setlength{\parsep}{0pt}}%
	{\end{itemize}}

\begin{document}

\begin{center}
{\Large\bf 15-211, Spring 1997\\
	Course Information}
\end{center}
\hrule


\bigskip
\section{Organization}

\subtitle{Instructors:}

\vspace{-.2in}
\parbox[t]{2.3in}{
{\em Prof. Guy Blelloch} \\ 4305 Dougherty Hall, x8-6245 \\
blelloch@cs.cmu.edu \\ Hours: Thu. 2:00-3:00}
\parbox[t]{2.3in}{
{\em Prof. Bruce Maggs} \\ 4123 Wean Hall, x8-7654 \\
bmm+@cs.cmu.edu \\ Hours: Thu. 3:00-4:00}
\parbox[t]{2.3in}{
{\em Prof. Gary Miller} \\ 4307 Dougherty Hall, x8-2631 \\
glmiller+@cs.cmu.edu \\ Hours: Mon. 4:00-5:00}
\parbox[t]{2.3in}{
\vspace{.2in}
{\em Prof. Daniel Sleator} \\ 4128 Wean Hall, x8-7563 \\
sleator+@cs.cmu.edu \\ Hours: Mon. 11:00-12:00}

\bigskip

\subtitle{Teaching Assistants:}

\vspace{-.2in}
\parbox[t]{2.3in}{{\em Doug Baker} \\ 8102 Wean Hall, x8-3042 \\
ldbapp+@cs.cmu.edu\\ Hours: Mon. 1:30-2:30}
\parbox[t]{2.3in}{{\em Neil Heffernan} \\ 5101 Wean Hall, x8-8139 \\
neil+@cs.cmu.edu\\ Hours: Fri. 9:00-10:00}
\parbox[t]{2.3in}{{\em William Uther} \\ 8117 Wean Hall, x8-2580 \\
will+@cs.cmu.edu\\ Hours: Thu. 4:00-5:00}

\bigskip

\parbox[t]{3.2in}{\subtitle{Course Secretary:}
{\em Dorothy Zaborowski}\\ 4116 Wean Hall, x8-3779}
%\parbox[t]{3.2in}{\subtitle{Head Grader:}
%{\em Martin Dixon} \\ 3505 Wean Hall \\ mdixon+@andrew.cmu.edu\\
%Hours: TBA
%}

\bigskip

\parbox[t]{3.3in}{
\parbox[t]{3.2in}{\subtitle{Lecture:} TuTh 12:00--1:00,   DH 2210\\ 
Guy Blelloch \\ Bruce Maggs}
\parbox[t]{3.2in}{\subtitle{Honors Recitations:}
\begin{tabular}{rlll}
I & M,W  10:30 & DH 2105 & Doug Baker \\
J & M,W  11:30 & DH 2105 & Doug Baker \\
\end{tabular}}
}
\parbox[t]{3.2in}{\subtitle{Recitations:}
\begin{tabular}{rlll}
A & M,W  8:30  & SC 200 & Neil Heffernan\\
B & M,W  9:30  & SC 200 & Neil Heffernan \\
C & M,W  10:30 & SC 200 & Gary Miller\\
D & M,W  11:30 & SC 200 & Gary Miller\\
E & M,W  12:30 & SC 200 & William Uther\\
F & M,W  1:30  & SC 200 & William Uther\\
G & M,W  2:30  & SC 200 & Daniel Sleator\\
H & M,W  3:30  & SC 200 & Daniel Sleator\\
\end{tabular}}

\bigskip

{\large\bf Course Web page:} \ 
{\tt file://localhost/afs/andrew/scs/cs/15-211/www/home.html}, \\
or {\tt http://www.cs.cmu.edu/afs/andrew/scs/cs/15-211/www/home.html}

\bigskip

\subtitle{Course staff in Wean 5th clusters: } 
Sundays and Mondays before due dates, 8--10pm$+$

\newpage

\section{Textbooks}

\begin{enumerate}
\item T.~A.~Standish, {\it Data Structures, Algorithms, and Software
Principles in C}, Addison-Wesley, 1995.

\item I.~Pohl, {\it C++ for C Programmers}, Benjamin Cummings, 1994.
\end{enumerate}

\section{Course Requirements}

Your participation in the course will involve the following forms of
activity:
attending and participating in lectures and recitations, reading the
texts, doing the homework assignments, and taking the quizzes,
midterm, and final.  You should also periodically read the course 
bulletin boards (discussed in Section \ref{sec:fac}).
%%\begin{denseenumerate}
%%\item Attending and participating in lectures.
%%
%%\item Attending and participating in recitations.
%%
%%\item Reading the texts.
%%
%%\item Assignments
%%
%%\item Quizzes and Exams
%%
%%%%\item Help Sessions (Optional)
%%\end{denseenumerate}

The grade will break down as follows:

%%\begin{quote}
%%\begin{tabular}{ll}
%%Assignments & 40\% \\
%%Quizzes  & 15\% \\
%%Midterm & 15\% \\
%%Final   & 30\% \\
%%\end{tabular}
%%\end{quote}

$$
\begin{array}{l}
\left.
	\begin{array}{ll}
	\mbox{7 Assignments} & \mbox{6\% each} \\
	\mbox{3 Quizzes} & \mbox{6\% each}
	\end{array}
\right \} \mbox{We drop the lowest one out of these 10.}\\
	\begin{array}{ll}
	\mbox{1 Midterm \hspace*{0.2in}} & \mbox{16\%} \\
	\mbox{1 Final}   & \mbox{30\%}
	\end{array}
\end{array}
$$

Although your grade does not depend directly on attendance, you will
be responsible for the material covered {\em both in the main lecture and
in your recitation.}

Grades for the course will be determined by a curve.  First, we will
compute a weighted total of each student's scores on assignments and
exams.  These will be plotted as a histogram, and then approximate
cutoff points for the different letter grades will be determined.
Individual cases, especially those near the cutoff points may then be
adjusted upward or downward based on factors such as 
earned extra credit and participation in recitation discussions. Very 
roughly, we expect to give about 25-30\% A's, 30-40\% B's, 
20-25\% C's, and about 10\% ``other.''  This is not a requirement; we
could give all A's if performance warrants it.

Make-up on the quizzes or exams will be given only by presenting
a letter from your Dean or the Director of Athletics.
Be prepared to present your student I.D. at the Midterm and Final.

The textbooks cover most of the material taught in the course.  In the
schedule shown in section \ref{sched}, you will see the readings
associated with each section of the course.  It would be a good idea to read
over each of these sections twice---a brief reading before the lecture to
become familiar with the basic concepts, and a more thorough reading later to
understand the details.

\section{Recitations} Recitations are Monday and Wednesday.
Recitations will cover new material, go through examples of
material discussed in lecture, and discuss issues related to the
current homework assignment.
%% The Monday  recitation will be more oriented towards the lecture
%% material, discussing  examples of concepts introduced in lecture,
%% as well as introducing new  material at times.  The Wednesday
%% recitations will be more of an informal  discussion generally
%% centered around the current homework.
\section{Class Schedule \label{sched}}

All reading assignments are from Standish.  All assignments are due at
11:59pm on Monday night, except for Assignment 6, which is due at
11:59pm on a Friday night.

\begin{center}
\begin{tabular}{||c|c|c|l|l|l||}
\hline
\input{schedule.tex}
\hline
\end{tabular}
\end{center}

\section{Objectives}

The purpose of 211 is to give students a solid foundation in data structures
and algorithms, plus an appreciation for good program design, especially the
use of abstraction and modularity.

After completing the course, students should have gained a firm grounding  in the following:
\begin{enumerate}
\item
C and C++ programming: functions, pointers, structures, classes, the
memory model, recursion, debugging techniques, I/O, etc.
\item
Foundations of algorithms and data structures.
\begin{itemize}
\item {\em Problem formulation.}
  Extracting a mathematical problem out of
an application task.

\item {\em Data structure selection.}
  Organizing the program data for
efficient problem solution.

\item {\em Algorithm design.}  Finding an efficient and systematic method
for solving the problem.

\item {\em Algorithm analysis.}
\begin{itemize}
\item Methods of proving algorithm correctness.
\item Asymptotic analysis of the space and time required by a program.
\end{itemize}
\end{itemize}

\item
Principles of good programming practice.
\begin{itemize}
\item {\em Modularity.}  Dividing a program into separate components, each having clean and well
defined interfaces.
\item {\em Abstraction.}  Separating the functionality of program component from its internal
construction.
\item {\em Code Design.} Methods for writing code that can be easily
understood and extended.
\end{itemize}

\item The functionality and implementation methods for
standard data abstractions including: queues and stacks, trees, 
priority queues, dictionaries, and graphs.
%% \begin{denseitemize}
%% \item Queues and Stacks
%% \item Trees
%% \item Sets and Sequences
%% \item Priority Queues
%% \item Dictionaries
%% \end{denseitemize}

\item Several standard data structures such as: arrays, 
lists, trees (search trees, balanced trees), hash tables, and graph 
representations (adjacency lists and adjacency matrices).
%% \begin{denseitemize}
%% \item Arrays
%% \item Lists
%% \item Trees: search trees, balanced trees.
%% \item Hash tables
%% \item Representations of graphs: adjacency lists, adjacency matrix
%% \end{denseitemize}

\item Standard computational problems such as sorting, 
searching and various graph problems.
%% \begin{denseitemize}
%% \item Sorting
%% \item Searching
%% \item Graph problems
%% \end{denseitemize}

\item Several algorithmic methods including: 
divide-and-conquer, tree and graph traversal methods, greedy algorithms,
dynamic programming and memoizing.
%%\begin{denseitemize}
%% \item Divide-and-conquer
%% \item Traversals of trees and graphs
%% \item Greedy algorithms
%% \end{denseitemize}

\item The basics of finite automata.
\end{enumerate}

\section{Useful Information}

\subsection{Office hours and help in clusters}

Each member of the course staff has office hours given on the first
page of this document.  If these times are not convenient for you,
please feel free to send email to one of us to set up an appointment.

%% Some of the help sessions will also be dedicated to lectures
%% on special topics, such as C++.  Such lectures will be posted
%% on the {\tt announce} electronic bulletin board.

There will also be TAs or other course staff available in the Wean 5th
floor clusters on Sunday and Monday evenings before assignments are
due to help with frustrating C problems, questions about the course,
the meaning of life, or whatever.

\subsection{Assignments and Quizzes}

Assignments form a critical part of the course work.  Experience has
shown that concepts are best learned by applying them to example
problems or by implementing them in computer programs.  The quizzes
will be based on the material learned in the homeworks, as well as on
recent material covered in class.  

Assignments will typically consist of a programming part and often a
written part as well.  Both are to be handed in electronically.  The
deadline will typically be {\bf Monday night at 11:59PM}.  
%%and in hard copy as well.  {\bf The electronic copy is due by 1:00
%%AM on Tuesday and the hardcopy must be handed in by the beginning of
%%class on Tuesday (12:00PM)}.  Handins after class starts will be
%%considered late.  
Late assignments will be accepted with a 20 point penalty {\bf up
until 8:30AM Wednesday}.  You may {\em not} hand in part of an
assigment on-time and part of it late.
More information on electronic handin procedures is in section
\ref{sec:fac} and explicit instructions will be given on each homework
as well.

The grade on the programming part of an assignment will be broken down
into two parts:
\begin{itemize}
\item
Style:  Modularity, readability, commenting, etc.
\item
Functionality:  Works properly.
\end{itemize}
%% Note: programs with small bugs but that are well documented and 
%% demonstrate that the student understands where the problems are even if 
%% he or she cannot fix them will generally still receive a good score.

\subsection{Cheating and Collaboration}
Certain forms of collaboration are beneficial for helping all involved
understand the material better and overcome small stumbling blocks.
Blatant copying of homeworks is not.  What you hand in should be your
own work.  The following are guidelines on what collaboration on
homeworks is authorized and what is not.

\paragraph{Not Cheating:}
\begin{itemize}
\item Clarifying ambiguities or vague points in class handouts or textbooks.

%%\item Helping another student use the computer systems, networks,
%%compilers, or other system facilities.

\item Discussing or explaining the general class material.

\item Providing assistance in C or C++, Purify, or in using the system
facilities.  Helping each other debug programs.

\item Discussing together the code that {\em we give out\/} on the 
assignment.
\end{itemize}

\paragraph{Cheating:}
\begin{itemize}
\item  Copying files, retyping another person's files, copying files and 
changing the variable names, etc.  Also, {\it allowing}
someone else to copy your code is cheating.

\item Copying another person's written assignment or allowing someone 
else to  copy yours.

\item If you do not understand what you are handing in, you are 
probably cheating.

\end{itemize}
Also it goes without saying that copying on quizzes or exams is cheating.

Because we are grading on a curve, to be fair to all students we must
enforce a strict policy with respect to cheating.  Programs that are
identical or exhibit suspicious similarities will be automatically
flagged, and students will be asked to explain how such similarities
came about and how their programs work.
%%identical up to cosmetic changes will be automatically identified, 
%% Students may also be asked to explain how their programs work, and
%% failure to give an adequate explanation may result in a penalty for
%% poor documentation.  
The penalty for cheating will depend on the severity of the offense
and the student's past record in this regard.  {\it At the very least}
the student will be given a score of 0 for the assignment.  Typically
a 6\% reduction in overall grade in the course will also be imposed.
Two or more infractions will result in failure in the course.

To help prevent cheating, you should read-protect
the directory in which you develop your assignments (if you
work on an Andrew machine). To protect a directory named,
for example, {\tt 211progs}, you would type the command
\begin{center}
{\tt fs sa 211progs} {\it username} {\tt all -clear}
\end{center}
where {\it username} is your Andrew userID. Please read-protect
any directories in which you develop code for 15-211.

\section{Facilities \label{sec:fac}}

\paragraph{Programming:} 

We will be using the Purify environment for writing C++ programs.
With very few exceptions, Ansi C programs are legal C++ programs.  We
will teach several C++ constructs that are not part of C, that serve
the purposes of the course.  You are allowed to use C++ features not
taught in class in your programs, as long as they make your program
simpler or more understandable (C++ has many constructs that can
easily make a program less understandable; please don't throw them in
just to seem more impressive).

You may develop your code using whatever compiler you want, and on
whatever machine you want.  However, your final program must be a
legal C++ program that can be compiled using g++, the GNU C++
compiler.

\paragraph{Electronic Hand-in:}

Assignments will typically consist of a programming part and a written
part.  Both parts are to be handed in electronically.  To hand in an
assignment, simply copy the appropriate files into your ``handin''
directory.

If there are written exercises, you should put your solutions in a
plain text file.

If the programming part of your handin does not work correctly, you
should create a file called {\tt bugreport}, which should be copied
into the handin directory along with your code.  The purpose of {\tt
bugreport} is for you to describe what problems your program has, and
what might be the causes for them.  This will help the graders give
you partial credit, and it is to your advantage to hand this file
in. In particular, if your program only works partially, or you have
some idea what needs to be fixed, or where the bug(s) are, say so!! It
will help establish to the grader that you understand what's going on,
what the problems are, and why you should get at least partial credit
for your program.

At each of the deadline times for an assignment, a program will scan
through your handin directories, scooping up your files.
You will receive email confirmation of the files found
sometime after the handin deadline.


\relax{\bf If you wish to hand in late, you must make certain your handin
directory has no files in it at the regular handin time} (and for a
few more hours while collection is taking place). If there 
is even a single file present at this time, the system will treat
that as your handin, and will ignore any late-handins.
To repeat: you are only allowed to submit your file(s) for collection
once (i.e. whatever is in the handin directory at the
collection time is what you've handed in).
Up until the handin time, 
you can copy new versions of your file(s) into
your handin directory as many times as you want.

Only you plus the teaching and grading staff have access to your
handin directory.  You must be logged in under your Andrew user ID to
get access to your directory.

\paragraph{Getting handouts:}
If you miss a handout in class, you can get it electronically from
{\tt /afs/andrew/scs/cs/15-211/handouts}.  Make sure you know how to
print out PostScript documents before printing them.  You can also get
handouts and other information from our web page at {\tt
/afs/andrew/scs/cs/15-211/www/home.html}.

\paragraph{Communicating:}

For urgent communication with the teaching staff, it is best to
send electronic mail to the addresses on the first page of this document.
We have also set up two bulletin boards for this class,
{\tt cmu.cs.class.cs211.announce} and {\tt cmu.cs.class.cs211.discuss}.
\begin{description}
\item[{\tt announce}] For official announcements about the class.  {\it Only
course staff may post to this bulletin board}.
\item[{\tt discuss}] For general discussion, particularly among members of
the class.  Post here if you need a clarification or if you are confused
about some part of an assignment.
\end{description}

{\bf We ask that students refrain from insulting anyone on the
bulletin board.}

\section{Who to See?}

Since the teaching staff for this class is large, you might wonder
who you should see about what.  Here is some help.

\begin{itemize}
\item {\bf Clarifications on the homework:} If the question does
not give away any of the solution, you should post the question on the
{\tt discussion} bulletin board.  The course staff reads the bulletin
board regularly and will try to answer your question as soon as
possible.  If the question requires giving away part of the solution,
send one of the TA's email or see one of the course
staff during office hours.

\item {\bf You need help on the homework or class material:} Talk with
the member of the course staff in the cluster, send one of the TAs or
instructors email, or see any of the TAs or instructors during their
office hours.  Please don't feel intimidated about going to office
hours.

\item {\bf Questions about your grade on a homework:} See your
recitation instructor.  You can send email to set up a meeting if the
office hours are inconvenient.

\item {\bf Questions about your grade on a quiz or test:} See your
recitation instructor or talk with Prof. Blelloch or Prof. Maggs.  You
can send email or come by during office hours.

\item {\bf The course is taking too much of your time:}  This
course is supposed to take 12 hours a week.  If on average you are
spending significantly more than this, we want to know.  Please send
one of the instructors an email message telling them.  Sometimes
it is hard for us to judge the difficulty of an assignment and
your message lets us know when there is a problem.

\item {\bf General academic questions:}  The course staff is happy
to answer general academic questions, such as ``is it worth it
for me to take 15-212?''   You should catch one of us after class or
recitation, or see us during office hours.
\end{itemize}

We hope you will enjoy the course, and the staff is always glad to
hear your comments or suggestions.

\end{document}
